Nonogram

A nonogram is a puzzle in which you complete a picture by painting some of the cells of a grid black. To the left of each row and above each column, the lengths of the blocks of consecutive black cells in that row (column) are listed from left to right (from top to bottom). For example, “2 5 2” means that blocks of 2, 5 and 2 black cells appear in this order, with at least one white cell between consecutive blocks. “0” means that the row (column) has no black cells. The goal is to decide which cells to paint so that all the clues are satisfied.

Here we solve the following $15\times 15$ puzzle ($H=15$ rows and $W=15$ columns):

A 15×15 nonogram puzzle

Start Positions of the Blocks

Consider a single row (or column) of length $n$ whose clue is $(L_0, L_1, \ldots, L_{m-1})$. Positions are counted from $0$ at the left (top) end. If block $k$ starts at position $s_k$, the blocks match the clue exactly when

\[\begin{aligned} s_0\geq 0,\qquad s_{k+1}\geq s_k+L_k+1\ \ (0\leq k\leq m-2),\qquad s_{m-1}+L_{m-1}\leq n \end{aligned}\]

The middle inequality says that block $k+1$ starts only after at least one white cell following block $k$.

If all the blocks are packed to the left, block $k$ starts at position

\[e_k=\sum_{l=0}^{k-1}(L_l+1)\]

and

\[d=n-\sum_{l=0}^{m-1}L_l-(m-1)\]

cells are left over on the right. We call $d$ the free space. Each block starts somewhere between positions $e_k$ and $e_k+d$.

Variables: Has the Block Started by Position $j$?

Instead of representing the start position $s_k$ directly, we use the following binary variables for each block $k$ and $0\leq p\leq d-1$:

\[a_{k,p}=1 \iff s_k\leq e_k+p\]

In other words, $a_{k,p}=1$ means that “block $k$ has started at or before position $e_k+p$”. As $p$ increases, $a_{k,p}$ takes the form $0,\ldots,0,1,\ldots,1$, and the number of $0$s, $s_k-e_k$, is the shift of the block from its left-packed position. Moving the boundary between the $0$s and the $1$s by one (flipping one variable) moves the block by one cell. Representing an integer (here, a start position) by a sequence of binary variables, each telling whether the integer is at most a given value, is called the order encoding.

For example, a row with $n=10$ and clue $(3, 1)$ has $e_0=0$, $e_1=4$ and $d=10-4-1=5$. The following painting has $s_0=2$ and $s_1=8$:

j   0 1 2 3 4 5 6 7 8 9
    . . # # # . . . # .

The variables then take the following values:

$p$ 0 1 2 3 4
$a_{0,p}$ (started by position $0+p$) 0 0 1 1 1
$a_{1,p}$ (started by position $4+p$) 0 0 0 0 1

Since $a$ can only represent start positions from $e_k$ to $e_k+d$, a block never runs off the end of the row.

Constraints

For each row (column), we impose the following two kinds of constraints.

  • Once a block has started, it has also started at every later position:
\[\begin{aligned} a_{k,p}\leq a_{k,p+1} && (0\leq k\leq m-1,\ 0\leq p\leq d-2) \end{aligned}\]
  • Block $k+1$ starts after block $k$:
\[\begin{aligned} a_{k+1,p}\leq a_{k,p} && (0\leq k\leq m-2,\ 0\leq p\leq d-1) \end{aligned}\]

The second one is a rewrite of the condition $s_{k+1}\geq s_k+L_k+1$. Since $e_{k+1}=e_k+L_k+1$, the condition is the same as $s_{k+1}-e_{k+1}\geq s_k-e_k$, that is, “the shift of block $k+1$ is at least the shift of block $k$”. The shift is the number of $0$s, so this is equivalent to $a_{k+1,p}\leq a_{k,p}$ for every $p$. In the example above, $a_{1,p}\leq a_{0,p}$ indeed holds for every $p$.

Next, we express the color of each position with the variables. Extending “block $k$ has started by position $j$” to every position $j$, let

\[A_k(j)=\begin{cases} 0 & (j<e_k)\\ a_{k,\,j-e_k} & (e_k\leq j<e_k+d)\\ 1 & (j\geq e_k+d) \end{cases}\]

Block $k$ covers position $j$ exactly when it has started by position $j$ but not by position $j-L_k$, so the color of position $j$ ($1$ for black, $0$ for white) is

\[B(j)=\sum_{k=0}^{m-1}\bigl(A_k(j)-A_k(j-L_k)\bigr)\]

If the two kinds of constraints above are satisfied, the blocks do not overlap, so $B(j)$ is $0$ or $1$. At position $8$ in the example, $A_1(8)-A_1(7)=a_{1,4}-a_{1,3}=1-0=1$, so the position is black.

Finally, we introduce a binary variable $x_{i,j}$ for the color of cell $(i,j)$. Writing $R_{i,j}$ for $B(j)$ computed for row $i$ and $C_{i,j}$ for $B(i)$ computed for column $j$, we require that the colors seen from the row and from the column are both equal to $x_{i,j}$:

\[\begin{aligned} R_{i,j}=x_{i,j},\qquad C_{i,j}=x_{i,j} && (0\leq i\leq H-1,\ 0\leq j\leq W-1) \end{aligned}\]

All the constraints are linear equalities and inequalities, and no auxiliary variables are needed.

QUBO++ Program

The following program declares the constraints above as native constraints with qbpp::cons() and solves the puzzle with the Easy Solver:

#include <qbpp/easy_solver.hpp>
#include <qbpp/qbpp.hpp>

#include <iostream>
#include <numeric>
#include <string>
#include <vector>

using Clue = std::vector<int>;

// Clues: lengths of the blocks of black cells in each row (from the top) and
// each column (from the left).
static const std::vector<Clue> ROWS = {
    {}, {1, 1}, {2, 2}, {3, 3}, {13}, {13}, {2, 5, 2}, {2, 5, 2},
    {13}, {6, 6}, {5, 5}, {11}, {9}, {5}, {}};
static const std::vector<Clue> COLS = {
    {}, {10}, {10}, {3, 5}, {2, 5}, {10}, {6, 3}, {5, 3},
    {6, 3}, {10}, {2, 5}, {3, 5}, {10}, {10}, {}};

// Variables a[k][p] of a row (column) of length n.
qbpp::Array<2, qbpp::Var> line_var(const std::string& name, const Clue& clue,
                                   int n) {
  // free space: cells left on the right when packed to the left
  int d = n - std::accumulate(clue.begin(), clue.end(), 0) -
          static_cast<int>(clue.size()) + 1;
  return qbpp::var(name, clue.size(), d);
}

// Expression that is 1 if block k has started by position j.
qbpp::Expr started(const qbpp::Array<2, qbpp::Var>& a, const Clue& clue,
                   int k, int j) {
  // position j minus the leftmost position where block k can start
  int p = j - std::accumulate(clue.begin(), clue.begin() + k, 0) - k;
  if (p < 0) return 0;
  if (p >= static_cast<int>(a.shape(1))) return 1;
  return a[k][p];
}

// Expression that is 1 if position j is black.
qbpp::Expr black(const qbpp::Array<2, qbpp::Var>& a, const Clue& clue, int j) {
  auto e = qbpp::toExpr(0);
  for (int k = 0; k < static_cast<int>(clue.size()); ++k)
    e += started(a, clue, k, j) - started(a, clue, k, j - clue[k]);
  return e;
}

// Constraints on the order of the blocks in one row (column).
qbpp::Expr line_cons(const qbpp::Array<2, qbpp::Var>& a) {
  size_t m = a.shape(0), d = a.shape(1);
  auto g = qbpp::toExpr(0);
  // a block that has started stays started
  for (size_t k = 0; k < m; ++k)
    for (size_t p = 0; p + 1 < d; ++p)
      g += qbpp::cons(a[k][p + 1] - a[k][p] >= 0);
  // block k+1 starts after block k
  for (size_t k = 0; k + 1 < m; ++k)
    for (size_t p = 0; p < d; ++p)
      g += qbpp::cons(a[k][p] - a[k + 1][p] >= 0);
  return g;
}

int main() {
  const int H = static_cast<int>(ROWS.size());
  const int W = static_cast<int>(COLS.size());

  auto x = qbpp::var("x", H, W);
  std::vector<qbpp::Array<2, qbpp::Var>> row, col;
  for (int i = 0; i < H; ++i)
    row.push_back(line_var("r" + std::to_string(i), ROWS[i], W));
  for (int j = 0; j < W; ++j)
    col.push_back(line_var("c" + std::to_string(j), COLS[j], H));

  auto f = qbpp::toExpr(0);
  for (const auto& a : row) f += line_cons(a);
  for (const auto& a : col) f += line_cons(a);
  for (int i = 0; i < H; ++i) {
    for (int j = 0; j < W; ++j) {
      f += qbpp::cons(black(row[i], ROWS[i], j) - x[i][j] == 0);  // color seen from the row
      f += qbpp::cons(black(col[j], COLS[j], i) - x[i][j] == 0);  // color seen from the column
    }
  }

  auto solver = qbpp::EasySolver(f);
  auto sol = solver.search({{"target_energy", 0}});
  for (int i = 0; i < H; ++i) {
    for (int j = 0; j < W; ++j) std::cout << (sol(x[i][j]) ? '#' : '.');
    std::cout << std::endl;
  }
}

The clues are given as a vector of std::vector<int>. A row (column) with clue “0” is the empty vector {}.

  • line_var(name, clue, n) creates the variables $a_{k,p}$ of a row (column) of length n as a 2-dimensional array qbpp::Array<2, qbpp::Var> of shape $(m, d)$. For a row (column) whose clue is empty, $m=0$, so the array has no elements.
  • started(a, clue, k, j) returns $A_k(j)$: 0, 1 or the variable a[k][p], depending on the position, as a qbpp::Expr.
  • black(a, clue, j) returns the expression for the color $B(j)$ of position j.
  • line_cons(a) returns an expression that declares the two kinds of inequality constraints of one row (column) with qbpp::cons(). a.shape(0) and a.shape(1) are $m$ and $d$. A comparison between two variables is written in the form a[k][p + 1] - a[k][p] >= 0 by taking their difference.

qbpp::var("x", H, W) is the array of variables $x_{i,j}$ for the colors of the cells. row[i] holds the variables $a$ of row $i$, and col[j] holds those of column $j$. The final double loop declares, for each cell, the equality constraints that the colors seen from the row and from the column are both equal to x[i][j]. There are 461 variables in total: 236 for $a$ and 225 for $x$.

This puzzle has no objective function to minimize, and the energy becomes $0$ when all the constraints are satisfied. solver.search({{"target_energy", 0}}) stops the search as soon as a solution with energy $0$ is found. Finally, the program prints black cells as # and white cells as ..

Running the program produces the following output, and the face of a cat appears:

...............
.#...........#.
.##.........##.
.###.......###.
.#############.
.#############.
.##..#####..##.
.##..#####..##.
.#############.
.######.######.
.#####...#####.
..###########..
...#########...
.....#####.....
...............

This is the only solution of this puzzle.

Back to top

Page last modified: 2026.10.12.

© 2026 Koji Nakano, Hiroshima University