第3章 Prologで数独を解く¶

盤面を直接操作するソルバーでは、空きマスへ数字を書き込み、行き詰まったら元へ戻します。 Prolog では、空きマスを値が未定の 論理変数 として表します。候補の一つを論理変数へ結び付け、その先の規則を満たせなければ、Prologが結び付ける前の状態へ戻ります。プログラム側で盤面を復元する処理を記述する必要はありません。

SWI-Prolog を用いて、Prologが規則を使って問い合わせへ答える流れを数独に当てはめます。本章では数字の候補範囲を自動追跡する有限領域制約ライブラリは使わず、論理変数、単一化、失敗、選択肢の探索をプログラムに記述します。

事実と規則へ問い合わせる¶

Prologでは、値どうしの関係に名前と引数を付けたものを述語と呼びます。その関係が無条件に成り立つものを事実、別の条件から成り立つものを規則として記述します。たとえば、数独の初期配置を given(行, 列, 数字) という事実で表してみます。

% 数独の初期配置を、行・列・数字の事実として表します。
given(1, 1, 5).
given(1, 4, 6).

% 同じ行の別のマスには、すでに置かれた数字を使えません。
blocked_in_row(Row, Col, Digit) :-
    given(Row, OtherCol, Digit),
    between(1, 9, Col),
    Col \= OtherCol.

given(1, 1, 5). は「1行1列に5がある」という事実です。blocked_in_row は、同じ行の別のマスではその数字を使えない、という規則です。規則の :- は、右側の条件がすべて成り立てば左側も成り立つ、と読めます。

この章で使うPrologの表記¶
表記	読み方
`name/3`	引数を3個取る `name` という述語。数字は引数の個数を表す
`A, B`	`A` と `B` の両方が成り立つ
`A \= B`	`A` と `B` を単一化できない
`?-`	ここから後ろが問い合わせであることを示す対話環境の表示
`.`	節（事実や規則）の終わり。Pythonの改行やセミコロンに相当する
`_`	無名変数。出現ごとに別の新しい変数になり、値を参照しない
`(C -> T ; E)`	条件 `C` が成り立てば `T`、さもなければ `E`。if-then-elseに相当する

ファイルを読み込んだあと、次のように問い合わせます。

$ swipl -q -s examples/02-prolog/facts_rules.pl
?- blocked_in_row(1, 2, 5).
true.

?- blocked_in_row(1, Col, 5).
Col = 2 ;
Col = 3.

一つ目の問い合わせは、1行2列で5が使えないかを尋ねています。二つ目の Col は値を指定していない変数です。Prologは最初に Col = 2 と答えます。そこで ; を入力すると、次の答え Col = 3 を表示します。実際のソルバーでは初期配置を事実の集まりにはせず、 81要素のリストとして扱います。それでも、規則を定義し、問い合わせに合う値を探す形は同じです。SWI-Prologの基本的な起動、規則の読み込み、問い合わせの流れは公式マニュアルにもまとまっています [1]。

論理変数を数字と結び付ける¶

Prologの変数は、大文字またはアンダースコアで始まります。Cell は論理変数、5 は整数です。次の問い合わせでは、単一化によって Cell と 5 を同じ値にします。

?- Cell = 5.
Cell = 5.

単一化 は、二つの項を同じ形にできるか調べ、必要な変数を結び付ける操作です。リストや複合項にも使えます。

?- [A, 2] = [1, B].
A = 1,
B = 2.

論理変数は、一つの探索経路では同じ値を保ちます。Cell を5に結び付けたあとで6とも単一化しようとすると、二つの条件を同時に満たせないため失敗します。

?- Cell = 5, Cell = 6.
false.

この失敗が起きると、Prologは直近の選択肢まで戻ります。戻った時点より後に作られた変数の束縛も取り消されます。SWI-Prologの用語集では、選択肢を残した位置を選択点（choice point）と呼び、バックトラック時にはそこまでの実行状態を復元すると説明しています [2]。

たとえば member(Digit, [2, 5]) は、最初に Digit = 2 で成功し、5という選択肢を残します。その後の規則が失敗すれば Digit = 5 を試します。数独では、この member/2 を候補の仮置きに用います。

補足

単一化は左右の向きを持ちません。Cell = 5 と 5 = Cell は、どちらも同じ関係を表します。値を更新する代入よりも、等しいという条件を加える操作として定義されます。

空きマスを論理変数にする¶

入力ファイルでは、空きマスを 0 で表しています。読み込んだ81個の整数から、0だけを新しい論理変数へ置き換えます。

numbers_cells([], []).
numbers_cells([0|Numbers], [_|Cells]) :-
    % 0のマスには、新しい論理変数を一つ置きます。
    numbers_cells(Numbers, Cells).
numbers_cells([Number|Numbers], [Number|Cells]) :-
    Number \= 0,
    % 初期配置の数字は、整数のまま盤面に残します。
    numbers_cells(Numbers, Cells).

リストの先頭が0なら、出力側の先頭を無名変数 _ にします。この _ は、呼び出すたびに別の新しい変数になります。初期配置の数字は整数のままです。

たとえば、盤面の先頭が 5006... なら、内部ではおおよそ次の形になります。

[5, A, B, 6, ...]

A や B は説明のために付けた名前です。実際には、81要素のリストの中に無名の論理変数が入っています。リスト自身が盤面であり、探索が終わると各変数が整数へ単一化されています。

数独の規則を候補にする¶

空きマスの位置を \(p\)、そのマスと同じ行、列、3×3ブロックにすでにある数字の集合を \(U(p)\) とします。候補集合 \(D(p)\) は次の式で求められます。

\[D(p) = \{1,\ldots,9\} \setminus U(p)\]

1から9のうち、行、列、ブロックですでに使われた数字を除く計算です。 candidate_digits/3 は、候補を通常のPrologリストとして返します。たとえば [2, 5] です。

空きマスが複数ある場合は、候補数が最も少ないマスを選びます。この選び方をMRV （Minimum Remaining Values）と呼びます。ここでは候補数とマス番号を Count-(Index-Candidates) にまとめ、keysort/2 で候補数の小さい順に並べます。この - は引き算ではなく、値を組にするPrologの複合項です。外側の Count が並べ替えのキーとなり、内側にマス番号と候補リストを保持します。

search(Cells) :-
    (   has_variable(Cells)
    ->  best_cell(Cells, Cell, Candidates),
        % 候補が空ならここで失敗し、Prologが直前の選択肢へ戻ります。
        Candidates \= [],
        member(Value, Candidates),
        % 単一化によって、選んだ数字を論理変数へ仮置きします。
        Cell = Value,
        search(Cells)
    ;   % 論理変数が残っていなければ、盤面は完成しています。
        true
    ).

has_variable([Cell|_]) :-
    var(Cell),
    !.
has_variable([_|Cells]) :-
    has_variable(Cells).

best_cell(Cells, Cell, Candidates) :-
    findall(
        Count-(Index-CellCandidates),
        (   nth0(Index, Cells, Current),
            var(Current),
            candidate_digits(Cells, Index, CellCandidates),
            length(CellCandidates, Count)
        ),
        Choices
    ),
    % 候補数をキーに並べ、分岐の少ないマスを選びます。
    keysort(Choices, [_-(Index-Candidates)|_]),
    nth0(Index, Cells, Cell).

candidate_digits(Cells, Index, Candidates) :-
    used_values(Cells, Index, Used),
    findall(
        Digit,
        (between(1, 9, Digit), \+ memberchk(Digit, Used)),
        Candidates
    ).

探索の中心は search/1 です。member(Value, Candidates) が候補を一つ選び、 Cell = Value が論理変数をその数字に単一化します。再帰呼び出しの先で候補が空になると、 Candidates \= [] が失敗します。Prologは member/2 の選択点へ戻り、変数の束縛を取り消して次の候補を選びます。

コードの (条件 -> 処理1 ; 処理2) は、条件が成り立てば処理1、成り立たなければ処理2へ進む分岐です。has_variable(Cells) が真の間は候補を選び、偽になると完成盤面として成功します。

第1章のPython実装にあった board[position] = 0 に相当する処理はありません。状態の復元はPrologの選択点管理とバックトラック機構が行います。すべてのマスに数字が確定し未定の論理変数が残らない状態になると has_variable/1 が失敗し、true 節へ進んで完成盤面を返します。

CLP(FD)との分担¶

Prologで数独を書く場合、CLP(FD)（有限領域上の制約論理プログラミング）を使う実装も一般的です。 SWI-Prologには、整数の範囲を表す ins/2、重複を禁じる all_distinct/1、具体的な値を列挙する labeling/2 などが用意されています [3]。これらを使えば、行、列、ブロックの制約を短く記述でき、候補の伝播もライブラリに任せられます。

この章では、Prologそのものの単一化と選択肢の探索が見えるように、通常のProlog述語で候補計算やMRVを実装しています。そのため、CLP(FD)を使う場合よりコードは長くなり、ほかのProlog処理系へ移すときにも組み込み述語の差を調整する必要があります。制約を宣言してソルバーに伝播させる方法は、第5章「制約プログラミング」で扱います。

実装と処理系¶

サンプルはSWI-Prolog 10.0.2で検証しました。read_file_to_codes/3 で盤面を読み、 findnsols/4 で指定した個数まで解を集めています。探索部分は通常のProlog述語だけで構成していますが、入出力と解数の制限にはSWI-Prologのライブラリを使っています。

solve_numbers/3 は、入力盤面から完成盤面を探す向きで使うよう実装しています。候補を調べるために var/1、integer/1、算術演算を使っているため、引数のどこを未知にしても同じ規則を逆向きに実行することはできません。論理変数を使うプログラムであっても、双方向に実行できるかどうかは実装依存です。

完全なコードは examples/02-prolog/solve.pl にあります。詳しい実行手順やコマンドラインオプションについては examples/02-prolog/README.md を参照してください。

実行結果¶

通常問題では解が1つ得られ、別解を探索しても見つからないことから一意解であることが確認できます。

engine: SWI-Prolog without CLP(FD)
limit: 2
solutions: 1
status: solved
search complete: yes
uniqueness: unique
solution 1:
534678912
672195348
198342567
859761423
426853791
713924856
961537284
287419635
345286179

矛盾問題では制約を満たす選択肢が存在せず、すべての枝で探索が失敗するため解なし（unsat）と判定されます。

engine: SWI-Prolog without CLP(FD)
limit: 2
solutions: 0
status: unsat
search complete: yes
uniqueness: not applicable

複数解問題では、異なる2つの完成盤面が得られた時点で指定した上限に達して探索を打ち切ります。この時点で、一意解ではない（複数解を持つ）ことが判定されます。

engine: SWI-Prolog without CLP(FD)
limit: 2
solutions: 2
status: solved
search complete: no
uniqueness: not unique
solution 1:
534678912
672195348
198342567
859761423
426853791
713924856
961537284
287419635
345286179
solution 2:
534678921
671295348
298341567
859762413
416853792
723914856
962537184
187429635
345186279

これらの結果は共通の検証器によっても初期配置の保持や規則の適合性が確認されています。

この方法で分かること¶

candidate_digits/3 は、その時点で規則に反しない数字をすべて列挙します。member/2 は各候補を順に選び、失敗すれば残りを試します。この探索を打ち切らずに終えれば、解が存在しない場合も unsat と判定します。乱数は使わないため、候補とマスの選択順も毎回同じです。

最初の解を得た時点で止めた結果だけでは一意性を確定できません。二解が見つかれば複数解、一解だけを返して全領域の探索が終了すれば一意解です。

この実装の候補計算が参照するのは、現在決まっている数字だけです。隠れたシングルなどの候補伝播は行わないため、難しい問題ではMRVを使っても探索量が増えます。掲載した出力は三つの共通問題に対する実行結果であり、Prolog全般の性能比較を示すものではありません。

参考文献¶

[1]

SWI-Prolog developers. Getting Started Quickly. SWI-Prolog, 2026. URL: https://www.swi-prolog.org/pldoc/man?section=quickstart (visited on 2026-08-08).

[2]

SWI-Prolog developers. Glossary of Terms. SWI-Prolog, 2026. URL: https://www.swi-prolog.org/pldoc/man?section=glossary (visited on 2026-08-08).

[3]

SWI-Prolog developers. CLP(FD): Introduction. SWI-Prolog, 2026. URL: https://www.swi-prolog.org/pldoc/man?section=clpfd-intro (visited on 2026-08-08).