どうやら人間の手で解いたら、簡単に解けてしまうようです。 ここでの難易度の定義に含めていない解法(n国同盟など)を使うと、難しくない問題になっているのかもしれません。
その後調べたところ、基本テクニックだけで解けてしまうことがわかりました。 Pencil Marksが唯一残ったものしか確定しない、というDeterministic Solverを使っていたのが原因で、 難しくない問題を「難しい」と誤判定してしまったようです。
Determistic Solver、つまり難易度判定を見直しました。これで基本解法だけでは解けなくなったはずです。
もちろん世界最高難易度にはほど遠いですが・・・。
↓
もう少し難易度判定を見直しました。これは難しいでしょうか？
3月13日版よりだいぶ難易度があがったはずです。
スパコンを使って力任せに数独の難しい問題を作ってみたところ、
2013年3月現在、おそらく世界で一番難しい問題を作ることに成功した失敗した。
上図がスパコンを用いて作られた、おそらく世界で一番難しい問題(2013年3月現在)。 後述する難易度の定義では、深さが10、通常幅が183530、平均幅が約100571である。 このうち平均幅が難易度の指標であり、それが10万を超えるということは、 単純な解法では解答にたどり着くまでに数万回ほど再帰しなければ ならないことを意味するので、人間が手で解くのは不可能だと思われる。
この計算を行う前に知られている、最も難しい数独の問題は、フィンランドの数学者、 Dr. Arto Inkara氏によるものであろう。以下の問題の(a)が2010年に発表されたもの、 (b)が2012年に発表されたものである。(a)の問題は深さ5、通常幅173、平均幅179。 (b)の問題は深さ8、通常幅3599、平均幅2257である。
この問題より難しい問題をスパコンを使って作ることにする。
Inkara氏が認めているように、数独の難易度の定義は難しい。 一般にパズルの難易度は、解法につかう手法に依存する。 数独の解法には様々なテクニックがあるが、 ここではPencil MarksとRecursive Backtrackingのみを採用する。
Pencil Marks: 空白のマス一つに着目し、そのマスが所属する行、列、ブロックに 存在する数字以外の数字を小さくそのマスに記入する。これらの数字は、そのマスに入る 可能性のある数字である。後で消せるように鉛筆で書くことからPencil Marksと呼ばれている。 もし、候補が一つしかなければ、そのマスの値が確定する。これを、どの空白のマスも 二つ以上の候補が存在するようになるまで繰り返す。
Recursive Backtracking: Pencil Marksで、どの空白のマスも 二つ以上の候補が存在する状態で、最も候補数が少ないマスを選び、その候補のうちの どれかを仮定して解き進める(再帰)。もし後で矛盾が生じたら、矛盾が生じる前まで 戻り(バックトラック)、別の候補を選んで再帰する。
数独を解くアルゴリズムとしては、まずPencil Marksで解けるだけ解いて、 その後、どこかのマスを選んで再帰し、またPencil Marksで解けるだけ解いて・・・、 ということを解を見つけるまで繰り返す。
まず、Pencil Marksは決定論的で、計算コストもたいしたことが無いので、 難易度には含めないことにする。この解法では、再帰によって木構造を作るので、 その構造の性質で難易度を決める。
まず、最初に与えられた問題(をPencil Marksでなるべく数字を埋めたもの)を 木構造の根ノード(root node)とする。その後、最も候補数の少ないマスを選び、 そのマスを軸に再帰する。その候補の数だけ根ノードの子ノードを作る。 それぞれの子ノードにおいてPencil Marksで答えが出ず、かつ矛盾も生じなかった場合には 再帰的に子ノードを定義していく。子ノードを持たないノードを葉ノード(leaf node)と呼ぶが、 葉ノードは解答であるか、矛盾が生じた状態のどちらかである。 この木構造において、根ノードから解答ノードまでの距離を、与えられた問題の深さ (depth)、 根ノードも含めたノードの総数を幅 (width) と呼び、幅を問題の難しさと定義する。
ここで、最も候補数の少ないマスが、同じ候補数で複数存在する場合、 どのマスを軸に再帰するかによって、深さや幅が異なることになる。 そこで、様々な可能性がある中で、最も浅い「深さ (つまりshortet path)」をこの問題の深さと定義する。 これは問題を解くための最低再帰数である。 また、候補数が複数存在した場合に、右上優先で再帰するマスを選んだ場合の幅を 通常幅 (normal width)と呼ぶ。 しかし、この定義では問題の難しさが問題の向きに依存してしまう。 そこで、再帰するマスに複数の候補がある場合、マスをランダムに選ぶことにする。 それを何度も繰り返し、平均を取った物を平均幅 (average width)と定義し、 これを問題の難しさにする。ここでは、100回の平均で平均幅を求めることにする。
なお、Inkara氏が2010年に発表した問題の深さは5、通常幅は173、平均幅は約179であるのに対し、 2012年に発表した問題では深さが8、通常幅が3599、平均幅が約2257であるので、 2010年の問題に比べて10倍以上難しいことがわかる。
数独はNP完全であることが知られており、かつ以前からスピングラス系との類似性も指摘されている。 そこで、適当なハミルトニアンを定義し、 数独の問題作成をイジングスピングラス系に似た模型の基底状態探索問題に帰着させ、 モンテカルロ法を使って最低エネルギー状態を探すことにした。
まず、ランダムに問題の元となる解答を作る。ここから問題を作るには、81個の数字のうち どれを消すかを決める必要がある。そこで、各マスを「サイト」だと思い、 数字を残す状態を「スピン上向き状態」、数字を消した状態を「スピン下向き状態」と定義する。 すると、この系は81個のスピンがあるイジングスピン模型となる。
この系のエネルギーを以下のように定義する。
ここでs_iがスピンの状態、Jが相互作用エネルギー、Uが内部エネルギー、 hが外場である。内部エネルギーUは、深さと幅で定義する。 最終目標は幅の広い問題を見つけることだが、最初から幅優先探索をすると 難しい問題を見つけるのが難しいことがわかったため、まずは深さ優先探索をする。 深さをdとする時、U=dとして、モンテカルロ法で「深い」問題を探す。 そしてある程度「深い」問題を見つけたら、そこから幅優先探索に切り替える。
深い問題が見つかったら、幅優先探索に切り替えるが、その際、 現在の問題の幅をwとして、U = log(w)とする。対数を取ったのは、 幅が深さに対して指数関数的に大きくなるため、そのままでは計算が不安定になるからである。
なお、平均幅の計算コストはかなり重いため、エネルギー計算には通常幅を用いてシミュレーションして 難しい問題の候補を探し、それらの候補について平均幅を計算して、最終的に最も難しい問題を選ぶ。 幅優先探索では、より効率的に探索するため、レプリカ交換モンテカルロ法を用いた。
以上のような計算を、1024コアを用いて24時間計算して得られた「最も難しい問題」が冒頭に 掲げた問題である。深さは8で、2012年にInkara氏により発表されたものと同じだが、 平均幅が98684と、Inkara氏の問題より40倍以上難しい。
数独の問題をイジングスピングラスに似た模型の基底状態探索問題に帰着させ、 レプリカ交換モンテカルロ法を用いることで、難易度の高い数独の問題を作った。 ただし、難易度の定義は採用する解法テクニックに依存するため、一意に決める事はできない。 あくまでここでの定義においてInkara氏の問題より難しい問題ができた、ということである。 だが、ここで使った手法は一般的なものなので、難易度を数値化する定義さえ与えられれば その定義において難しい問題を作ることは容易である。
Author: Hiroshi Watanabe