Solving Picross using quantum annealing and Ising machines¶
This sample code explains how to solve Picross $^{*1}$, a puzzle game, using quantum annealing and Ising machines, and implements it using Amplify. This notebook consists of the following sections:
 1. Rules and solution outline
 1.1. Rules
 1.2. Solution outline
 1.3. Terms and pattern expressions
 1.3.1. Firstblack, LastBlack
 1.3.2. State of the squares
 1.3.3. Matrix representation of coloring
 2. Formulating the Picross solution
 3. Implementing Picross solution
 Advanced: Tuning
*1: Picross is a registered trademark of Nintendo Co., Ltd.
1. Rules and solution outline¶
1.1. Rules¶
Picross is a puzzle where the purpose is to complete a picture by filling a grid of squares either in black or white, based on the clues given as numbers to the left of each row and above each column.
For example, if the clue says 5
, it means that five consecutive squares in that row or
column must be filled in black; if the clue says more than one number, such as 1 1 1
, it
means that a total of three squares must be filled in black with one or more white spaces in between.
Also, 1 3
indicates that one square and three consecutive squares are to be filled in
black
with one or more blank spaces in between. Note that the order of numbers in each clue is important,
and
1 3
and 3 1
suggest different patterns one another.
Below is an example of a completed Picross according to the clues.
1.2. Solution outline¶
A Picross is complete when the entire domain, consisting of a grid of squares, is filled in either black or white so that both the top and left clues are satisfied at the same time.
If a given Picross is completed so that only the left clue is satisfied, there is no one fixed way to color it. For example, the following different patterns are possible
They only satisfy the left clue, and we call such a blackwhite pattern "Pattern 0" hereafter.
Similarly, let Pattern 1 be a blackwhite pattern that only satisfies the top hint.
If the color of each square in Pattern 0 matches that of Pattern 1, then both the top and left clues are satisfied at the same time, and the Picross puzzle is completed.
Therefore, to solve the puzzle, the following conditions must be satisfied:

Condition (i): Pattern 0 and Pattern 1 match,

Condition (ii): Each of the vertical columns and horizontal rows fulfills the corresponding clue.
1.3. Terms and pattern expressions¶
1.3.1. Firstblack, LastBlack¶
Let us take a sequence from a Picross puzzle as follows.
Now we define FirstBlack and LastBlack for the segment with consecutive black squares as follows.

FirstBlack square in the segment is a black square where the previous square if it exists, is filled in white. (orange box in the figure below)

LastBlack square in the segment is a black square where the next square is filled in white if it exists. (green box in the figure below)
Using these terms, Condition (ii) introduced in the previous section can be seen as the following constraints, focusing on the part of the transition from one previous square to the next.

(iia) Each square is always filled either in black or white.

(iib) The square after a white one is either white or FirstBlack square.

(iic) The square before the white one is white or LastBlack square.

(iid) The square following a black square other than LastBlack is also black one.
By properly imposing the above constraints, Picross can be completed using Ising and quantum annealing machines.
1.3.2. State of the squares¶
Now each square is simply represented as either white or black, but we define more detailed states to allow for the formulation of constraints.
 Define the state of a black square by what number of black square it is.
For example, if the clue is given as2 3
, the state of each black square is defined as follows:
 Define the state of a white square by the number of black squares that have appeared so far.
For example, if the clue is given as2 3
, the state of each white square is defined as follows:
 Integrate the defined states for white and black squares in order of appearance.
For example, if the clues are given as2 3
, the state of each square is defined as follows
Defining the state of each square in this way, and denoting the $i$th clue in each Picross sequence
as
$h_i$, we can write the total number of states $W$ as $W=1+\sum_i (h_i + 1)$. For example, in the
above
picross sequence with 2 3
given as a hint, $h_1=2, h_2=3$ and we get $W=8$ as the total
number of states.
1.3.3. Matrix representation of coloring¶
For example, suppose the following coloring is attempted for a Picross sequence with hints
2 3
.
In order to systematically represent this coloring, the following method can be considered.
 The colors of the $i$th square can be represented in the following table.
Table 1: Color of the $i$th square in the sequence (W: white and B: black).
$i$th  1  2  3  4  5  6  7  8  9  10 

Color  W  W  B  B  W  W  B  B  B  W 
 Using a binary variable matrix, we can also represent the color and state of square $i$.
Table 2: Color and state of the square $i$ (W: white and B: black).
$i$th  1  2  3  4  5  6  7  8  9  10 

W (State ①)  1  1  0  0  0  0  0  0  0  0 
B (State ②)  0  0  1  0  0  0  0  0  0  0 
B (State ③)  0  0  0  1  0  0  0  0  0  0 
W (State ④)  0  0  0  0  1  1  0  0  0  0 
B (State ⑤)  0  0  0  0  0  0  1  0  0  0 
B (State ⑥)  0  0  0  0  0  0  0  1  0  0 
B (State ⑦)  0  0  0  0  0  0  0  0  1  0 
W (State ⑧)  0  0  0  0  0  0  0  0  0  1 
As shown above, for a given coloring pattern, the color and state of a Picross sequence can be represented by a matrix.
2. Formulating the Picross solution¶
Here, we formulate the specific conditions necessary for the Picross solution described in Section 1. The constants and variables that appear in the formulation are as follows (including the constants and variables already introduced):
Constants
 $V$ : the number of vertical squares in the Picross matrix
 $H$ : the number of horizontal squares in the Picross matrix
 $N$ : the number of squares in a sequence
 $h_i$ : the $i$th clue for a sequence
 $W$ : the number of states ($= 1 + \sum_i (h_i+1)$)
 $s_i$ : the state $i$ ($i \in \{1, \dots, W\}$)
 $S_{\rm{white}}, S_{\rm{black}}$ : set of white states and set of black states ($s_i$ always belongs to either $S_{\rm{white}}$ or $S_{\rm{black}}$)
Variables

$q^{(m)}_{i,j} \in \{0, 1\} \quad (i \in \{1, \dots, V\})$ $\quad (j \in \{1, \dots, H\})$
Color of the square in the $i$th row and $j$th column (see Table 1). $q^{(0)}$ indicates Pattern 0 satisfying only the left hint, and $q^{(1)}$ indicates Pattern 1 satisfying only the top hint. For instance, if the square in row $i$ and column $j$ is black, $q_{i,j}=1$; if it is white, $q_{i,j}=0$.

$p_{i,j} \in \{0, 1\} \quad (i \in \{1, \dots, N\}) \quad (j \in \{1, \dots, W\})$
State of square $i$ (see Table 2). If the state of the square $i$ is $j$, $p_{i,j}=1$, otherwise $p_{i,j}=0$.
Based on these constants and variables, we will formulate each constraint introduced in Section 1.
2.1. Initial value constraints¶
To solve a Picross, we search for various states for each row and column. In other words, during the search, a binary variable matrix (e.g., Table 2) corresponding to the different states is evaluated for each Picross sequence.
In the above Picross sequence example given the 2 3
clue, the number of possible states
is
$W=1 + \sum_i (h_i+1)=8$, and the leftmost square ($i=1$) must take one of the following states:
 state ① (when the first square of the sequence starts with white), or
 State ② (when the sequence starts with FirstBlack, and there is no state ① with white)
The first square ($i=1$) of the sequence cannot be in state ③ or ④.
Similarly, the second square from the left ($i=2$) can take the states ①, ②, and ③, as shown in the figure below. Conversely, it will never take a larger state.
In this way, the binary variable matrix can be zeropadded to account for states that the square $i$ can never take. For example, the Picross sequence above can be zeropadded as follows:
Table 3: Color and state of square $i$ after zeropadding (W: white, B: black).
$i$th  1  2  3  4  5  6  7  8  9  10 

W (State ①)  0  0  0  0  0  0  
B (State ②)  0  0  0  0  0  
B (State ③)  0  0  0  0  0  
W (State ④)  0  0  0  0  0  
B (State ⑤)  0  0  0  0  0  
B (State ⑥)  0  0  0  0  0  
B (State ⑦)  0  0  0  0  0  
W (State ⑧)  0  0  0  0  0  0 
In this way, we can restrict the way the Picross sequence takes states, thereby limiting the scope of the search in the solution method. We call this constraint an initial value constraint, which is realized by zeropadding the binary variable matrix representing the states of the squares. The formulation of the initial value constraint can be implemented as follows, by using the variable $p_{i,j}$, which represents the state of the square $i$ of a Picross sequence.
$$ \left\{ \begin{align*} &\begin{split} &p_{i, j} = 0 \quad (j > i+1) \end{split}\\ &\begin{split} &p_{i, j} = 0 \quad (Wj > Ni+1) \end{split}\\ \end{align*} \right\}, $$
where $i \in \{1, ... , N\}, j \in \{1, ... , W\}$. As an exercise, see if you can constrain the initial values if $N = 5$ and $W=8$ as in Table 3.
2.2. Transition constraints¶
The transition constraints have already been introduced in 1.3.1. FirstBlack, LastBlack as (iia) to (iid). In this section, we formulate this transition constraint. We will use the following Picross sequence example described above:
Using the state of each square, the conditions (iia) to (iid) for the transition from one previous square to the next, already introduced, can be described in more detail as follows.

(iia') Each square takes one state.

(iib') If the $i$th square is in the state $j$ and the state $j$ is white, then the $i+1$th square is in the state $j$ (white) or the state $j+1$ (FirstBlack).
Example: If the $i$th square is in the state ④ (white), then the $i+1$th square is in the state ④ (white) or the state ⑤ (FirstBlack).

(iic') If the $i$th square is in the state $j$ and the state $j$ is white, the $i1$th square is in the state $j$ (white) or the state $j1$ (LastBlack).
Example: If the $i$th square is in the state ④ (white), then the $i1$th square is in the state ④ (white) or the state ③ (LastBlack).

(iid') If the $i$th square is in the state $j$ (black) ($\neq$ LastBlack), the $i+1$th square is in the state $j+1$ (black).
Example: If the $i$th square is in the state ⑤ (black), the $i+1$th square is in the state ⑥ (black).
Corresponding to these transition constraints, the following holds for $i \in \{1, ... , N\}$:

(iia') $\quad \sum_j p_{i,j}=1$

(iib') $\quad p_{i, j} \land (1p_{i+1, j}) = p_{i+1, j+1} \quad (\forall j \neq W, s_j \in S_{\rm{white}})$

(iic') $\quad p_{i, j} \land (1p_{i1, j}) = p_{i1, j1} \quad (\forall j \neq 1, s_j \in S_{\rm{white}})$

(iid') $\quad p_{i, j} = p_{i+1, j+1} \quad (\forall j, \{s_j, s_{j+1}\} \subset S_{\rm{black}})$
2.3. Matching constraints¶
In 1.2. Outline of Picross Solution Method, we have introduced the following condition.
 Condition (i): Pattern 0 and Pattern 1 match.
This can be stated more rigorously as follows:

For any Picross matrix square $i,j$, the $(i,j)$ square of Pattern 0 and the $(i,j)$ square of Pattern 1 are both black, or both white. To formulate this, we have for $i \in \{1, ... , V\}, j \in \{1, ... , H\}$,

(i') $\quad q^{(0)}_{i,j} = q^{(1)}_{i,j}$
as the matching constraints.
2.4. Constraints linking color and state¶
In the transition constraints, we defined constraints for a single Picross sequence. In the actual Picross, there are $V$ rows and $H$ columns, so we need to formulate for $H+V$ sequences. Therefore, we add a superscript to the variables to have two pieces of information: whether it is based on a top or left hint, and what number Picross sequence it points to. Specifically, the superscript is $(a,b)$, where $a$ indicates a left hint when $a$ is $0$ and a top hint when $a$ is $1$. Also, $b$ indicates what number of the Picross sequence it is from the top or left.
Using these notations, we can formulate constraints on the relationship between $q^{(m)}_{i,j}$ (the color of the square at position $i, j$, Pattern $m$) and $p_{i,k}^{(a,b)}$ (the state $k$ of square $i$) in a Picross sequence $(a,b)$ as follows.
 Constraint (iii) $$ \begin{align*} \sum_{k s^{(0, j)}_k \in S^{(0, j)}_{\rm{black}}} p^{(0, j)}_{i, k} = q^{(0)}_{i,j} \end{align*} $$
$$ \begin{align*} \sum_{k s^{(1, i)}_k \in S^{(1, i)}_{\rm{black}}} p^{(1, i)}_{j, k} = q^{(1)}_{i,j} \end{align*} $$
Here, $i \in \{1, ... , H\}, j \in \{1, ... , V\}$.
3. Implementing Picross solution¶
Now, based on the constraints we have formulated so far, let us implement the Picross solution method using Amplify.
3.1. Picross matrix plotting function¶
First, we define the function plot_solution
to plot the Picross matrix (and the
solution).
import matplotlib.pyplot as plt
import numpy as np
def plot_solution(v_hints, h_hints, solution=np.zeros((0, 0))):
if solution.shape[0] == len(v_hints) and solution.shape[1] == len(h_hints):
solution = solution
else:
solution = np.zeros((len(h_hints), len(v_hints)))
_, ax = plt.subplots()
ax.tick_params(
which="both",
top=True,
bottom=False,
labeltop=True,
labelbottom=False,
length=0,
)
ax.tick_params(axis="x")
ax.imshow(solution, cmap="Greys", aspect="equal")
# Major tick
ax.set_xticks(np.arange(len(h_hints)))
ax.set_yticks(np.arange(len(v_hints)))
# Minor tick
ax.set_xticks(np.arange(0.5, len(h_hints), 1), minor=True)
ax.set_yticks(np.arange(0.5, len(v_hints), 1), minor=True)
# Label for the major ticks
ax.set_xticklabels(["\n".join(map(str, hint)) for hint in h_hints])
ax.set_yticklabels([" ".join(map(str, hint)) for hint in v_hints])
ax.set_xlim([0.5, len(h_hints)  0.5])
ax.set_ylim([len(v_hints)  0.5, 0.5])
ax.set_title(f"{len(h_hints)} x {len(v_hints)}", fontsize=20, pad=20)
# Grid based on the minor ticks
ax.grid(which="minor", color="#aaaaaa", linestyle="", linewidth=1)
return plt.show()
Also, using plot_solution
, let us create and draw a Picross problem introduced in 1.1. Picross rules.
Now the groundwork for the Picross solution implementation is ready.
# Describe the left and top hints using list.
# Left hints
left_hints = [[5], [1], [5], [1], [5]]
# Top hints
top_hints = [[3, 1], [1, 1, 1], [1, 1, 1], [1, 1, 1], [1, 3]]
# Vertical and horizontal sizes of the Picross matrix
v_len, h_len = len(left_hints), len(top_hints)
# Plot the Picross problem defined above
plot_solution(left_hints, top_hints, np.zeros((v_len, h_len)))
3.2. Implementation of constraint equations¶
3.2.1. Decision variables¶
Next, we define the required decision variables using Amplify's VariableGenerator
.
Define a twodimensional array q
representing the colors of the squares, each of which
is
located at $i,j$, in the Picross matrix. As in $q^{(m)}_{i,j}$ introduced in Picross
solution
formulation, we define an array with left and top hints. The values 0 and 1 correspond to white
and
black, respectively.
from amplify import VariableGenerator
gen = VariableGenerator()
# Color of square (i,j) on the Picross matrix based on the left hints
q_from_left_hints = gen.array("Binary", shape=(v_len, h_len))
# Color of square (i,j) on the Picross matrix based on the top hints
q_from_top_hints = gen.array("Binary", shape=(h_len, v_len))
In addition, for each Picross sequence, we define a twodimensional array p
, which is
("number of squares" x "number of states"). Each square is associated with one state. As in
$p_{i,k}^{(a,b)}$ described in 2.4. Constraints linking color and state, we define
arrays with left hints left_hints
and top hints top_hints
, respectively.
# Create a variable for each of the left and top clues
# Twodimensional array of "number of squares" and "number of states"
p_from_left_hints = [
gen.array("Binary", shape=(h_len, sum(hint) + len(hint) + 1)) for hint in left_hints
]
p_from_top_hints = [
gen.array("Binary", shape=(v_len, sum(hint) + len(hint) + 1)) for hint in top_hints
]
3.2.2. Implementation  initial value constraints¶
As described in 2.1. Initial Value Constraints, the zeropadding of the binary variable matrix is implemented as follows.
$$ \left\{ \begin{align*} &\begin{split} &p_{i, j} = 0 \quad (j > i+1) \end{split}\\ &\begin{split} &p_{i, j} = 0 \quad (Wj > Ni+1) \end{split}\\ \end{align*} \right. $$
from amplify import PolyArray
def assign_init_values(p: PolyArray):
n = p.shape[0]
for i in range(n):
# Initial value constraints: zeropadding in states that each square cannot take.
p[i, i + 2 :] = 0
p[i  1, : i  2] = 0
3.2.3. Implementation  transition constraints¶
Transition constraints are already introduced in 2.2. Transition Constraints, and they consist of four constraints in total. These will be implemented one by one below.
(iia')¶
Each square takes one state.
$$ \quad \sum_j p_{i,j}=1 $$
This condition can be implemented with the one_hot
function. By setting the
axis
parameter, you can create a constraint object about the sum along that axis. In this
case, we set axis=1
since $i$ corresponds to axis=0
and $j$ corresponds to
axis=1
.
from amplify import one_hot
def make_state_constraint(p: PolyArray):
return one_hot(p, axis=1)
(iib')¶
If the $i$th square is in the state $j$ and the state $j$ takes white, then the $i+1$th square is in the state $j$ (white) or the state $j+1$ (FirstBlack).
$$ \quad p_{i, j} \land (1p_{i+1, j}) = p_{i+1, j+1} \quad (\forall j \neq W, s_j \in S_{\rm{white}}) $$
We implement this constraint using Amplify's penalty function. First, the lefthand side of the above equation is transferred to the righthand side and both sides are squared. The logical conjunction $\land$ can be converted to multiplication. This righthand side can be implemented as the penalty $P_b$ for this constraint:
$$ \quad P_b = \left[ p_{i, j} (1p_{i+1, j})  p_{i+1, j+1}\right]^2 \quad (\forall j \neq W, s_j \in S_{\rm{white}}). $$
We see that only set of $(p_{i,j}, p_{i+1,j}, p_{i+1,j+1})$ yielding $P_b=0$ satisfies this constraint.
Expanding the above equation, we obtain:
$$ P_b = p_{i,j}p_{i+1,j}  2p_{i,j}p_{i+1,j+1} + 2\:{\color{red} p_{i,j}} \:p_{i+1,j}p_{i+1,j+1} + p_{i,j} + p_{i+1,j+1} \quad (\forall j \neq W, s_j \in S_{\rm{white}}). $$
Here, the above equation is treated as a penalty, and for a set of $(p_{i,j}, p_{i+1,j}, p_{i+1,j+1})$ that yields $P_b \neq 0$, $P_b$ does not need to be calculated exactly as long as the resulting $P_b \neq 0$. Based on this idea, we can omit the term in redcolored font in the above equation, and avoid the use of thirdorder terms that require the introduction of auxiliary variables.
Finally, $P_b$ in the case of $$j\neq W$$ is,
$$ P_b = p_{i,j}p_{i+1,j}  2p_{i,j}p_{i+1,j+1} + 2p_{i+1,j}p_{i+1,j+1} + p_{i,j} + p_{i+1,j+1} \quad (\forall j \neq W, s_j \in S_{\rm{white}}) $$
Also, if $j=W$, the above equation is reduced to:
$$ P_b = p_{i,j}p_{i+1,j} + p_{i,j} \quad (j=W, s_j \in S_{\rm{white}}) $$
These two equations are implemented as a penalty function with respect to the white squares (to make $P_b$ take a value as close to 0 as possible) as follows.
from amplify import Constraint, ConstraintList
# Function to generate indices of the white state from the hint
def get_white_indices(hint: list[int]):
indices = {0}
cursor = 0
for h in hint:
indices.add(cursor + 1 + h)
cursor += 1 + h
return indices
def make_white_constraint_forward(p: PolyArray, hint: list[int]):
white_constraints = ConstraintList()
# Keep the indices of the white state
s_white_indices = get_white_indices(hint)
# Transition constraint (iib'): if the ith square is in the state j and the state j takes white, then the (i+1)th square is in the state j (white) or the state (j+1) (FirstBlack).
n = p.shape[0]
w = p.shape[1]
for i in range(n  1):
for j in s_white_indices:
c = c = (
p[i, j] * p[i + 1, j] + p[i, j]
if j == w  1
else (
p[i, j] * p[i + 1, j]
 2 * p[i, j] * p[i + 1, j + 1]
+ 2 * p[i + 1, j] * p[i + 1, j + 1]
+ p[i, j]
+ p[i + 1, j + 1]
)
)
white_constraints += Constraint(c, eq=0, penalty=c)
return white_constraints
(iic')¶
If the $i$th square is in the state $j$ and the state $j$ is white, the $i1$th square is in the state $j$ (white) or the state $j1$ (LastBlack).
$$ \quad p_{i, j} \land (1p_{i1, j}) = p_{i1, j1} \quad (\forall j \neq 1, s_j \in S_{\rm{white}}) $$
This transition constraint is also implemented by expanding the expression in the same way as (iib') above and using Amplify's penalty function.
Therefore, the penalty $P_c$ of this transition constraint is:
$$ P_c = p_{i,j}p_{i1,j}  2p_{i,j}p_{i1,j1} + 2p_{i1,j}p_{i1,j1} + p_{i,j} + p_{i1,j1} \quad (\forall j \neq 1, s_j \in S_{\rm{white}}) $$
$$ P_c = p_{i,j}p_{i1,j} + p_{i,j} \quad (j=1, s_j \in S_{\rm{white}}) $$
def make_white_constraint_backward(p: PolyArray, hint: list[int]):
last_black_constraints = ConstraintList()
# Keep the indices of the white state
s_white_indices = get_white_indices(hint)
# Transition constraints (iic'): if the ith square is in the state j and the state j is white, the (i1)th square is in the state j (white) or the state j1 (LastBlack).
n = p.shape[0]
for i in range(1, n):
for j in s_white_indices:
c = (
p[i, j] * p[i  1, j] + p[i, j]
if j == 0
else (
p[i, j] * p[i  1, j]
 2 * p[i, j] * p[i  1, j  1]
+ 2 * p[i  1, j] * p[i  1, j  1]
+ p[i, j]
+ p[i  1, j  1]
)
)
last_black_constraints += Constraint(c, eq=0, penalty=c)
return last_black_constraints
(iid')¶
If the $i$th square is in the state $j$ (black) ($\neq$ LastBlack), the $i+1$th square is in the state $j+1$ (black).
$$ \quad p_{i, j} = p_{i+1, j+1} \quad (\forall j, \{s_j, s_{j+1}\} \subset S_{\rm{black}}) $$
# Function to generate indices of the black state from the hint
def get_black_indices(hint: list[int]):
indices = set([])
cursor = 0
for h in hint:
indices = set(range(cursor + 1, cursor + 1 + h))
cursor += h + 1
return indices
def assign_black_forward(p: PolyArray, hint: list[int]):
# Keep the indices of the black state
s_black_indices = get_black_indices(hint)
# Keep the indices of the black state
n = p.shape[0]
w = p.shape[1]
for i in range(n  2, 1, 1):
for j in range(w  2, 1, 1):
if j in s_black_indices and j + 1 in s_black_indices:
p[i, j] = p[i + 1, j + 1]
3.2.4. Implementation  matching constraints¶
The matching constraints introduced in 2.3. Matching constraints for Pattern 0 based on the left hint and Pattern 1 based on the above hint, are implemented as follows:
$$ \quad q^{(0)}_{i,j}  q^{(1)}_{i,j} = 0. $$
from amplify import equal_to
def equal_constraints(q_left: PolyArray, q_top: PolyArray, v_len, h_len):
constraints = ConstraintList()
for y in range(v_len):
for x in range(h_len):
# Matching constraints for "Pattern 0" and "Pattern 1".
constraints += equal_to(q_left[y, x]  q_top[x, y], 0)
return constraints
3.2.5. Implementation  Constraints linking color and state¶
2.4. Constraints linking color and state are expressed by the following equations:
 Constraints (iii) $$ \begin{align*} \sum_{k s^{(0, j)}_k \in S^{(0, j)}_{\rm{black}}} p^{(0, j)}_{i, k} = q^{(0)}_{i,j} \end{align*} $$
$$ \begin{align*} \sum_{k s^{(1, i)}_k \in S^{(1, i)}_{\rm{black}}} p^{(1, i)}_{j, k} = q^{(1)}_{i,j} \end{align*} $$
Here, in terms of implementation, the smaller the number of variables are, the faster the solution can be obtained by annealing. In Picross, if the size of the Picross matrix is large enough, the number of white states is considered to be substantially greater than the number of black states. To reduce the number of variables to be referenced, the following equations are used. (synonymous with the above equation).
 Constraints (iii') $$ \begin{align*} \sum_{k s^{(0, j)}_k \in S^{(0, j)}_{\rm{white}}} p^{(0, j)}_{i, k} = 1q^{(0)}_{i,j} \end{align*} $$
$$ \begin{align*} \sum_{k s^{(1, i)}_k \in S^{(1, i)}_{\rm{white}}} p^{(1, i)}_{j, k} = 1q^{(1)}_{i,j} \end{align*} $$
The sum over $k$ is obtained by using the sum
function of Amplify.
There are several ways to use the sum
function, but here the first argument is a set of
indices and the second argument is a lambda expression, and the results of executing the lambda
expression
for each element of the set are added up.
For more information on the sum
function, see Reference.
from amplify import sum as amplify_sum
def assign_state_color_link(q: PolyArray, p: PolyArray, hint: list[int]):
for j in range(q.shape[0]):
# Keep the indices of the white state
s_white_indices = get_white_indices(hint)
# (iii') Constraints linking color and state
q[j] = 1  amplify_sum(s_white_indices, lambda k: p[j, k])
3.3. Client configuration¶
Now, we create a client for the combinatorial optimization solver (Fixstars Amplify Annealing Engine).
from amplify import FixstarsClient
from datetime import timedelta
client = FixstarsClient()
client.parameters.timeout = timedelta(seconds=1) # Timeout: 1 sec
# client.token = "Please enter your Amplify API Token"
3.4. Running the Picross solver¶
First, after reflecting the type of constraint that fixes the value of the variable, the constraints implemented above are added together.
def fix_variables(
q_list: list[PolyArray], p_list: list[PolyArray], hint_list: list[list[int]]
):
for q, p, hint in zip(q_list, p_list, hint_list):
# Initial value constraints
assign_init_values(p)
# Transition constraints: (iid')
assign_black_forward(p, hint)
# Constraints linking color and state: (iii')
assign_state_color_link(q, p, hint)
fix_variables(q_from_left_hints, p_from_left_hints, left_hints)
fix_variables(q_from_top_hints, p_from_top_hints, top_hints)
# Transition constraints: (iia'), (iib'), (iic')
def make_transition_constraints(p_list: list[PolyArray], hint_list: list[list[int]]):
state_constraints = ConstraintList()
white_constraints = ConstraintList()
last_black_constraints = ConstraintList()
for p, hint in zip(p_list, hint_list):
state_constraints += make_state_constraint(p)
white_constraints += make_white_constraint_forward(p, hint)
last_black_constraints += make_white_constraint_backward(p, hint)
return state_constraints + white_constraints + last_black_constraints
left_constraints = make_transition_constraints(p_from_left_hints, left_hints)
top_constraints = make_transition_constraints(p_from_top_hints, top_hints)
# Matching constraints
eq_constraints = equal_constraints(q_from_left_hints, q_from_top_hints, v_len, h_len)
# Add up all constraints constructed above
constraints = left_constraints + top_constraints + eq_constraints * 2
In this addition for constraints
, only eq_constraints
is multiplied by two
for
the following reasons.
Each of left_constraints
and top_constraints
considers transition
constraints
(iia'), (iib'), and (iic'). This means that the transition constraints (iia'), (iib'), and
(iic')
are added together twice, once for Pattern 0 based on the left hint and once for
Pattern 1 based on the top hint.
On the other hand, the matching constraints implemented in eq_constraints
do not need to
be
added twice, since they assume that the elements inferred from the left hint and the top hint are
equal.
Therefore, we can assume that the intensity of the constraints is (approximately) half that of the
transition constraints (iia'), (iib'), and (iic').
Therefore, by adding double weights to the matching constraints and adjusting the intensities of these constraints, it is considered that the formulation is solvable by Ising and quantum annealing machines.
The solver is executed using the constraint constraints
constructed up to this point.
If the formulation consists only of constraints, as in this case, you can pass the constraint object
directly to the solve
function without building the model.
from amplify import solve
# Create an Amplify solver with the previously instantiated client
result = solve(constraints, client)
if len(result.solutions) == 0:
raise RuntimeError("No solution was found")
values = result.best.values
solution = q_from_left_hints.decode(values)
plot_solution(left_hints, top_hints, solution)
Advanced: Tuning for high performance¶
To make larger problems solvable, the number of variables must be reduced. In the solution methods mentioned above, 3.2.2. Implementation  initial value constraints and 3.2.3. Inplementation  transition constraints (iid'), and 3.2.4. Implementation  matching constraints reduced the number of variables to be searched by preassigning variables.
The matching constraints are implemented using equal_to
. Here we consider further
reducing
the number of variables by resolving the constraint expressions of some elements in the matching
constraints by assignment.
For a larger scale problem, the below 15x15 picross puzzle is used.
# Describe the left and top hints using list.
left_hints = [
[],
[5],
[1, 1],
[5, 1],
[1, 1, 1],
[1, 1, 5],
[1, 2, 1],
[9, 1],
[1, 1, 1, 1],
[5, 1, 1, 1],
[1, 1, 1, 2],
[1, 1, 5],
[1, 2],
[5],
[],
]
top_hints = [
[],
[5],
[2, 1],
[5, 1, 1],
[2, 1, 1, 1],
[1, 1, 1, 5],
[1, 1, 1, 1],
[1, 9],
[1, 2, 1],
[5, 1, 1],
[1, 1, 1],
[1, 5],
[1, 1],
[5],
[],
]
v_len, h_len = len(left_hints), len(top_hints)
plot_solution(left_hints, top_hints, np.zeros((v_len, h_len)))
Define variables similar to the 5x5 problem (see 3.2.1. Decision variables).
gen = VariableGenerator()
# Color of square (i,j) on the Picross matrix based on the left hints
q_from_left_hints = gen.array("Binary", shape=(v_len, h_len))
# Color of square (i,j) on the Picross matrix based on the top hints
q_from_top_hints = gen.array("Binary", shape=(h_len, v_len))
# Create a variable for each of the left and top clues
# Twodimensional array of "number of squares" and "number of states"
p_from_left_hints = [
gen.array("Binary", shape=(h_len, sum(hint) + len(hint) + 1)) for hint in left_hints
]
p_from_top_hints = [
gen.array("Binary", shape=(v_len, sum(hint) + len(hint) + 1)) for hint in top_hints
]
For the defined variables, the initial value constraints, transition constraints (iid'), and constraints to link color and state (iii') are applied, and assignments are performed to the variables.
# Picross sequences based on the left hints
for q, p, hint in zip(q_from_left_hints, p_from_left_hints, left_hints):
# Initial value constraints
assign_init_values(p)
# Transition constraints: (iid')
assign_black_forward(p, hint)
# Constraints linking color and state: (iii')
assign_state_color_link(q, p, hint)
# Picross sequences based on the top hints
for q, p, hint in zip(q_from_top_hints, p_from_top_hints, top_hints):
# Initial value constraints
assign_init_values(p)
# Transition constraints: (iid')
assign_black_forward(p, hint)
# Constraints linking color and state: (iii')
assign_state_color_link(q, p, hint)
To reduce the number of variables and constraints,
3.2.4. Implementation  matching constraints, the constraint expression
$q^{(0)}_{i,j}  q^{(1)}_{i,j}=0$ can be realized by substitution instead of using
equal_to
.
That is, if the matching constraint equation $q^{(0)}_{i,j}  q^{(1)}_{i,j}=0$ is satisfied, then the $(i,j)$component of Pattern 0 based on the left hint may be $q^{(1)}_{i,j}$ instead of $q^{(0)}_{i,j}$ (and vice versa) This is the case. By doing so, we see that we can reduce the number of variables corresponding to the $(i,j)$components of the matrix based on the left and above hints from two to one.
Note that the matching constraint equation $q^{(0)}_{i,j}  q^{(1)}_{i,j}$ does not necessarily have
only
two terms, since the initial value constraint, the transition constraint (iid'), and the assignment
(assign_*
) by the constraint connecting the mass color and state (iii') are already
implemented above. Note that $q^{(0)}_{i,j}  q^{(1)}_{i,j}$ does not necessarily have only two terms.
Therefore, we first detect matching constraints with two or less terms, and only for matching
constraints
with two or less terms, store pairs of polynomials that are equationally connected to variables to be
assigned in substitute_dicts
, and also match q_from_left_hints
and
q_from_top_hints
to reduce the number of variables. match, reducing the number of
variables.
This requires breaking Poly
into terms, which can be accomplished by writing
l = [t for t in q_diff]
in list comprehension notation.
Each element of l
has the form tuple[tuple, float]
, where the first element
is a
tuple containing multiple Poly
and the second element represents its coefficient.
To give a concrete example, for the Poly
f = q_0 q_1  q_0 + q_1  1
, we
have
l = [((Poly(q_0), Poly(q_1)), 1.0), ((Poly(q_0),)), 1.0), ((), 1.0)]
. The first tuple
[((Poly q_0), Poly(q_1)), 1.0), ((Poly(q_0),), 1.0), ((Poly(q_1),), 1.0), ((), 1.0)]
means
that the product of q_0
and q_1
with coefficient 1. The same is true for the
remaining terms.
from amplify import Poly
# Dictionary which stores the ids of the lefthand side variable as keys and the righthand side variables as values in the assignment
substitute_dicts: dict[int, Poly] = {}
for x in range(h_len):
for y in range(v_len):
q_diff = q_from_left_hints[y, x]  q_from_top_hints[x, y]
terms: list[tuple[tuple, float]] = [t for t in q_diff]
# Focus on only the terms with one or two terms
if len(terms) > 2 or len(terms) == 0:
continue
# When there is only one term, since q_diff is linear, the constraint has the form of Poly == 0
if len(terms) == 1:
q_diff = 0
continue
# When there are two terms, then the constraint form is either Poly == number or Poly == Poly
tp_i, coef_i = terms[0] # The content of tp_i must always be Poly
tp_j, coef_j = terms[1] # The content of tp_j is either Poly of a number
r = coef_j / coef_i
substitute_dicts[tp_i[0].id] = r * tp_j[0] # r == 1 or 1
# Assign tp_i[0] in q_from_left_hints or q_from_top_hints to tp_j[0] in the other
if tp_i[0].as_variable() in q_from_left_hints[y, x].variables:
q_from_left_hints[y, x] = r * q_from_top_hints[x, y]
else:
q_from_top_hints[x, y] = r * q_from_left_hints[y, x]
break
Next, reflect the contents of substitute_dicts
(pairs of polynomials that are
equationally
related to the variable to be assigned) to p_from_left_hints
and
p_from_top_hints
.
def substitute_according_to_dicts(p: PolyArray, d: dict[Poly, dict[Poly, int]]):
for j in range(p.shape[0]):
for k in range(p.shape[1]):
if p[j, k].is_number():
continue
if p[j, k].id in d:
p[j, k] = d[p[j, k].id]
for p in p_from_left_hints:
substitute_according_to_dicts(p, substitute_dicts)
for p in p_from_top_hints:
substitute_according_to_dicts(p, substitute_dicts)
After reducing the number of variables as described above, constraints are created as in the previous implementation of the formulation.
# Transition constraints: (iia'), (iib'), (iic')
left_constraints = make_transition_constraints(p_from_left_hints, left_hints)
top_constraints = make_transition_constraints(p_from_top_hints, top_hints)
# Match constraints
eq_constraints = equal_constraints(q_from_left_hints, q_from_top_hints, v_len, h_len)
constraints = left_constraints + top_constraints + eq_constraints * 2
Since the problem size has increased, set a larger timeout for the previously created client and then reconstruct the solver.
client.parameters.timeout = timedelta(seconds=10) # Timeout: 10 sec
The solver is run by passing the constraint object constraints
and client object
client
to the solve
function.
result = solve(constraints, client)
if len(result.solutions) == 0:
raise RuntimeError("No solution was found")
values = result.best.values
Pass the solution values
to the evaluate
method of the variable array
q_from_left_hints
and assign the result to the variable array solution
. The
plot_solution
function is then used to plot the solution.
solution = q_from_left_hints.evaluate(values)
plot_solution(left_hints, top_hints, solution)