Saturday, June 16, 2012

In this post, I'll be discussing on how to a make a SUDOKU solver-cum-helper.

lets start:
The basic point behind the helper is that for a particular cell of the board, we find the possible numbers that it can take based on:
1.its row,
2.column and
Exploring further, at first, we find what numbers we need for a row to be completely filled and satisfy the invariant.similar is for column and the box.
So, we represent the rows, columns and boxes by 2-D arrays.
Now, for the particular cell, the possible numbers it can take will be the numbers which are supported by all the three-its row,column and box, i.e. basically we want to AND the numbers common to the these three to ""produce"" the possibilities for the current cell.Therfore, to facilitate this, we will be using bitwise coding.

                             declaration and initialisation

Now, what's the use of this 3-D array?
Well, obviously we need something to store each cell's possibilities.Dont focus on the initialisation part now, you will get to know after the following explanation

Now, how the bitwise coding actually works in this case:
first, let me tell you what the above arrays represent:
a statement like row[1][i]=0110101001(i:0 to 9)->represents that ith row doesn't contain the numbers [1,2,4,6,9], i.e row[i][j] is set 'j' is not present in the ith row.This way, bitwise coding is used to show the possibilities, the respective row, column or box has.Similar logic for the Xboard array: Xboard[i][j][k] is set if board[i][j] cell be filled with k, and is '0' if 'k' can't be placed in board[i][j] in any case.The '0th' bit in all the above cases has a special purpose.It is set if the field is completely filled and unset in all other cases.
Now, the above image is quite easy to understand I suppose.

Now, the most important thing:
To calculate the each cell's possibility through its row,col & box.
Actually nothing great to be done, just AND the possibilities of all the three for a specific cell.This is obvious, since a number is an option in a field if it is allowed in it's row, column and group.
                                         calculating the possibility

k..I guess the helper is ready now.
Yup, having the possibilities for each cell actually helps a lot in solving(At least it works for me always).
Additionally, warnings in following cases can be generated:
1) fields without any option but not completely filled.
2) rows, columns or groups with missing options can be generated.

Lets proceed with coding a small solver using the above info:
Actually, its quite simple.Having before yourself all the possibilities, now you just need to figure out the cells having only one possibility(yes there will be such cells) and yes, you guessed right man->FILL THEM !.
Filling these cells will obviously change the possibilities of the other cells.So, run the possibility checker again and this goes on like this(provided, you wish to solve the sudoku !).
But BEFORE THIS, you need to change the values of all the arrays accordingly.It doesn't needs an explanation I guess on why/how to change.
You need to do this after the scanning part also.
We have the easy level solver ready.

Now, this is the most basic step I explained above.There are more than a dozen of techniques present to solve the higher level sudoku's.I will be explaining one of these to help you get through the moderate level sudoku.

This technique can be called as "hidden singles".In this, as the name indicates, we search for the fields(r/c/box) where an number is just limited to only one cell.An example will explain it more clearly.
row[3][4]=1 -> 3th row can contain 4.
But in 3rd row, only for one cell, 4th bit has set, rest all are having it unset.So, obviously that cell ought to have 4.Clear enough !
Similarly, we check for each column and box.And after filling out the cells, run the possibility checker and again the whole procedure or you can also jump to possibility checker after all the fields of a particular kind and.. THIS IS IT for the moderate level.Here's an example of how we perform this operation with the rows:

                              Hidden singles for the rows

Similar to this, you can refer the other techniques and code them, and build a FULL SUDOKU SOLVER of your own (sounds great !,I know)

k then..adiĆ³s to all !
Any queries are welcomed :)

No comments: