View RSS Feed

JosAH's blog

Sudoku

Rate this Entry
by , 06-23-2011 at 01:32 PM (3092 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:

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

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:

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 | . . . | . . . | . . . |
	  +-------+-------+-------+
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.

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':

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

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

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

Java Code:
private int[][] board= new int[9][9];
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 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;
}
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.

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

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;
}
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:
public boolean setValue(int i, int j, int val) {
		
	return possible(i, j, val-1);
}
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.

And here's a simple method that gets a value at a position i,j:
Java Code:
public int getValue(int i, int j) {
	return board[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.

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 a Reader stream 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:

Java 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;
}
The next group of methods can print a board given a Writer. It prints the board using the same format as shown in the example board shown in the first part of the article:

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();
}
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.

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:

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

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

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");
}
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 a newspaper:

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 |
+-------+-------+-------+
Then I started the Sudoku class:

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

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 | 
+-------+-------+-------+
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:
+-------+-------+-------+
| . . . | . . . | . . . | 
| . . . | . . . | . . . |
| . . . | . . . | . . . |
+-------+-------+-------+ 
| . . . | . . . | . . . |
| . . . | . . . | . . . |
| . . . | . . . | . . . |
+-------+-------+-------+ 
| . . . | . . . | . . . |
| . . . | . . . | . . . |
| . . . | . . . | . . . |
+-------+-------+-------+
and fired up the solver again; this was the output:

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 | 
+-------+-------+-------+
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.

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
go4soumya and AlexGraal like this.

Submit "Sudoku" to Facebook Submit "Sudoku" to Digg Submit "Sudoku" to del.icio.us Submit "Sudoku" to StumbleUpon Submit "Sudoku" to Google

Updated 06-23-2011 at 03:52 PM by JosAH

Tags: None Add / Edit Tags
Categories
Uncategorized

Comments

  1. doWhile's Avatar
    • |
    • permalink
    Nice blog post. I loved programming Sudoku's - fun exercises. Noticed the first solution your solver creates (based upon an empty puzzle)...for what its worth, there is an easy and fast way to create unique solved puzzles (in case one wishes to write a game that gives a user a starting point) - take that solution then swap rows and columns within the same grid 'trio'. Do this randomly a few times and you've got a solution to work with
  2. JosAH's Avatar
    • |
    • permalink
    Thanks for the compliment; interesting idea: randomly fill one 'sub square' with the numbers 1 ... 9; ths is always a valid sub-solution. Based on this sub-square try to fill the other sub-squares; I don't know whether or not it is faster than my brute force solution (which is quite fast b.t.w.)

    kind regards,

    Jos
  3. go4soumya's Avatar
    • |
    • permalink
    It's really great!!...and loved the way ou started the blog post :D