Sudoku A

**JosAH** · May 12 '07, 02:49 PM

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, but because of a puzzle: Sudoku.

This is what Sudoku is all about:[code=text]

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

This article is a three part article mainly because of the maximum size allowed
for an Article using this forum software. The first part of the article goes
through the basic functionality we need for 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:

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

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

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:

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:

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:

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:

Code:

private void reset(int i, int j) {
		
	// adjust to the range 0 ... 8
	int val= board[i][j]-1;

	board[i][j]= 0;

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

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:

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. See you there.

kind regards,

Jos