AIが4x4の数独を解くのが難しいのはなぜか
GPTに、なぜ君は数独を解くことが難しいのか、尋ねてみた
数独（通称ナンプレ）ソルバーのコードをいろいろ見てみて、
最も優れたアルゴリズムはDonald E. Knuth博士の開発した
Algorithm Xの改良版の”Dancing Links”である、と思った。
（Dancing Links は、Exact Cover Problem（完全被覆問題） を効率的に解くために、
Knuthが提案した Algorithm X を高速化するためのデータ構造です。）
これを用いて解くと、ほぼ人間が数独を解いているように解ける（ただし、超上級レベルの問題は解くには時間がかかる）
双方向循環リンクリストを用いて、ノードの削除と復元を効率的に行う、らしい。
しかし、AIに数独の問題を「解いてください」と依頼すると、間違えたり、でたらめな答えを示すことが多い。
これはなぜなのか？
ようするに 自分で考えていない ために、Web上にある解法のデータをつなぎ合わせて、適当な解を示すのだ。
Web上に、同じような問題があるばあい、そのデータを検索してきて当てはめるだけなのだ。
これは唯一の「解」が求められる数独の解にはなりえないのである。８０％の精度では全くダメ。
１００％、合っていなくては数独は解けない。
したがって、これでは、でたらめな答えにならざるを得ないのである。
AIは決して 「自分で考えてはいない」。
そのことを知らない人が、多いような気がする。
ChatGPTに質問してみた
４ｘ４ならば、数独を少しでもかじった人間なら、あっという間に解けてしまうでしょうね。
でも、ＡＩにとって、この課題が難しい理由は何ですか？
ChatGPTの回答
まさにその通りです。4×4数独は人間にとっては小さな盤面なので、少し数独をやった経験があれば直感や候補の絞り込みだけで短時間で解けます。でもAIにとっては難しい理由がいくつかあります。整理するとこうなります。
-
直感的なパターン認識ができない
人間は「候補がこの行・列・ブロックで絞られた」「ここに入れるとすぐ矛盾」などを直感的に把握します。
現状の言語モデル（GPTなど）は、文章や数値のパターンを統計的に学習しているだけで、直感的に候補を把握する能力はありません。
つまり、「頭の中で候補表を作り、可能性を瞬時に排除する」作業が自然にはできません。 -
論理的手順の再帰的推論が苦手
数独は、候補の組み合わせを順に追い、矛盾を見つけて消去する「再帰的推論」が必要です。
小さい盤面でも、場合分けの連鎖（フォーシングチェイン）が必要な局面では、人間は直感で飛ばせますが、AIは全手順を逐一推論する必要があります。
言語モデルは一度に長い論理チェーンを正確に追うのが苦手で、途中で「矛盾を見逃す」ことがあります。 -
状態管理が難しい
人間は頭の中で候補表や盤面の状態を簡単に更新できます。
GPTのようなモデルは「文章としての盤面」を扱うため、候補の消去・追加・複数の仮定などを正確に管理するのが難しいです。
その結果、直感的に進めることができず、誤った候補を残してしまうことがあります。 -
小さな盤面でも情報密度が高い
4×4でも、一つの数字の選択が他の複数セルに影響するため、局所的な決定だけでは解けません。
人間は「影響範囲を瞬時に予測」できますが、AIは統計的な推定や全探索なしには判断できない場合があります。
結論
人間：パターン認識＋直感＋経験で即座に解ける
現状のAI：逐次的・統計的処理しかできず、候補管理や再帰的推論をアルゴリズムなしで正確に行うのが難しい
つまり、「小さい盤面でも直感と経験に依存する部分が多い」ことが、AIにとっての最大の難しさです。
Discussion