A Combinatorial Optimization Approach to Solving Picross Puzzles¶

This sample code explains how to solve Picross $^{*1}$, a puzzle game, using combinatorial optimization solver, and implements it using Amplify.

${*1}$: Picross is a registered trademark of Nintendo Co., Ltd. (Japan Trademark Registration No. 4069661).

Picross Rules¶

Picross is a puzzle game where you complete a picture by coloring squares on a rectangular board. The hints are given as numbers to the left of each row and above each column. In this sample code, we handle the puzzle below.

The hint numbers written to the left of each row indicate how many consecutive squares should be colored black in that row. The hint numbers above each column indicate how many consecutive squares should be colored black in that column.

For example, a hint 5 means to color five consecutive squares black in that row or column. A hint 1 3 means to color one square black, leave at least one square empty, and then color three consecutive squares black.

The solution to this sample puzzle forms the letter "A", as shown below.

Picross Formulation¶

Formulation Strategy¶

Solving Picross with a combinatorial optimization solver, such as Amplify AE, requires a specific formulation of the problem. We use the following strategy:

1. Use a set of binary variables $q^\text{row}$ to represent board layouts that satisfy the row (left-side) hints.
2. Use another set of binary variables $q^\text{col}$ to represent board layouts that satisfy the column (top) hints.
3. Add constraints to ensure that $q^\text{row}$ and $q^\text{col}$ represent the same board layout.

The two diagrams below show examples of a board that satisfies only the row hints and a board that satisfies only the column hints.

Next, we explain how to represent the coloring of the board using binary variables.

Representation of Boards Satisfying Row Hints¶

We represent a board that satisfies the row hints by assigning numbers to certain squares, as shown in the diagram below.

In each row, numbers $0, 1, \ldots$ are written from left to right on the leftmost square of each consecutive block of black squares.

When performing this operation, the following rules must be satisfied for each row.

If the hints for a row are $h_0, h_1, \ldots, h_{n-1}$:

• The numbers $0$ to $n-1$ must each appear exactly once in that row.
• For $0 \leq k < n-1$, the square with the number $k+1$ must be at least $h_k + 1$ squares to the right of the square with the number $k$.
• The square with the number $n-1$ cannot be to the right of the $h_{n-1}$-th square from the right edge.

For example, if the hints for a row are 2 1 2, these properties are illustrated below.

Setting Up Row Variables¶

We use binary variables to represent the numbers written in each square. For each square, we prepare several binary variables equal to the number of hints for that row. If the $i$-th variable is 1, it means the number $i$ is written in that square. For example, in the second row of the figure above, there are two hints. The number 0 is in the second square from the left, and the number 1 is in the fourth square. This can be represented using a $5 \times 2$ table of binary variables:

Square \ Number	Number 0	Number 1
1st square from left	0	0
2nd square from left	1	0
3rd square from left	0	0
4th square from left	0	1
5th square from left	0	0

In this table, both variables for the first square are 0, which means no number is written in this square. For the second square, the variable representing "Number 0" is 1, which means zero is written there.

In this way, we set up (number of columns) $\times$ (number of hints for that row) binary variables for each row. We'll use $q^\text{row}_{i,j,k}$ for the binary variable that represents whether number $k$ is written in the square at row $i$, column $j$.

Constraints¶

Next, we need to add constraints to $q^\text{row}_{i,j,k}$ to ensure it correctly represents a board that satisfies the row hints.

First, a square can have at most one number written on it, or none at all; it cannot have two. This means that for each square, at most one of its corresponding binary variables (one for each hint) can be 1. In equation form:

$$ \sum_k q^\text{row}_{i,j,k} \leq 1 $$

Next, we add conditions for each row to ensure it satisfies its hints. Assume the hints for a row are $h_0, h_1, \ldots, h_{n-1}$. As mentioned earlier, the following three rules must hold:

• The numbers $0$ to $n-1$ must each appear exactly once in that row.
• For $0 \leq k < n-1$, the square with the number $k+1$ must be at least $h_k + 1$ squares to the right of the square with the number $k$.
• The square with the number $n-1$ cannot be to the right of the $h_{n-1}$-th square from the right edge.

First, "The numbers $0$ to $n-1$ must each appear exactly once in that row." In our binary variable table, this means the sum of each "Number" column must be 1. For each $k$ from $0$ to $n-1$, only one variable representing $k$ being written in that row should be 1. In equation form:

$$ \sum_j q^\text{row}_{i,j,k} = 1 $$

Second, "For $0 \leq k < n-1$, the square with number $k+1$ must be at least $h_k + 1$ squares to the right of the square with number $k$." This is a constraint for all but the last hint number. We can rephrase this as: "We cannot have number $k$ in column $j_1$ AND number $k+1$ in column $j_2$ if $j_2 - j_1 < h_k+1$." In equation form:

$$ q^\text{row}_{i,j_1,k} q^\text{row}_{i, j_2, k+1} = 0 \quad (j_2 - j_1 < h_k + 1,\ \text{$h_k$ is the $k$-th hint for row $i$}) $$

Finally, "The square with number $n-1$ cannot be to the right of the $h_{n-1}$-th square from the right edge." This is a constraint for the last hint number in each row. In equation form:

$$ q^\text{row}_{i, j, n-1} = 0 \quad (j > (\text{number of columns}) - h_{n-1}) $$

Conversely, if $q^\text{row}$ satisfies all these conditions, it will be a valid representation of a board satisfying the row hints.

Representation of Boards Satisfying Column Hints¶

We can apply the same approach for the column hints. We define binary variables $q^\text{col}$, this time setting up (number of rows) $\times$ (number of hints) variables for each column.

A board satisfying the column hints would look like this for the example given earlier:

We use $q^\text{col}_{j, i, k}$ for the variable that represents the number $k$ being written in the square at row $i$, column $j$. Note that the column index $j$ comes first.

We can add the same types of constraints for $q^\text{col}$ to ensure it represents a valid board for the column hints. Simply refer to the previous section, swapping "row" for "column" and "left" for "top."

Constraint for Matching Boards¶

Now we need to add constraints to ensure that the two sets of binary variables, $q^\text{row}$ and $q^\text{col}$, describe the same colored board.

First, let's consider how to reconstruct the board (which squares are colored) from the $q^\text{row}$ values.

For example, if a row's hints are 2 1 2, a square in that row is colored black if it meets any of the following conditions:

• Number 0 is written in that square or one square to its left.
• Number 1 is written in that square.
• Number 2 is written in that square or one square to its left.

Because of the constraints we have already set on $q^\text{row}$, these conditions cannot overlap. Therefore, if the hint for row $i$ is 2 1 2, the square at row $i$, column $j$ is black if the following expression is 1, and white if it is 0.

$$ q^\text{row}_{i, j, 0} + q^\text{row}_{i, j-1, 0} + q^\text{row}_{i, j, 1} + q^\text{row}_{i, j, 0} + q^\text{row}_{i, j-1, 0} $$

Even with different hint numbers, we can find a similar linear expression of $q^\text{row}$ for each square's color. In general, if the hints for row $i$ are $h_0, h_1, \ldots$, the color of the square at row $i$, column $j$ ($C^\text{row}_{i,j}$) is black if the value is 1, and white if 0.

$$ C^\text{row}_{i,j} = \displaystyle\sum_k \sum_{r=j-h_k+1}^j q^\text{row}_{i,r,k} $$

We can do the same for $q^\text{col}$. If the hints for column $j$ are $H_0, H_1, \ldots$, the color of the square at row $i$, column $j$ is:

$$ C^\text{col}_{i,j} = \displaystyle\sum_k \sum_{r=i-H_k+1}^j q^\text{col}_{j,r,k} $$

Therefore, to make the boards match, we simply need to add a constraint that $C^\text{row}{i,j} = C^\text{col}_{i,j}$ for every square $(i, j)$.

$$ \sum_k \sum_{r=j-h_k+1}^j q^\text{row}_{i,r,k} = \sum_k \sum_{r=i-H_k+1}^j q^\text{col}_{j,r,k} $$

This constraint ensures that the board reconstructed from $q^\text{row}$ and the board from $q^\text{col}$ are the same.

With this, the Picross formulation is complete.

Solving Picross¶

Let's implement the solution for Picross using Amplify based on the formulation we just discussed.

Picross Visualization Function¶

Before we begin the implementation, let's define a helper function, plot_picross(), to display the Picross board and its solution.

We also use the plot_picross function we just defined to create and display the same puzzle problem introduced in the Picross Rules section.

Definition of Decision Variables¶

Now, let's move on to the implementation. First, we create the decision variables using Amplify's VariableGenerator.

For the $q^\text{row}$ variables, which create the board satisfying row hints, we create a 2D binary variable array q_row for each row, with shape (number of columns) $\times$ (number of hints). q_row[i][j, k] represents whether number k is written in the square at row i, column j.

Similarly, for the $q^\text{col}$ variables, which represent the column hints, we create a 2D binary variable array q_col for each column, with shape (number of rows) $\times$ (number of hints). q_col[j][i, k] represents whether number k is written in the square at row i, column j.

For example, the variables $q^\text{row}_{i=1,j,k}$ for the second row from the top (i=1) can be displayed as follows:

Implementation of Constraints for q_row¶

We add constraints to q_row to ensure it represents a board that satisfies the row hints. We need to create constraints for the following:

• A square has at most one number written on it (or it might have no number).

And, if a row's hints are $h_0, \ldots, h_{n-1}$:

• The numbers $0$ through $n-1$ each appear exactly once in that row.
• For $0 \leq k < n-1$, the square with number $k+1$ is at least $h_k + 1$ squares to the right of the square with number $k$.
• The square with number $n-1$ is not to the right of the $h_{n-1}$-th square from the right edge.

First, let's add the last constraint: "The square with number $n-1$ must not be to the right of the $h_{n-1}$-th square from the right edge."

$$ q^\text{row}_{i, j, n-1} = 0 \quad (j > (\text{number of columns}) - h_{n-1}) $$

This can be implemented in code by assigning a value to the variable array. This assignment should be done before building any other objective functions or constraints.

Let's display the values of q_row for the fourth row (i=3). We can see that number 0 cannot be written in any column except the leftmost one (j=0).

Next, let's create the first constraint: "A square has at most one number written on it."

$$ \sum_k q^\text{row}_{i,j,k} \leq 1 $$

This sums over $k$ (which is axis=1 in the 2D array q_row), so we specify axis=1 in the less_equal function.

The second constraint: "If a row's hints are $h_0, \ldots, h_{n-1}$, the numbers $0$ through $n-1$ must each appear exactly once in that row."

$$ \sum_j q^\text{row}_{i,j,k} = 1 $$

This sums over $j$ (which is axis=0 in the 2D array q_row[i]), so we specify axis=0 in the one_hot function.

And the third constraint: "If a row's hints are $h_0, \ldots, h_{n-1}$, then for $0 \leq k < n-1$, the square with number $k+1$ must be at least $h_k + 1$ squares to the right of the square with number $k$."

$$ q^\text{row}_{i,j_1,k} q^\text{row}_{i, j_2, k+1} = 0 \quad (j_2 - j_1 < h_k + 1) $$

First, for a fixed $i$, $j_1$, and $k$, we create a 1D array of all $q^\text{row}_{i,j_1,k} q^\text{row}_{i, j_2, k+1}$ products for all $j_2$ that satisfy $j_2 - j_1 < h_k + 1$. Then, we use the equal_to function to create constraints that all elements of this array must be 0. To create constraints for each element of the array at once, we specify an empty tuple for the axis parameter.

With that, we have created the constraints for q_row. Let's group them into one constraint list.

Implementation of Constraints for q_col¶

Now we add the same constraints for q_col, just as we did for q_row.

Implementation of Consistency Constraints¶

Next, we implement the constraint to make the boards represented by q_row and q_col match. First, let's create an array that represents the color of each square as reconstructed from q_row. The color of the square at row $i$, column $j$ (where $h_0, h_1, \ldots$ are the hints for row $i$) is:

$$ \sum_k \sum_{r=j-h_k+1}^j q^\text{row}_{i,r,k} $$

Similarly, let's create an array representing the color of each square as reconstructed from q_col.

We use the equal_to function to create constraints that the colors from q_row and q_col match for every square. To create constraints for every element of the arrays at once, we specify an empty tuple for the axis parameter.

Construction of the Combinatorial Optimization Model¶

Now, let's combine all the constraints we have created into a single combinatorial optimization model.

3.3. Client Configuration¶

We create a client for the Fixstars Amplify Annealing Engine (AE).

Let's solve the problem using Amplify AE.

By assigning the solution values into the field_from_q_row array, we can reconstruct the board colors from the solution.

Finally, let's display the result.

Whis this, we have successfully solved the Picross problem.