Wednesday, March 14, 2012

Sudoku Verification.


Write a function to validate a SuDoKu board.


Approach:
Assign primes numbers {2,3,5,7,11,13,17,19,23} to numbers 1 to 9.
1 => 2
2 => 3
3 => 5
4 => 7
5 => 11
6 => 13
7 => 17
8 => 19
9 => 23


Multiple all the prime numbers, it would be "223092870".
Now verify each row of sudoku by calculating its hash and making sure its equal to "223092870".
Similarly calc hash for each col and then each grid, if any of the hash fails then return false otherwise in the end return true.


Sample code input/output:
3 2 9 6 5 7 8 4 1
7 4 5 8 3 1 2 9 6
6 1 8 2 4 9 3 7 5
1 9 3 4 6 8 5 2 7
2 7 6 1 9 5 4 8 3
8 5 4 3 7 1 6 1 9
4 3 2 7 1 6 9 5 8
5 8 7 9 2 3 1 6 4
9 6 1 5 8 4 7 3 2


Hash value: 223092870
Row verification failed!
is sudoku verified? false




3 2 9 6 5 7 8 4 1
7 4 5 8 3 1 2 9 6
6 1 8 2 4 9 3 7 5
1 9 3 4 6 8 5 2 7
2 7 6 1 9 5 4 8 3
8 5 4 3 7 2 6 1 9
4 3 2 7 1 6 9 5 8
5 8 7 9 2 3 1 6 4
9 6 1 5 8 4 7 3 2


Hash value: 223092870
Grid Hash: 223092870
Grid Hash: 223092870
Grid Hash: 223092870
Grid Hash: 223092870
Grid Hash: 223092870
Grid Hash: 223092870
Grid Hash: 223092870
Grid Hash: 223092870
Grid Hash: 223092870
is sudoku verified? true

No comments:

Post a Comment