Sudoku Validator
Write a function that validates a finished sudoku board. It should take a vector of vectors. The inner vectors represent rows from the sudoku board. The rows should contain nine integers. If the board is well-played, the function should return true
, otherwise, false
.
(sudoku-valid? [[ 1 5 2 4 8 9 3 7 6 ]
[ 7 3 9 2 5 6 8 4 1 ]
[ 4 6 8 3 7 1 2 9 5 ]
[ 3 8 7 1 2 4 6 5 9 ]
[ 5 9 1 7 6 3 4 2 8 ]
[ 2 4 6 8 9 5 7 1 3 ]
[ 9 1 4 6 3 7 5 8 2 ]
[ 6 2 5 9 4 8 1 3 7 ]
[ 8 7 3 5 1 2 9 6 4 ]]) ;=> true
(sudoku-valid? [[ 1 1 2 4 8 9 3 7 6 ]
[ 7 3 9 2 5 6 8 4 1 ]
[ 4 6 8 3 7 1 2 9 5 ]
[ 3 8 7 1 2 4 6 5 9 ]
[ 5 9 1 7 6 3 4 2 8 ]
[ 2 4 6 8 9 5 7 1 3 ]
[ 9 1 4 6 3 7 5 8 2 ]
[ 6 2 5 9 4 8 1 3 7 ]
[ 8 7 3 5 1 2 9 6 4 ]]) ;=> false
Notes:
- A sudoku puzzle is successfully solved if all rows contain the numbers 1-9, all columns contain 1-9, and the nine 3x3 boxes contain 1-9. See the Wikipedia page for more information.
Thanks to this site for the challenge idea where it is considered Expert level in JavaScript.
@KingCode Yes it is an interesting approach. I use a vector of nine 3-element vectors. Each of these 3-element vectors is used to track the occurrence of a valid integer (that's why there are nine) in a row, column and box (that's why their dimension is 3). This is done in a single pass over the board. I check if the number I read, say
n
, has occurred already in a row, column or box and if it has I terminate the loop. I do that by testing then
th bit on the element of the 3-vector that corresponds to the row (first), column (second) and box (third). If the bit is off I turn it on and continue. If it terminates without error I last check that the every 3-vector is actually[511 511 511]
i.e. every integer 1-9 has been seen for every row, column and box2^0+...+2^8=511
so the last check is not to be removed.