Sudoku
Last updated
Last updated
Here's how to implement a solver in Keelung!
The solver itself is a circuit that accepts the problem matrix as public input and the solution matrix as private input. Both matrices are 9x9 matrices of Field
numbers.
The solver itself is a circuit that accepts the problem matrix as public input and the solution matrix as private input. Both matrices are 9x9 matrices of Field
numbers.
The solution matrix must contain all the numbers in the problem matrix. We use the digit 0
to indicate empty cells in the problem matrix. So, if a digit is not 0
, it should be equal to the corresponding digit in the solution matrix.
We want to make sure that all the numbers in the problem matrix are in the range 0
to 9
.
The helper function from0to9
checks if a number is in the range 0
to 9
.
In order for a Sudoku solution to be valid, the following conditions must be met:
Each row must contain the digits 1-9 without repetition.
2. Each column must contain the digits 1-9 without repetition.
3. Each of the 9 3x3 sub-boxes of the grid must contain the digits 1-9 without repetition.
Let's declare a helper function valid
that checks if a list of 9 Field
numbers satisfies the Sudoku constraints. Instead of checking that the list contains the digits 1
to 9
without repetition, we check that the sum of the list is 45
and the product of the list is 362880
.
Using this helper function, we can check if the solution matrix is valid.