Zenn
🧩

数理最適化でナンプレ（数独）の問題を作成する

2024/12/01に公開
Streamlit
数理最適化
pulp
tech

この記事は数理最適化 Advent Calendar 2024 1日目の記事です。

数理最適化と聞くと、多くの人はコストの最小化やポートフォリオの最適化を思い浮かべるかもしれません。しかし、数理最適化は「最適化」だけではなく、さまざまな用途に使える強力な手法です。今回は、その一例としてナンプレ（数独）を取り上げます。

ナンプレの解法については既に多くの記事[1][2]が存在しますが、この記事ではナンプレの問題作成に踏み込んでいきます。これにより、数理最適化がどのように一見最適化には見えない問題にも応用できるかをお伝えできればと思います。

なお本記事のコードはGitHubで公開しています。また、Streamlit Community Cloud で実際に動かすことができるので、遊んでみてください。

https://opt-number-place.streamlit.app/generate

https://github.com/ohtaman/number_place

数理最適化とは

数理最適化（Mathematical Optimization）とは、「与えられた制約の中で、ある数値を最大化（もしくは最小化）する変数の値をみつけること」を指します。与えられた制約のことを 制約条件 (Constraints)、最大化（もしくは最小化）する数値のことを 目的関数 (Objective Function)、最適化の対象となる変数のことを 意思決定変数（Decision Variables） と呼びます。

項目 説明
目的関数（Objective Function） 最大化または最小化したい対象の数値を定義する関数です。例えば、「コストを最小化する」や「利益を最大化する」といった具合です。
制約条件（Constraints） 解が満たさなければならない条件を定義する部分です。制約条件は、現実世界のリソース制限や物理的な制約を数学的に表現したもので、例えば「使用できる予算は一定以内」といった条件が含まれます。
意思決定変数（Decision Variables） 最適化の対象となる変数であり、目的関数や制約条件に基づいて最適な値が求められます。例えば、製造業であれば「各製品の生産量」が意思決定変数となります。

ナンプレを解いてみる

数理最適化の応用例として、ナンプレ（数独）を解くことを考えてみましょう。ナンプレは、9×9のマスに1から9の数字を埋めていくパズルで、以下のルールを満たさなければなりません：

  1. 各行には1から9の数字がそれぞれ一度だけ入る。
  2. 各列にも1から9の数字がそれぞれ一度だけ入る。
  3. 各3×3のブロックにも1から9の数字がそれぞれ一度だけ入る。
  4. ヒントの数字は変えられない。

このルールを数理最適化の言葉で表現すると、以下のようになります（これを定式化と呼びます）

1. 意思決定変数

意思決定変数として「セル (i, j) に数字 k が入るかどうか」を示す変数 x_{ijk} を導入します。この x_{ijk} は 0 もしくは 1 をとるバイナリ変数で、次のように定義します

  • x_{ijk} = 1 のとき、 セル (i, j) に数字 k が入る
  • x_{ijk} = 0 のとき、 セル (i, j) に数字 k は入らない

ここで、 i,\ j \in \{0,\dots,8\} はセルの位置、k \in \{1,\dots,9\} はセルに入る値を表しています。例えば x_{002} = 1 の時、セル (0, 0) の値は 2 です。

2. 制約条件

次に、この決定変数を使って、ナンプレのルールを制約条件として数学的に表現します。

  1. 各セルに必ず1つの数字が入る。
    各セル (i, j) には、1 から 9 のどれか1つの数字が入らなければなりません。このルールは x_{ijk} を使うと、以下のように書けます。

    \sum_{k=0}^{8} x_{ijk} = 1 \quad \forall i, j

    例えばセル (0, 0) の値が 2 であった場合を考えると、上の左辺は x_{001} + x_{002} + \cdots + x_{009} となりますが、値が 2 なので、 x_{002} = 1 でそれ以外は 0 となるため、上の式が成り立ちます。上の式が成り立っていない場合、x_{00k} が全てゼロ（つまりどの値も入らない）か複数が 1（つまり、1つのセルに2つの値が入る）となり、おかしくなってしまうからです。

  2. 各行には1から9の数字がそれぞれ一度だけ入る。
    各行 i の中で、数字 k が一度だけ現れる必要があります。

    \sum_{j=0}^{8} x_{ijk} = 1 \quad \forall i, k

  3. 各列にも1から9の数字がそれぞれ一度だけ入る。
    同様に、各列 j においても、数字 k が一度だけ現れる必要があります。

    \sum_{i=0}^{8} x_{ijk} = 1 \quad \forall j, k

  4. 各3×3のブロックにも1から9の数字がそれぞれ一度だけ入る。
    すこし式が複雑になりますが、列や行と同様に制約条件を記述できます。

    \sum_{i=a}^{a+2} \sum_{j=b}^{b+2} x_{ijk} = 1 \quad \forall k, \quad a, b \in \{0, 3, 6\}

    ここで a, b はブロックの位置を表しています。

  5. ヒントの数字は変えられない。
    ヒントが与えられているセルについては、その数字が入ります。

    x_{ijk} = 1 \quad (セル (i,j) に数字 k がヒントとして与えられている場合)

3. 目的関数

通常の最適化問題では、最大化もしくは最小化したい対象、つまり目的関数が存在します。しかし、ナンプレの場合には、このような目的関数は特に存在しません。なぜなら、ナンプレの目的は「特定のルールを満たす解を見つけること」であり、その中で最も「良い」解を求めるわけではないからです。求めるべき解はただ1つであり、その条件を満たしていれば良いため、ナンプレの問題設定では目的関数は不要です。

そこで、ナンプレを数理最適化で解く場合は、目的関数が定数であるとみなすことで問題を最適化問題として扱います。具体的には、目的関数に決定変数を含めないようにする[3]ことで、制約条件を満たす解を見つけることに集中することができます。このように目的関数をあえて持たない形式にすることで、ナンプレのような「制約を満たす解を探す」問題にも数理最適化が応用できます。

実装する

定式化が済んだので、さっそく実装してみましょう。ここではPythonライブラリの PuLP を使います。 PuLP は以下のコマンドでインストールできます。

pip install pulp

PuLP では、上記の制約条件をもつ問題は以下のように記述できます。細かい解説は割愛しますが、上述の制約条件が Python コードに反映されているのがみて取れるかと思います。 Streamlit アプリも用意したので、興味のある方はそちらもご覧ください。適当に数字を入れて実行すると、一瞬で解いてくれるのがわかると思います。

https://opt-number-place.streamlit.app/

def solve(hints):
    """
    ナンプレを混合整数計画法で解く

    Args:
        hints (np.ndarray): 9x9のナンプレの初期状態。NaNは空白を表す。

    Returns:
        list: 解の9x9グリッド（解がない場合はNone）。
    """
    # 数理最適化問題の定義
    prob = LpProblem("SolveNumberPlace", LpMinimize)

    # 各セルを表す変数を定義
    # cells[i][j][k] == 1 のとき、セル [i, j] の値が k であることを表す
    cells = LpVariable.dicts("Cell", (range(9), range(9), range(1, 10)), cat=LpBinary)

    # 各セルに1つの値が入る制約
    for i in range(9):
        for j in range(9):
            prob.addConstraint(
                lpSum(cells[i][j][k] for k in range(1, 10)) == 1,
                f"CellValue_{i}_{j}"
            )

    # 各行に1〜9が1回ずつ入る制約
    for i in range(9):
        for k in range(1, 10):
            prob.addConstraint(
                lpSum(cells[i][j][k] for j in range(9)) == 1,
                f"RowValue_{i}_{k}"
            )

    # 各列に1〜9が1回ずつ入る制約
    for j in range(9):
        for k in range(1, 10):
            prob.addConstraint(
                lpSum(cells[i][j][k] for i in range(9)) == 1,
                f"ColumnValue_{j}_{k}"
            )

    # 各3x3ブロックに1〜9が1回ずつ入る制約
    for block_i in range(3):
        for block_j in range(3):
            for k in range(1, 10):
                prob.addConstraint(
                    lpSum(cells[block_i * 3 + di][block_j * 3 + dj][k] for di in range(3) for dj in range(3)) == 1,
                    f"BlockValue_{block_i}_{block_j}_{k}",
                )

    # 初期値（ヒント）を設定
    for i in range(9):
        for j in range(9):
            if not np.isnan(hints[i][j]):  # NaNは空白を表す
                prob.addConstraint(
                    cells[i][j][int(hints[i][j])] == 1,
                    f"HintValue_{i}_{j}"
                )

    # 目的関数を設定（必要ないため定数（0）を設定）
    prob.setObjective(lpSum([]))

    # 解を見つける
    prob.solve()

    # 最適解が得られた場合、解を9x9グリッドで返す
    if LpStatus[prob.status] == "Optimal":
        solution = np.zeros((9, 9))
        for i in range(9):
            for j in range(9):
                for k in range(1, 10):
                    if cells[i][j][k].value() == 1:
                        solution[i, j] = k
        return solution
    else:
        return None  # 解がない場合

与えられた問題が間違っていた場合に、修正を提案する

さて、先ほどのコードでは、問題が間違っていたときには None を返して諦めるようにしていました。しかし、少し工夫することで、 ヒントが間違っていた場合に修正箇所を提案 させることができます。具体的には、 制約条件 と 目的関数 を少し変更します。

  1. 制約条件の変更
    既存のヒントをそのまま使用するのではなく、「ヒントの修正を許容する」形で制約条件を設定します（これを制約条件の緩和と呼びます）。具体的には、ペナルティ変数 z_{ij} を導入し、セル (i, j) のヒントが修正されるかどうかを示すバイナリ変数とします。

    x_{ijk} + z_{ij} = 1 \quad (セル (i,j) に数字 k がヒントとして与えられている場合)

    以前の制約条件 5. と異なり、z_{ij} = 1 であれば、ヒントの与えられているセルについても x_{ijk} = 0 とすることができます。

  2. 目的関数の設定
    z_{ij} を導入すると、ヒントを無視して好き勝手に数字を入れられるようになってしまいます。そこで、ヒントをなるべく修正しないように、目的関数を設定します。具体的には z_{ij}=1 となるセルの数が最小となるようにします。

    \mathrm{minimize}\quad \sum_{i=0}^{8}\sum_{j=0}^{8}z_{ij}

    この目的関数により、最適化アルゴリズムはなるべくヒントを修正せずにナンプレを解くことが目標となります。

コードは以下のように修正されます。

...
    # ペナルティ変数の定義
    # penalty[i][j] == 1 のとき、セル [i, j] の値（ヒント）を修正することを表す
    penalty = LpVariable.dicts("Penalty", (range(9), range(9)), cat=LpBinary)
...

    # 初期値（ヒント）を設定
    for i in range(9):
        for j in range(9):
            if not np.isnan(hints[i][j]):  # NaNは空白を表す
                prob.addConstraint(
                    cells[i][j][int(hints[i][j])] + penalty[i][j] == 1,
                    f"HintValue_{i}_{j}"
                )

    # 目的関数: ペナルティの合計を最小化
    prob += lpSum(penalty[i][j] for i in range(9) for j in range(9))
...

デモもあるので触ってみてください。

https://opt-number-place.streamlit.app/modify

このように、制約条件や目的関数を変更することで、さまざまな状況に対応できるようになります。

数理最適化を使って問題を生成する

では、本題の問題生成に進みましょう。まずはナンプレの問題として成り立つ条件を考えます。例えば、以下の例はどうでしょうか？

alt text

ヒントが一切ない問題です。これは9×9のグリッドがすべて空白であり、いわば「どんな解でも許される」状態です。このような問題は数学的には解を持ちます（実際、前述のプログラムを使えば解を1つ出すことができます）が、良いナンプレの問題とは言えないでしょう。なぜなら解が一意に定まらないからです。複数の異なる解が存在してしまうと、プレイヤーにとっては、どれが正しい解なのか判断がつかなくなってしまいます。論理的に考えて1セルずつ確定していくナンプレの楽しさが失われてしまいそうです。

そこで、本記事では 解が一意に定まる、つまり、適切にヒントが配置されていて論理的な手順で唯一の解にたどり着けること、を生成する問題の条件とします。

解が一意に定まる条件とは？

さて、解が一意に定まる ことを保証しながら問題を生成するにはどうしたら良いでしょうか？
いくつか方法が考えられそうですが、まず完全に埋まった状態のナンプレ（全ての数字が正しく配置された状態）を用意し、それを元に一部のセルの数字を消していく、つまりヒントを削ることで問題を作ろうと思います[4]。

ヒントを削る際には注意が必要です。どのセルを削るかによっては、解が一意でなくなる可能性があるためです。そこで、削った後に「この問題が一意解を持つかどうか」を確認する必要があります。この確認作業を数理最適化を用いて行います。

数理最適化による解の一意性を確認する

問題が一意の解を持つかどうかは、次のようにして問題を再度解くことで検証できます。

  1. ナンプレの解を1つ見つける：
    まず、削ったヒントを持つ状態で問題を解き、一つの解を求めます。

  2. もう一つの異なる解を探す：
    得られた解とは異なる別の解が存在するかどうかを確認します。具体的には、最初に得られた解を禁止する制約を追加し、それでもなお解が見つかるかを調べます。

    最初に得られた解でセル (i, j) に数字 k が入っているとしましょう。その場合、次に解くときには「セル (i, j) に数字 k は入らない」という制約を追加します。全ての (i, j) に対してこの制約を課すことで、最初に得られた解を禁止できます。

最初に得られた解を禁止してもなお解が得られる場合、その問題には複数の解が存在するということです。逆に解が得られなければ、解は唯一であったことがわかります。

コード上では前述の solve(hints) 関数を以下のように修正することで実現できます。

...
    # 解を見つける
    prob.solve()

    if LpStatus[prob.status] != "Optimal":
        return False  # 解が存在しない


    # はじめに見つかった解を禁止する
    # はじめに見つかった解で選択されなかった変数 cells[i][j][k] が少なくとも1つは値 1 を持つ
    prob.addConstraint(
        lpSum(
            cells[i][j][k]
            for i in range(9)
            for j in range(9)
            for k in range(1, 10)
            if cells[i][j][k].value() != 1
        ) >= 1
    )

    prob.solve()

    return LpStatus[prob.status] != "Optimal"  # 別解がなければ一意解

一意解を持つナンプレ問題を生成する

具体的な問題生成の手順をまとめると、次のようになります。

  1. 完全なナンプレを用意する：
    まず、数理最適化を使ってすべてのセルに数字が埋まった状態のナンプレを解きます。この段階では解が一意に定まっています。この解は、前出の solve 関数で簡単に得られます。

    solution = solve(np.full((9, 9), np.nan))

  2. ヒントを削る：
    すべてのセルのうち、いくつかのセルを空白（ヒントなしの状態）にします。この時、削るセルはランダムに選びますが、削った後にその問題が一意解を持つかどうかの確認が必要です。

  3. 一意解かの確認と調整：
    ヒントを削った後、その状態で再度問題を解き、一意解が保たれているかを確認します。複数の解が存在する場合は、そのセルを再度ヒントとして元に戻します。

プロセス 2. と 3. を繰り返しながら決められた数になるまでヒントを削っていくことで、ナンプレの問題を生成することができます。

def generate_problem(solution, num_hints):
    """
    一意解を持つナンプレの問題を生成する

    Args:
        solution (np.ndarray): 完全なナンプレの解。
        num_hints (int): 問題として残すセルの数（難易度調整）。

    Returns:
        np.ndarray: 一意解を持つナンプレの問題。
    """
    hints = solution.copy()
    indices = [(i, j) for i in range(9) for j in range(9)]
    random.shuffle(indices)  # セルの順序をランダムにする

    for i, j in indices:
        # 現在のセルを削除（np.nan に設定）
        temp = hints[i][j]
        hints[i][j] = np.nan

        # 一意解でなければ削除を戻す
        if not has_unique_solution(hints):
            hints[i][j] = temp

        # 残っているヒントの数が指定の数に達したら終了
        if np.sum(~np.isnan(hints)) == num_hints:
            break

    return hints

デモもあるので触ってみてください。

https://opt-number-place.streamlit.app/generate

解に多様性を与える

さて、デモを触っていただくと気づくと思いますが、先ほどのコードでは最終的に得られる解が（ほとんど）いつも同じものになってしまいます[5]。これではプレイヤーもすぐに飽きてしまいますね。これは、はじめに完全な解を得るときにランダムな要素を含めていないためです。そこで、目的関数にランダムな要素を含めることで、ランダムな解が得られるように改修しましょう。

これには色々な方法が考えられますが、ここでは「全ての決定変数にランダムな重みをつけて、重みと変数の積の和が最小となる」ような目的関数を考えました。これで、ランダムに小さい重みが振られた決定変数が 1 となりやすくなるため、ランダムな解が得られます。

...
    # ランダムな目的関数を設定
    prob.setObjective(lpSum([
        cells[i][j][k]*random.random()
        for i in range(9)
        for j in range(9)
        for k in range(1, 10)
    ]))
...

以下のデモを何度か動かしてみると、解が毎回異なることがわかると思います。

https://opt-number-place.streamlit.app/generate_random

条件を指定できるようにする

ここまではプログラムが完全に自動でナンプレの問題を生成していましたが、人が特定の条件を指定して問題を作りたいと思うこともあると思います。たとえば、「特定のセルにはこの数字を入れてほしい」や、「対称性のある問題を作りたい」といった条件です。数理最適化を用いた問題生成においては、制約条件を少し変更するだけでこれらの条件に対応できます。

特定のセルの数字を固定するには、はじめに解を生成する際に、ヒントとして指定すればよさそうです。

    hints = ...  # ヒントの入力を許可する
..
        # solution = solve(np.full((9, 9), np.nan))
        solution = solve(hints)

https://opt-number-place.streamlit.app/generate_with_hints

それ以外の条件にも柔軟に対応できます。例えば対称性を考慮したナンプレの生成を行いたい場合、「対称なセルには同じ数字が入る」という制約を追加すれば大丈夫です[6]。これにより、問題の見た目が美しい対称性を持つナンプレを生成することができます。

数理最適化の強力な点の1つは、制約条件や目的関数の柔軟性です。対称性以外にも、例えば「特定のエリアに特定の数字を配置したい」といった細かい条件も、容易に指定可能です。ぜひ、色々な条件を制約条件や目的関数に落とし込んでみてください。

まとめ

この記事では、数理最適化を使ってナンプレ（数独）の問題を解くだけでなく、問題そのものを生成する方法を紹介しました。目的変数や制約条件を適切に設定することで、ナンプレの解を簡単に得たり、誤ったヒントを修正できること、さらに数理最適化の適用方法を工夫することで解が一意になるようにヒントを調整できること、さまざまな制約を柔軟に取り入れられることを見てきました。この柔軟性により、数理最適化を使うこと自体が、まるでパズルを解くような楽しさがあると感じています。

数理最適化は、コストの最小化や効率化といった典型的な最適化問題に限らず、工夫次第でさまざまな課題に応用できる強力な手法です。この記事を通じて、そのイメージを少しでも感じていただけたなら幸いです。

脚注

  1. 「数理最適化でナンプレ（数独）を解く」 - Qiita
    この記事では、Pythonのpulpライブラリを使用して、ナンプレを数理最適化の手法で解く方法を詳しく解説しています。 ↩︎

  2. 「最適化① - ナンプレをortoolsで解いてみる」 - Qiita
    Googleのortoolsを用いて、ナンプレを解く手法を紹介しています。 数理最適化の具体的な実装例として参考になります。 ↩︎

  3. 目的関数が不要であっても、目的関数を設定した方が計算時間が短くなるようなケースもあるようです。 ↩︎

  4. ChatGPT にこの方法を提案されたので、そのまま採用しました。 ↩︎

  5. おそらく何度繰り返しても同じ解になりますが、保証されているわけでもありません。 ↩︎

  6. ナンプレの性質上、完全に上下対象、左右対称な問題は作れません（同じ行や列に同じ数字が入るため）。ルールに適合する対称性を考える必要があります。 ↩︎

Discussion