ノノグラム

ノノグラムは、マス目のいくつかを黒く塗って絵を完成させるパズルで、お絵かきロジックとも呼ばれます。 各行の左と各列の上には、その行（列）にある黒マスの塊の長さが、左から（上から）順に書かれています。 例えば「2 5 2」は、長さ 2、5、2 の黒マスの塊がこの順に並び、塊と塊の間には白マスが 1 個以上あることを表します。 「0」は、その行（列）に黒マスがないことを表します。 すべての手がかりを満たすように、塗るマスを決めます。

ここでは次の $15\times 15$ の問題を解きます（行数 $H=15$、列数 $W=15$）:

15×15 のノノグラムの問題

塊の開始位置

長さ $n$ の 1 本の行（または列）を考え、手がかりを $(L_0, L_1, \ldots, L_{m-1})$ とします。 位置は左端（上端）を $0$ として数えます。 塊 $k$ が位置 $s_k$ から始まるとすると、塊の並びが手がかりに合う条件は

\[\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}\]

です。真ん中の不等式は、塊 $k$ の後に白マスが 1 個以上あってから塊 $k+1$ が始まることを表します。

すべての塊を左に詰めると、塊 $k$ は位置

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

から始まり、右には

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

個のマスが余ります。これを余白と呼びます。 各塊は位置 $e_k$ から $e_k+d$ までのどこかで始まります。

変数: 塊が位置 $j$ までに始まっているか

開始位置 $s_k$ を直接表す代わりに、各塊 $k$ と $0\leq p\leq d-1$ について、次のバイナリ変数を使います:

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

つまり $a_{k,p}=1$ は「塊 $k$ は位置 $e_k+p$ までに始まっている」ことを表します。 $p$ を増やしていくと、$a_{k,p}$ は $0,\ldots,0,1,\ldots,1$ の形になり、$0$ の個数 $s_k-e_k$ が、左に詰めた位置からのずれになります。 $0$ と $1$ の境目を 1 つずらす（変数を 1 個反転する）と、塊が 1 マス動きます。 このように、整数（ここでは開始位置）を「ある値以下か」を表すバイナリ変数の列で表す方法は、順序符号化と呼ばれます。

例えば $n=10$、手がかり $(3, 1)$ の行では、$e_0=0$、$e_1=4$、$d=10-4-1=5$ です。 次の塗り方では $s_0=2$、$s_1=8$ です:

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

このとき変数の値は次のようになります:

$p$ 0 1 2 3 4
$a_{0,p}$（位置 $0+p$ までに始まっている） 0 0 1 1 1
$a_{1,p}$（位置 $4+p$ までに始まっている） 0 0 0 0 1

$a$ で表せる開始位置は $e_k$ から $e_k+d$ までなので、塊が行の端からはみ出すことはありません。

制約

1 本の行（列）について、次の 2 種類の制約を課します。

  • 一度始まった塊は、その先の位置でも「始まっている」:
\[\begin{aligned} a_{k,p}\leq a_{k,p+1} && (0\leq k\leq m-1,\ 0\leq p\leq d-2) \end{aligned}\]
  • 塊 $k+1$ は塊 $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}\]

2 つ目は条件 $s_{k+1}\geq s_k+L_k+1$ を書き直したものです。 $e_{k+1}=e_k+L_k+1$ なので、この条件は $s_{k+1}-e_{k+1}\geq s_k-e_k$、 つまり「塊 $k+1$ のずれは塊 $k$ のずれ以上」と同じです。 ずれは $0$ の個数なので、これは各 $p$ で $a_{k+1,p}\leq a_{k,p}$ が成り立つことと同値です。 上の例でも $a_{1,p}\leq a_{0,p}$ がすべての $p$ で成り立っています。

次に、各位置の色を変数で表します。 「塊 $k$ が位置 $j$ までに始まっている」を、すべての位置 $j$ に広げて

\[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}\]

とします。塊 $k$ が位置 $j$ を覆うのは、塊 $k$ が位置 $j$ までに始まっていて、位置 $j-L_k$ までには始まっていないときなので、 位置 $j$ の色（黒なら $1$、白なら $0$）は

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

と書けます。上の 2 種類の制約を満たせば塊は重ならないので、$B(j)$ は $0$ か $1$ です。 上の例の位置 $8$ では、$A_1(8)-A_1(7)=a_{1,4}-a_{1,3}=1-0=1$ で黒になります。

最後に、マス $(i,j)$ の色を表すバイナリ変数 $x_{i,j}$ を用意します。 行 $i$ について求めた $B(j)$ を $R_{i,j}$、列 $j$ について求めた $B(i)$ を $C_{i,j}$ と書き、 行から見た色と列から見た色がどちらも $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}\]

制約はすべて線形の等式・不等式で、補助変数は必要ありません。

QUBO++ プログラム

以下のプログラムは、上記の制約を ネイティブ制約 qbpp::cons() で宣言し、 Easy Solver でパズルを解きます:

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

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

using Clue = std::vector<int>;

// 手がかり: 各行 (上から) と各列 (左から) の黒マスの塊の長さ。
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}, {}};

// 長さ n の行 (列) の変数 a[k][p]。
qbpp::Array<2, qbpp::Var> line_var(const std::string& name, const Clue& clue,
                                   int n) {
  // 余白: 塊を左に詰めたときに右に余るマスの数
  int d = n - std::accumulate(clue.begin(), clue.end(), 0) -
          static_cast<int>(clue.size()) + 1;
  return qbpp::var(name, clue.size(), d);
}

// 塊 k が位置 j までに始まっていれば 1 になる式。
qbpp::Expr started(const qbpp::Array<2, qbpp::Var>& a, const Clue& clue,
                   int k, int j) {
  // 位置 j と、塊 k が始まれる最も左の位置との差
  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];
}

// 位置 j が黒なら 1 になる式。
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;
}

// 1 本の行 (列) の塊の並びの制約。
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);
  // 始まった塊は、その先でも始まっている
  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);
  // 塊 k+1 は塊 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);  // 行から見た色
      f += qbpp::cons(black(col[j], COLS[j], i) - x[i][j] == 0);  // 列から見た色
    }
  }

  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;
  }
}

手がかりは std::vector<int> のベクトルで与えます。「0」の行（列）は空のベクトル {} です。

  • line_var(name, clue, n) は、長さ n の行（列）の変数 $a_{k,p}$ を、形 $(m, d)$ の 2 次元配列 qbpp::Array<2, qbpp::Var> として作ります。 手がかりが空の行（列）では $m=0$ なので、要素のない配列になります。
  • started(a, clue, k, j) は $A_k(j)$ を返します。位置によって 0、1、変数 a[k][p] のいずれかを qbpp::Expr として返します。
  • black(a, clue, j) は位置 j の色 $B(j)$ を表す式を返します。
  • line_cons(a) は、1 本の行（列）について 2 種類の不等式制約を qbpp::cons() で宣言した式を返します。 a.shape(0) と a.shape(1) が $m$ と $d$ です。 変数どうしの大小は、差を取って a[k][p + 1] - a[k][p] >= 0 の形で書きます。

qbpp::var("x", H, W) はマスの色を表す変数 $x_{i,j}$ の配列です。 row[i] は行 $i$ の変数 $a$、col[j] は列 $j$ の変数 $a$ です。 最後の二重ループで、各マスについて行から見た色と列から見た色がどちらも x[i][j] に等しいという等式制約を宣言します。 変数は $a$ が 236 個、$x$ が 225 個の計 461 個です。

このパズルには最小化したい目的関数がなく、すべての制約を満たすとエネルギーが $0$ になります。 solver.search({{"target_energy", 0}}) で、エネルギー $0$ の解が見つかった時点で探索を打ち切ります。 最後に、黒マスを #、白マスを . で表示します。

実行すると次の出力が得られ、猫の顔が現れます:

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

この問題の解はこの 1 つだけです。

Back to top

Page last modified: 2026.10.12.

© 2026 中野浩嗣, 広島大学