By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
462,168 Members | 714 Online
Bytes IT Community
Submit an Article
Got Smarts?
Share your bits of IT knowledge by writing an article on Bytes.

Sudoku A

Expert 10K+
P: 11,448
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:
Expand|Select|Wrap|Line Numbers
  1.  
  2.  
  3. +-------+-------+-------+ 
  4. | . . . | . . . | . . . | 
  5. | . . . | . . . | . . . |
  6. | . . . | . . . | . . . |
  7. +-------+-------+-------+ 
  8. | . . . | . . . | . . . |
  9. | . . . | . . . | . . . |
  10. | . . . | . . . | . . . |
  11. +-------+-------+-------+ 
  12. | . . . | . . . | . . . |
  13. | . . . | . . . | . . . |
  14. | . . . | . . . | . . . |
  15. +-------+-------+-------+
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:
Expand|Select|Wrap|Line Numbers
  1. ... 0 1 2   3 4 5   6 7 8
  2.   +-------+-------+-------+ 
  3. 0 | . . . | . . . | . . . | 
  4. 1 | . 0 . | . 1 . | . 2 . |
  5. 2 | . . . | . . . | . . . |
  6.   +-------+-------+-------+ 
  7. 3 | . . . | . . . | . . . |
  8. 4 | . 3 . | . 4 . | . 5 . |
  9. 5 | . . . | . . . | . . . |
  10.   +-------+-------+-------+ 
  11. 6 | . . . | . . . | . . . |
  12. 7 | . 6 . | . 7 . | . 8 . |
  13. 8 | . . . | . . . | . . . |
  14.   +-------+-------+-------+
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':
Expand|Select|Wrap|Line Numbers
  1. boolean[][] rows= new boolean[9][9];
  2. ...
  3. if (row[i][val]) // 'val' is already present in row 'i'
The same for a value 'val' in column 'j':
Expand|Select|Wrap|Line Numbers
  1. boolean[][] columns= new boolean[9][9];
  2. ...
  3. 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:
Expand|Select|Wrap|Line Numbers
  1. boolean[][] squares= new boolean[9][9];
  2. ...
  3. if (squares[3*(i/3)+j/3][val]) // 'val' is already present in this square
And of course I need that little board itself:
Expand|Select|Wrap|Line Numbers
  1. 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:
Expand|Select|Wrap|Line Numbers
  1. private boolean possible(int i, int j, int val) {
  2.  
  3.     // position already taken or invalid?
  4.     if (rows[i][val] || columns[j][val] || 
  5.         squares[3*(i/3)+j/3][val])
  6.         return false;
  7.  
  8.     // position i,j is taken now:        
  9.     rows[i][val]= true;
  10.     columns[j][val]= true;
  11.     squares[3*(i/3)+j/3][val]= true;
  12.  
  13.     board[i][j]= val+1;
  14.  
  15.     return true;
  16. }
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:
Expand|Select|Wrap|Line Numbers
  1. private void reset(int i, int j) {
  2.  
  3.     // adjust to the range 0 ... 8
  4.     int val= board[i][j]-1;
  5.  
  6.     board[i][j]= 0;
  7.  
  8.     // location i,j is free:        
  9.     squares[3*(i/3)+j/3][val]= false;
  10.     columns[j][val]= false;
  11.     rows[i][val]= false;
  12. }
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:
Expand|Select|Wrap|Line Numbers
  1. public boolean setValue(int i, int j, int val) {
  2.  
  3.     return possible(i, j, val-1);
  4. }
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:
Expand|Select|Wrap|Line Numbers
  1. public int getValue(int i, int j) {
  2.     return board[i][j];
  3. }
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
May 12 '07 #1
Share this Article
Share on Google+