11,448
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:
Expand|Select|Wrap|Line Numbers
- +-------+-------+-------+
- | . . . | . . . | . . . |
- | . . . | . . . | . . . |
- | . . . | . . . | . . . |
- +-------+-------+-------+
- | . . . | . . . | . . . |
- | . . . | . . . | . . . |
- | . . . | . . . | . . . |
- +-------+-------+-------+
- | . . . | . . . | . . . |
- | . . . | . . . | . . . |
- | . . . | . . . | . . . |
- +-------+-------+-------+
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:
Expand|Select|Wrap|Line Numbers
- ... 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 | . . . | . . . | . . . |
- +-------+-------+-------+
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':
Expand|Select|Wrap|Line Numbers
- boolean[][] rows= new boolean[9][9];
- ...
- if (row[i][val]) // 'val' is already present in row 'i'
Expand|Select|Wrap|Line Numbers
- boolean[][] columns= new boolean[9][9];
- ...
- if (columns[j][val]) // 'val' is already present in column 'j'
the regularity and jotted down this:
Expand|Select|Wrap|Line Numbers
- boolean[][] squares= new boolean[9][9];
- ...
- if (squares[3*(i/3)+j/3][val]) // 'val' is already present in this square
Expand|Select|Wrap|Line Numbers
- private int[][] board= new int[9][9];
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:
Expand|Select|Wrap|Line Numbers
- 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,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:
Expand|Select|Wrap|Line Numbers
- 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;
- }
Here's a convenient method that fills a cell with a digit:
Expand|Select|Wrap|Line Numbers
- public boolean setValue(int i, int j, int val) {
- return possible(i, j, val-1);
- }
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:
Expand|Select|Wrap|Line Numbers
- public int getValue(int i, int j) {
- return board[i][j];
- }
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
