ルールを守ってパズルを解く：制約充足問題

「AIの基礎：探索から機械学習まで」のレッスン 9 / 15・約6分

変数・ドメイン・制約の3要素でパズルを定義し、バックトラック探索とアーク整合性（AC-3）で効率的に解く手法を学ぶレッスンです。

このレッスンで学ぶこと

制約充足問題とバックトラック探索を説明する
身のまわりの問題に当てはめて考える

レッスンの内容

ルールを1つも破らない並べ方

隣り合う地域を別の色で塗る。数独で同じ数字を重ねない。どれもルールを1つも破らない組み合わせを探す問題です。

これを制約充足問題といいます。

3色で塗り分けてみよう

7つの地域を3色で塗り、となりを別の色にします。塗れたら「AIに解かせる」で手数と比べましょう。

問題を3つの部品に分ける

7つの地域のように決めたい対象が変数。選べる3色がドメイン、「となりは別の色」が制約です。

この3つを整理すれば、地図でも数独でも同じ手順で解けます。

数独では、空いたマスに1〜9のどれかを入れます。この「1〜9の数字の集まり」は、変数・ドメイン・制約のどれ？

問題：数独では、空いたマスに1〜9のどれかを入れます。この「1〜9の数字の集まり」は、変数・ドメイン・制約のどれ？

ドメイン（正解）
変数
制約

解説：1つのマスに入れられる値の候補なので、ドメインです。マスそのものが変数、「同じ列に同じ数字を入れない」が制約にあたります。

全部試すと、すぐ膨らむ

7地域を3色で塗ると2187通り。20地域だと約35億通りにもなります。

1つずつ全部試すやり方では、問題が大きくなると計算が間に合いません。

破れたら、1つ前へ戻る

バックトラック探索は1つずつ試し、違反した瞬間に1つ前へ戻ります。

だめな先の組み合わせを試さずに済む、深さ優先探索と同じ進め方です。

7つの地域を3色で塗るとき、バックトラック探索が2187通りの総当たりより速く終わるのはなぜ？

問題：7つの地域を3色で塗るとき、バックトラック探索が2187通りの総当たりより速く終わるのはなぜ？

ルールを破った時点で、その先の塗り方を試さないから（正解）
2187通りの塗り方を、同時にまとめて試しているから
どの地域に何色が合うかを、最初から知っているから

解説：となりと同じ色を塗った瞬間に戻るので、その先の塗り方は試さずに捨てられます。速さの理由は、試す数そのものが減るからです。

決まった色を、となりから消す

となりが青になれば、自分は青を消せます。成り立たない候補をあらかじめ消す考え方がアーク整合性です。

選択肢を減らしておけば、試行錯誤も少なくなります。

1つ消すと、次も消える

Aが青に決まり、となりのBから青が消えて黄だけになると、BのとなりのCから黄が消えます。

何も消えなくなるまでこれを繰り返す手順がAC-3です。

○か✕か

○か✕か：アーク整合性で候補を消していくと、正しい答えに必要な色まで消えてしまうことがある。

答え：✕。消すのはとなりのどの候補とも合わない色だけです。その色を選べば必ずルールを破るので、答えに使われることはありません。

候補が少ない地域から塗る

迷ったら、残った候補が一番少ない地域から塗ります。これを最小残り値ヒューリスティックと呼びます。

選べる色が1つしかない場所を後回しにすると、無駄な試行錯誤が増えてしまうためです。

地図の塗り分けの途中で、地域Aは候補が3色、Bは2色、Cは1色だけ残っています。最小残り値ヒューリスティックで次に塗るのは？

問題：地図の塗り分けの途中で、地域Aは候補が3色、Bは2色、Cは1色だけ残っています。最小残り値ヒューリスティックで次に塗るのは？

候補が1色だけの地域C（正解）
候補が3色ある地域A
候補が2色ある地域B

解説：残った候補が最も少ない地域から決めるので、Cです。選べる色が1つしかない地域を先に決めれば、失敗するルートにすぐ気づけます。

試験の日程も、同じ形

大学の試験日程づくりも同じ形です。科目が変数、試験日がドメイン、「同じ学生が受ける2科目は別の日」が制約。

看護師のシフトや時間割づくりも、こう書けば同じ手順で解けます。

○か✕か

○か✕か：制約充足問題では、決められたルールを1つ破っても、ほかの点がよければ答えとして認められる。

答え：✕。決められた制約は、1つでも破れば答えになりません。点数を比べて一番を選ぶ問題とは違い、まずすべてのルールを守れるかが問われます。

ルールを守る答えの探し方

問題を 変数・ドメイン・制約 の3つに置き直す
1つずつ仮に決め、ルールを破ったら1つ前へ戻る
両立しない候補を先に消し、消えた分をとなりへ連鎖させる
候補が一番少ない変数から決めて、行き詰まりを早く見つける

7科目の試験を3日に割り振ります。同じ学生が受ける2科目は別の日です。1つずつ仮に決めていくとき、戻る回数がいちばん少なく済みそうな進め方は？

問題：7科目の試験を3日に割り振ります。同じ学生が受ける2科目は別の日です。1つずつ仮に決めていくとき、戻る回数がいちばん少なく済みそうな進め方は？

候補日が少ない科目から決め、そのたび両立しない日を消す（正解）
科目表の上から順に決め、ルールを破ったら1つ前へ戻る
受ける学生が多い科目ほど後に回し、最後にまとめて決める

解説：候補の少ない科目から決め、両立しない日を先に消せば、戻る回数がぐっと減ります。おつかれさまでした。ただ、ここではルールを人が書き出せました。では「迷惑メールかどうか」のように、誰もルールを書けない問題はどうするのでしょう。次は、正解付きの例をたくさん見せて、AI自身にルールを見つけさせる機械学習に入ります。

用語

AC-3（AC-3）: 候補を1つ消したら影響を受けるとなりも確かめ直す。何も消えなくなるまで繰り返して、アーク整合性を保つ手順。
制約（Constraint）: 変数どうしが守るルール。「となりの地域は別の色」など。
変数（Variable）: 値を決める対象のこと。地図の地域や、数独の空きマスなどを指します。
ドメイン（Domain）: 変数が取れる値の候補。地図なら塗れる色、数独なら1〜9の数字です。
アーク整合性（Arc Consistency）: 2つの変数の間で、相手のどの候補とも両立しない候補を消しておくこと。
制約充足問題（Constraint Satisfaction Problem (CSP)）: 決めるもの・選べる値・ルールの3つで書ける問題。ルールを1つも破らない割り当てを探す。
バックトラック探索（Backtracking Search）: 1つずつ仮に決め、ルールを破ったら1つ前に戻って別の値を試す探し方。
最小残り値ヒューリスティック（Minimum Remaining Values (MRV)）: 次に決める変数として、残った候補が一番少ないものを選ぶ進め方。