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.
When using transducers, it's important to remember that a big part of their purpose is to minimize the amount of work done: in this case, look at each element at most once if at all possible, and that's it. So I would think that reformatting the entire input or even parts of it, e.g. transpose and gather boxes (or invoking transduce multiple times) - kind of defeats that intent?
With that in mind, fastest is to pry each element from the current/next row as they come in (e.g. using 'cat), then try to fail it by checking it against previously gathered elements for the same row/column/box. Adding to each element's collections can be done with index arithmetic and propagated through the accumulator.
For efficiency, each pipeline step does a single task (the pipeline itself is a single function), usually a single line expression, to prevent any possibly unneeded work to be done. In a fail-fast implementation, we can invoke 'reduced and end processing on the spot.
I have also experienced slower times using transduce for small problems, than the 3-line golfing version - I think that is probably due to transducer machinery setup time compared to a small input size like a sudoku grid. What would be interesting for benchmarking is to do something similar with rows of thousands of elements, maybe a 1000 side square of Queens or Knight Tour in chess?
Or how about this? Let's rewrite the input in such a way that looking at a grid value takes x amount of time - like perhaps having the thread sleep for a while. Then an efficient transducer should shine through: