# Sudoku

Here's how to implement a Sudoku solver in Keelung!

## Describing the Problem & the Solution

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.

## Checking the problem 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`

.

## Checking the solution matrix

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.

Last updated