OHJ-2206 project topic 2010:
Sudoku
The problem
Sudoku is a puzzle where the goal is to fill the missing numbers
in a typically 9×9 grid such that each row, column, and 3×3 block
contains all the numbers from 1 to 9.
A typical Sudoku board looks like:
The solution is (completed numbers are drawn in red):
More advanced or simpler Sudoku boards can be created by changing the
size of the grid, which is determined by the number of rows
and columns of the constituent blocks. The following Sudoku puzzle has
2×3 blocks, where N = 2 × 3 = 6 numbers must be placed in
each row, column and block, making the entire grid 6×6.
The goal of the program is to solve Sudoku boards of varying size and
print the solution, or respond that it has
no solution. If the puzzle has more than one solution, the program may freely
choose which solution it prints.
Solving Sudoku puzzles for an N × N grid
is known to be an NP-complete problem, and so any solver must eventually
guess to find a solution to the more difficult puzzles. However, a more robust
solver could use logic to fill in some numbers and minimize the amount
of backtracking that must be done.
Your program must use at least one idea to reduce the amount of
backtracking, and the idea and its implementation must be described in the
document.
The input
The input has the following syntax:
R and C are natural numbers.
This part obeys the usual lexical rules in this course.
Among other things, R and C are separated from each other with
spaces and/or ends of lines (C++ \n).
At the end of this part there must be an end of line so that <Content>
starts in the beginning of a line.
<Content> is formatted in a special way.
It uses spaces and empty lines to represent the borders of blocks and to
imitate how sudokus are usually printed.
It consists of RC+C–1 lines, where each line consists of
RC+R–1 characters.
Let the first line be called line 1.
Lines R+1, 2R+2, …,
(C–1)R+(C–1) are empty, that is, they only
contain an end of line each.
Each remaining line first has C data characters, then a space, then
C data characters and so on, until there have been altogether
RC data characters and R–1 spaces.
After them is an end of line.
A data character is a digit 1, 2, …,
9, capital letter A, B, …,
W, or the period ..
The digits denote values from 1 to 9, the letters denote values from 10 to 32
(where A = 10, B = 11, and so on),
and the period denotes an empty square.
(The absence of codes for numbers greater than 32 implies that
RC ≤ 32.
This might be handy when using 32-bit integers.)
An example of a valid input corresponding to the first puzzle given above
is as follows:
3
3
.3. .15 9.2
.1. ..6 ...
6.5 7.. ...
... .5. ..9
4.7 .8. 1.6
9.. .6. ...
... ..1 7.4
... 6.. .9.
5.1 49. .3.
And this is the second puzzle given above:
2 3
... .4.
4.5 6..
.6. .2.
.5. .3.
..6 1.4
.4. ...
The output
If the input has no solution, the program must print zero (that is,
0) and end of line.
Otherwise, the program must print one solution (it does not matter which one)
in the same format as the input.