Sunday, July 7, 2013

Verifying A Sudoku Solution

This one may be easy for Sudoku fans. I used to play it so it wasn't difficult to come up with the rules that would define the algorithm. For those who haven't played, Sudoku is a number game where you have a board (usually 9 by 9) divided in 9 sub-grids (blocks 3 by 3). Every cell of the board can contain a number from 1 to 9. The goal is to fill the board with numbers in such a way that numbers are unique column-wise, row-wise and block-wise. The board comes with some numbers filled in. For more information check the Wikipedia page. The above Sudoku game was of order 3, but we may want our problem to be a little less restrictive and accept higher orders too. Thus if it would accept a Sudoku board of order n, the board would have ncolumns and n2 rows; the blocks would be n by n, and we would have to fill in numbers from 1 to n2.

Our algorithm will have at least O(n2) time complexity since we have to check each element on the board. It sounds like we could one table traversal and check each element's validity. But how would you check one element when it depends on other elements that may be on the same row/column/block? We could use a Set array of size nfor columns, another array of same size for rows and a bi-dimensional array of size n for blocks. Thus, while traversing the board we note each element in the associated set or if it is already there then we stop the algorithm since we have an invalid solution.

In code looks like this:

It seems like we could improve the code a little by using some bit patterns instead of sets. We could set a bit for each existing number. For example if we already have 3 and 1 our bit pattern should look like this: 101. We would need some simple bit manipulation logic to check and set a bit. I used longs so that I can allow Sudoku boards of orders up to 8:

Helper initialize method and test data for convenience:

No comments:

Post a Comment