Sudoku¶

This tutorial explains how to solve a Sudoku puzzle using an Ising machine with Amplify.

About Sudoku¶

Sudoku is a puzzle that fills a $9\times9$ grid with the numbers from $1$ to $9$ accordingly to the following rules:

• Place one number from $1$ to $9$ to each cell.
• No identical numbers may be placed in each row and column, and in each of the nine $3\times3$ subgrids.

First, we are given initial clues, where 17 or more numbers are placed (it has been proven that no solution can be found with 16 or less clues). The game is played by determining the numbers that go into the unfilled cells accordingly to the rules above. When the game's difficulty level is low, it is relatively easy to determine which numbers to place. As the difficulty of the game increases, and it requires some experience to solve the puzzles.

Reference: https://en.wikipedia.org/wiki/Sudoku

Various algorithms have been devised to solve Sudoku puzzles using computers, such as depth-first search, probabilistic methods, constraint satisfaction problems, exact cover problems, etc. By following these algorithms, Sudoku puzzles can be solved mechanically.

In this tutorial, we will show how to solve Sudoku puzzles using an Ising machine. Formulating the problem from the above Sudoku rules, we define the corresponding function, where finding its minimum value is equivalent to solving the Sudoku puzzle. In the case of Sudoku, only constraint conditions are needed, and no cost function appears.

Now let us take a look at how the code for solving a Sudoku puzzle is implemented using Amplify.

Formulation of constraints¶

How to express Sudoku constraints on annealing machines¶

First, we consider how to express the constraint conditions that correspond to the Sudoku rules, using binary variables whose values are $\{0, 1\}$.

The rules to be expressed are the followings:

1. Each row contains the digits from $1$ to $9$ without overlap.
2. Each column contains the digits $1$ to $9$ without overlap.
3. Each $3\times3$ subgrid contains the digits $1$ to $9$ without overlap.

Without imposing the above rules 1-3, $9$ possible numbers can be placed in each of $9\times9=81$ cells. We thus consider assigning $9$ binary variables to each of the cells, so that $9\times9\times9=729$ variables are prepared in total. One way to describe this situation is that we stack $9$ layers of $9\times9=81$ grids, so that each layer corresponds to the numbers from $1$ to $9$, respectively. For the $9\times9=81$ grid in each layer, we let $i$ and $j$ be the indices expressing the rows and columns, respectively, with $i,j=0,\cdots,8$, corresponding to $1, \cdots, 9$ th row and column. We also assign the layer index $k=0,\dots,8$, so that the layer specified by the index corresponds to numbers $1,\cdots,9$, respectively.

From this observation, we can express the binary variables by $q_{i,j,k}$, where $i,j,k=0,\cdots,8$ correspond to the indices for rows, columns, and layers, respectively. For example, $q_{2,4,6}=1$ means that number $7$ is placed in the cell at the 3rd row and 5th column, and $q_{2,4,6}=0$ means that $7$ is not to be placed here.

Using these variables, the constraints 1-3 can be written as the following one-hot constraints, respectively.

$$ \left\{ \begin{align} &\begin{split} (a) \quad &\sum_{j=0}^8 q_{i,j,k}=1 \end{split}\\ &\begin{split} (b) \quad &\sum_{i=0}^8 q_{i,j,k}=1 \end{split}\\ &\begin{split} (c) \quad &\sum_{i,j\in 3\times3\,\text{subgrid}}q_{i,j,k}=1 \end{split}\\ &\begin{split} (d) \quad &\sum_{k=0}^8 q_{i,j,k}=1 \end{split} \end{align} \right. $$

The constraints $(a)$, $(b)$ and $(c)$ correspond to rules 1, 2 and 3, respectively. The $(d)$ constraint corresponds to the basic condition that each cell can only contain one number.

Initialization¶

In Sudoku, clues are given as an initial placement with 17 or more numbers already placed. Here we use the following initial placement which is considered a difficult problem. In the following notation, the cells with no filled numbers are marked with $0$.

Creating Constraints¶

Define variables and reflect initial placement¶

First, we prepare variables using gen_symbols and BinaryPoly provided by Amplify.

This gives a three-dimensional array with $9^3=729$ variables. Each of 9, 9, 9 represents the number of elements in the rows, columns, and number layers, and their indices are i, j, and k, respectively. Each element can be accessed with q[i][j][k]. For example, the 9 variables for row number $0$ and column number $0$ can be displayed as follows:

From the initial placement stored in initial, we can narrow down the unknown variables that can be determined accordingly to the rules of Sudoku. For example, the cell indicated by i=1 and j=5 already has a number $8$ (initial[1][5]=8), so the variable in the layer k=7 corresponding to the number $8$ can be specified by q[1][5][7]=1. In this specific case, we can place some numbers accordingly to the rules in the following way.

Rules 1 and 2 allow us to further determine the values of the variables q[i][5][7]=0 ($i\neq1$), q[1][j][7]=0 ($j\neq5$), and q[i][5][7]=0 ($j\neq5$), since the row and column containing the cell indicated by i=1 and j=5 in the layer k=7 cannot contain the same number as $8$. This corresponds to imposing the constraints $(a)$ and $(b)$.

Also, by rule 3, the $3\times3$ subgrid, which this number $8$ above belongs to, cannot contain $8$ any more, so in $(i,j)\in\{(0,3),(0,4),(0,5),(1,3),(1,4),(2,3),(2,4),(2,5)\}$, we can let q[i ][j][7]=0. We can imposed the constraint $(c)$ in this manner.

Furthermore, we impose the constraint $(d)$ to place only one of the numbers in a cell where the number is fixed. In the above example, we have q[1][5][k]=0 ($k\neq7$). By performing similar operations for all the cells given from the initial layout, we can narrow down the required variables so that we can perform the calculations with fewer number of variables.

We have now prepared the initial settings. As an example, if you display the 9 variables with the row number $0$ and the column number $0$, you will see that the second element is fixed as $1$, that is, the number $2$ is assigned to this cell.

Similarly, if we display the 9 variables with the row number $0$ and column number $1$, we can see that the numbers $1,2,3,4,5,6$ are not candidates.

Setting constraints¶

Next, we show how the constraint parts are implemented. The one-hot constraint in $(a)$-$(d)$ can be expressed using Amplify's equal_to function.

We start by defining the constraint condition corresponding to $(a)$ that each row of cannot contain the same number. Since the sum of the variables for all columns specified by row i and layer k is given by $\sum_{j=0}^{8}q_{i,j,k}$, the constraint can be obtained by setting this sum to $1$ as follows.

Similarly, the constraint $(b)$ that each column has cannot contain the same number and $(d)$ that only one number can be placed in a given cell can be expressed as follows:

Finally, we express the constraint $(c)$ that each $3\times3$ subgrid cannot contain the same number. We take the sum of the variables in each $3\times3$ subgrid for all layers and impose the one-hot constraint as follows:

We have now obtained all the constraints, and we can add all these constraints together to obtain the total constraint object.

This completes the formulation of the Sudoku problem. If the Ising machine can find the combination of variables that satisfies all the constraints, this allows us to determine the numbers to be placed for all the cells, giving the solution for Sudoku.

We formulate the constraint constraints as a logical model class by giving it to BinaryQuadraticModel, and we can get the result by giving it to the Solve.solver method of the previously set solver.

The result of the execution is stored in values. By giving the variable array q and values to the decode_solution function, the variables are evaluated with the result values. Then, by searching for k such that q[i][j][k] = 1 for all i and j, we can get the number k + 1 as the solution for the indicated cell.

Finally, the print_sudoku function is used to output the solution.

Generalization of Sudoku¶

So far we have dealt with a $9 \times 9$ grid with $3 \times 3$ subgrids, but the Ising machine can easily handle Sudoku puzzles with extended problem sizes, such as $16 \times 16$ and $25 \times 25$. We let the number of cells in a Sudoku puzzle be $N\times N,\,(N\in\mathbb{Z})$ and the corresponding subgrids be in the form of $n\times n$ (where $N=n^2,\,(n\in\mathbb{Z})$). For example, a basic $9\times9$ Sudoku would have $N=9$ and $n=3$.

We generalize the previous code using $N$ and $n$ and solve the $16\times16$ mass Sudoku as an example.