#### Sudoku

by

, 06-23-2011 at 01:32 PM (3371 Views)
Greetings,

a couple of years ago a large part of the world went totally mad. Not because of global climate changes, not because of terrible wars that were started in the Middle East, nor because of global famine, nor because of large investment banks going bankrupt and nor because of Tsunamis, but because of a puzzle: Sudoku.

This is what Sudoku is all about:

At the positions of the dots we're allowed to jot down a digit 1 ... 9 with the restriction that a digit only occurs exactly once in every row, column and in every little 3x3 sub-square. Sounds easy enough, but still millions of people all over the globe found this little puzzle much more important than the disasters described above.Java Code:+-------+-------+-------+ | . . . | . . . | . . . | | . . . | . . . | . . . | | . . . | . . . | . . . | +-------+-------+-------+ | . . . | . . . | . . . | | . . . | . . . | . . . | | . . . | . . . | . . . | +-------+-------+-------+ | . . . | . . . | . . . | | . . . | . . . | . . . | | . . . | . . . | . . . | +-------+-------+-------+

Basic functionality

The first part of this article goes through the basic functionality needed by our Sudoku solver. I don't like these types of puzzles: I have to think a lot, jot down what I

did before, correct my mistakes etc. etc. So I decided to build a little program that would solve the thing for me. I took my scribbling paper and did this:

I merely numbered the rows, columns and I gave the nine little squares an index number too. I also decided that I wanted to fill every position with the digits 1 ... 9 but Java prefers index values 0 ... 8 instead.Java Code:0 1 2 3 4 5 6 7 8 +-------+-------+-------+ 0 | . . . | . . . | . . . | 1 | . 0 . | . 1 . | . 2 . | 2 | . . . | . . . | . . . | +-------+-------+-------+ 3 | . . . | . . . | . . . | 4 | . 3 . | . 4 . | . 5 . | 5 | . . . | . . . | . . . | +-------+-------+-------+ 6 | . . . | . . . | . . . | 7 | . 6 . | . 7 . | . 8 . | 8 | . . . | . . . | . . . | +-------+-------+-------+

Given a row index 'i' and a column index 'j' I want to check whether or not I can put a digit value 'val' in there. For the rows I need a boolean value that tells me if the value 'val' is already taken in row 'i':

The same for a value 'val' in column 'j':Java Code:boolean[][] rows= new boolean[9][9]; ... if (row[i][val]) // 'val' is already present in row 'i'

And then there are those little squares ... after a bit of scribbling I noticed the regularity and jotted down this:Java Code:boolean[][] columns= new boolean[9][9]; ... if (columns[j][val]) // 'val' is already present in column 'j'

And of course I need that little board itself:Java Code:boolean[][] squares= new boolean[9][9]; ... if (squares[3*(i/3)+j/3][val]) // 'val' is already present in this square

So far so good: I can mark those three two dimensional arrays when I want to put a value 'val' there. Let's write some code for it; the 'val' value has to be a value in the range 0 ... 8 but I want to store values 1 ... 9 instead; here goes:Java Code:private int[][] board= new int[9][9];

This little method returns false if the digit 'val' cannot be put at location i,j and it returns true if it can be stored there.Java Code:private boolean possible(int i, int j, int val) { // position already taken or invalid? if (rows[i][val] || columns[j][val] || squares[3*(i/3)+j/3][val]) return false; // position i,j is taken now: rows[i][val]= true; columns[j][val]= true; squares[3*(i/3)+j/3][val]= true; board[i][j]= val+1; return true; }

I want to remove a digit from the board too so I wrote this:

Most (if not all of) those Sudoko puzzles have a few cells filled in already. Here's a convenient method that fills a cell with a digit:Java Code:private void reset(int i, int j) { // adjust to the range 0 ... 8 int val= board[i][j]-1; // location i,j is free: squares[3*(i/3)+j/3][val]= false; columns[j][val]= false; rows[i][val]= false; }

This method assumes digits in the normal range 1 ... 9 and takes care of the adjustment to the range 0 ... 8. If the digit can not be set at that position for one reason or another, the method returns false. If there were no problems the method returns true.Java Code:public boolean setValue(int i, int j, int val) { return possible(i, j, val-1); }

And here's a simple method that gets a value at a position i,j:

We have the primitive functionality now: we can correctly get and set a cell value and we can reset it again. We can't solve the Sudoku puzzle yet nor can we conveniently set up the entire board and we can't even print it properly. Reading and writing entire Sudoku boards will be the subject of the second part of this article.Java Code:public int getValue(int i, int j) { return board[i][j]; }

Sudoku I/O

The second part of the article defines two groups of methods. One method that is able to read an entire Sudoku board and a couple of methods that can write such a board, using a nice format.

We want a method that can read from aReaderstream and initialize the board accordingly. It would be very convenient if we could read a text file with content as shown in the example board as shown in th first part of this article.

Basically we want to read 81 digits or dots; a dot and a '0' both describe an empty cell, while the digits 1 ... 9 describe a filled cell. Here goes:

The next group of methods can print a board given aJava Code:public boolean read(Reader r) { int i= 0, j= 0; // the first position of the board try { // keep on reading characters: for (int x; (x= r.read()) != -1; ) { // skip it if not a digit nor a dot if (!(Character.isDigit(x) || x == '.')) continue; // is it a digit 1 ... 9? if (!(x == '0' || x == '.')) setValue(i, j, x-'0'); // position i,j at next position, return when done if ((j= (j+1)%9) == 0) if (++i == 9) return true; } } catch (IOException ioe) { } // something went wrong return false; }Writer. It prints the board using the same format as shown in the example board shown in the first part of the article:

Note that both the read method and the write method do not close the character streams; the Reader and Writer were passed in as a parameter so the caller of these methods is responsible for closing the streams. The read method does catch IOExceptions and simply returns false; all that the caller knows is that a board could not be read for some reason, i.e. an IOException was thrown or the content of the Reader didn't make up a valid board configuration.Java Code:// print a horizontal separator line private void printHorizontal(PrintWriter p) { p.println("+-------+-------+-------+"); } // print a little vertical line private void printVertical(PrintWriter p) { p.print("| "); } // print the Sudoku board public void print(Writer w) { PrintWriter p= new PrintWriter(w); for (int i= 0; i < rows.length; i++) { if (i%3 == 0) printHorizontal(p); for (int j= 0; j < columns.length; j++) { if (j%3 == 0) printVertical(p); p.print(board[i][j]+" "); } printVertical(p); p.println(); } printHorizontal(p); p.flush(); }

Now we have all the primitive methods to manipulate a Sudoku board: we can test and set a value anywhere on the board, we can reset a cell again, we can initialize and entire board given a Reader and finally we can print the Sudoku board given a Writer.

The third and last part of the article shows the actual Sudoku solver. All methods shown above are part of a 'Sudoku' class. The solver method will also

be a member method.

Sudoku solver

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:

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:Java Code: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; } ...

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.Java Code:... 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; }

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:

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:Java Code:public boolean solve() { return solve(0, 0); }

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.Java Code: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"); }

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 a newspaper:

Then I started the Sudoku class:Java Code:+-------+-------+-------+ | 7 . . | . . . | 4 . . | | . 2 . | . 7 . | . 8 . | | . . 3 | . . 8 | . . 9 | +-------+-------+-------+ | . . . | 5 . . | 3 . . | | . 6 . | . 2 . | . 9 . | | . . 1 | . . 7 | . . 6 | +-------+-------+-------+ | . . . | 3 . . | 9 . . | | . 3 . | . 4 . | . 6 . | | . . 9 | . . 1 | . . 5 | +-------+-------+-------+

And this is what was printed almost immediately:Java Code:java -classpath . Sudoku /sudoku.txt

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:Java Code:+-------+-------+-------+ | 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 | +-------+-------+-------+

and fired up the solver again; this was the output:Java Code:+-------+-------+-------+ | . . . | . . . | . . . | | . . . | . . . | . . . | | . . . | . . . | . . . | +-------+-------+-------+ | . . . | . . . | . . . | | . . . | . . . | . . . | | . . . | . . . | . . . | +-------+-------+-------+ | . . . | . . . | . . . | | . . . | . . . | . . . | | . . . | . . . | . . . | +-------+-------+-------+

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.Java Code:+-------+-------+-------+ | 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 | +-------+-------+-------+

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.

Today the Sudoku madness went a bit down, but I can still see those silly puzzles in the newspapers. I don't care anymore, I have my Sudoku solver ;-)

kind regards,

Jos

## Having trouble writing a recursive...

Today, 10:29 AM in Advanced Java