Greetings,
welcome back to part three of the Sudoku article. This part describes the actual
Sudoku solver. The solver works quite simple: given a cell to be filled in,
try all possible values and solve the rest of the board. If all cells are filled
the Sudoku puzzle is solved.
The solver iterates over all cells, left to rigth, top to bottom. It receives
two parameters i and j which are the indexes of the cell to be filled in. The
cell could be filled in already (it was a given cell value) in which case the
solver has to find a next position. The first part of the solve method tries
to find an empty cell:
-
private boolean solve(int i, int j) {
-
-
for(;;) {
-
if (j >= columns.length) {
-
j= 0;
-
i++;
-
}
-
-
if (i >= rows.length) return true;
-
-
if (board[i][j] > 0) j++;
-
else break;
-
}
-
...
If you carefully inspect this piece of code you see that every row is checked,
column by column. When the last column has been checked a next row is checked
again until all cells are checked in which case the Sudoku puzzle is solved
and true is returned. Otherwise an empty cell has been found and the piece of
the code following this for loop is executed. The next piece of this method
recursively tries to solve the Sudoku puzzle:
-
...
-
for (int val= 0; val < squares.length; val++) {
-
if (possible(i, j, val))
-
if (!solve(i, j+1)) {
-
reset(i, j);
-
}
-
else
-
return true;
-
}
-
-
return false;
-
}
For the current cell all values 0 ... 8 are tried. If a value is feasible
it is filled in and an attempt is made to solve the rest of the Sudoku puzzle.
If the attempt fails the cell is reset and a next value is tried. If the
attempt was successful the method returns immediately because the entire
puzzle was solved. Otherwise the loop ends (none of the values were feasible
for that particular cell i,j) and the method returns false.
Note that this method is a private method. I did that on purpose because I
don't want other objects to supply the two index values. Here's a public
method that does it for them:
-
public boolean solve() {
-
return solve(0, 0);
-
}
All we need now is a simple driver method that creates a Sudoku solver object,
opens a Reader, initializes the puzzle and fires up the solver. We'll implement
the driver functionality in the main() method for reasons of simplicity:
-
public static void main(String[] args) throws Exception {
-
-
Sudoku s= new Sudoku();
-
FileReader fr= new FileReader(args[0]);
-
-
if (s.read(new FileReader(args[0))) {
-
if (s.solve()) {
-
s.print(new OutputStreamWriter(System.out));
-
}
-
else
-
System.err.println("problem cannot be solved");
-
}
-
else
-
System.err.println("problem file cannot be read");
-
}
Note that this is a very sloppy implementation, i.e. when something goes
seriously wrong, e.g. no file name was passed to the main method or the
actual reading failed, an Exception is simply passed on to the JVM which will
print an ugly stack trace. We even didn't bother to close the FileStream
properly: when the JVM exits the FileReader will be closed anyway.
I leave it up to your imagination and creativity to implement a proper,
industrial strength driver. The one above serves fine for demonstration
purposes in this article.
I created a file "/sudoku.txt" with the following content I found in an
old newspaper:
-
+-------+-------+-------+
-
| 7 . . | . . . | 4 . . |
-
| . 2 . | . 7 . | . 8 . |
-
| . . 3 | . . 8 | . . 9 |
-
+-------+-------+-------+
-
| . . . | 5 . . | 3 . . |
-
| . 6 . | . 2 . | . 9 . |
-
| . . 1 | . . 7 | . . 6 |
-
+-------+-------+-------+
-
| . . . | 3 . . | 9 . . |
-
| . 3 . | . 4 . | . 6 . |
-
| . . 9 | . . 1 | . . 5 |
-
+-------+-------+-------+
Then I started the Sudoku class:
-
java -classpath . Sudoku /sudoku.txt
And this is what was printed almost immediately:
-
+-------+-------+-------+
-
| 7 9 8 | 6 3 5 | 4 2 1 |
-
| 1 2 6 | 9 7 4 | 5 8 3 |
-
| 4 5 3 | 2 1 8 | 6 7 9 |
-
+-------+-------+-------+
-
| 9 7 2 | 5 8 6 | 3 1 4 |
-
| 5 6 4 | 1 2 3 | 8 9 7 |
-
| 3 8 1 | 4 9 7 | 2 5 6 |
-
+-------+-------+-------+
-
| 6 1 7 | 3 5 2 | 9 4 8 |
-
| 8 3 5 | 7 4 9 | 1 6 2 |
-
| 2 4 9 | 8 6 1 | 7 3 5 |
-
+-------+-------+-------+
I checked the next days' newpaper and indeed: both the newspaper as well as the
solver showed this same solution. Just for fun I changed the content of my
/sudoku.txt file:
-
+-------+-------+-------+
-
| . . . | . . . | . . . |
-
| . . . | . . . | . . . |
-
| . . . | . . . | . . . |
-
+-------+-------+-------+
-
| . . . | . . . | . . . |
-
| . . . | . . . | . . . |
-
| . . . | . . . | . . . |
-
+-------+-------+-------+
-
| . . . | . . . | . . . |
-
| . . . | . . . | . . . |
-
| . . . | . . . | . . . |
-
+-------+-------+-------+
and fired up the solver again; this was the output:
-
+-------+-------+-------+
-
| 1 2 3 | 4 5 6 | 7 8 9 |
-
| 4 5 6 | 7 8 9 | 1 2 3 |
-
| 7 8 9 | 1 2 3 | 4 5 6 |
-
+-------+-------+-------+
-
| 2 1 4 | 3 6 5 | 8 9 7 |
-
| 3 6 5 | 8 9 7 | 2 1 4 |
-
| 8 9 7 | 2 1 4 | 3 6 5 |
-
+-------+-------+-------+
-
| 5 3 1 | 6 4 2 | 9 7 8 |
-
| 6 4 2 | 9 7 8 | 5 3 1 |
-
| 9 7 8 | 5 3 1 | 6 4 2 |
-
+-------+-------+-------+
The output clearly shows that the solver works its way through the problem in
a strictly left to right, top to bottom manner: check the first row and the
first sub-square and see the regularity.
This is a naive solver but it works fine for the problems I tried. Some problems
are considered to be extremely difficult. Play with this solver a bit, feed it
some of those difficult problems and see how it runs.
The Sudoku class only needs a Reader and a Writer, i.e. it doesn't care how
these streams were created. You can even create a free Sudoku solver server
out of it if you feel like it: wrap a Reader around an InputStream created
by a socket. Do the same for the Writer and the socket's OutputStream.
This solver finds the 'first' solution given a problem. You might try and
alter the 'solve' method a bit so that it finds all solutions. It's up to you.
Until next week when a bit more serious matters will be discussed a bit.
kind regards,
Jos
