解けたら天才！ フィンランドの数学者が作った「世界一難しい数独」というのがあるらしい。

こちらの問題、実はフィンランドの数学者Arto Inkala氏が作成した問題で、曰く「世界でもっとも難しい数独」とのこと

この問題の作者であるArto Inkalaさんは、これまで「史上最難」と言われいた問題「AI Escargot」の作者でもある。その彼が言うのだから、間違いないと言いたいところだが、そもそも、数独の難しさに客観的な指標なんてないはず。合理的なものに限っても、たまたま知っていた定石で一発、なんてこともあり得る。だから、「ある解き方においては最も難しい」という限定的なことしか言えないのだ。彼自身、著書“AI Escargot”の中で次のように述べている。

it is often impossible to clearly identify the clearly most difficult puzzle in the world.

それにも拘わらず「世界でもっとも難しい」なんて言うことの大人の事情は放っておいて、せっかくだから手元にあるアルゴリズム（単純なしらみつぶし）でどうなるかを見てみよう。解を見つけるまでにどれだけの候補をチェックしなければならないかを調べる。Mathematica版なら全体をTraceで囲んで、結果の長さを見ればよい。

problem={
  {0, 0, 5, 3, 0, 0, 0, 0, 0},
  {8, 0, 0, 0, 0, 0, 0, 2, 0},
  {0, 7, 0, 0, 1, 0, 5, 0, 0},
  {4, 0, 0, 0, 0, 5, 3, 0, 0},
  {0, 1, 0, 0, 7, 0, 0, 0, 6},
  {0, 0, 3, 2, 0, 0, 0, 8, 0},
  {0, 6, 0, 5, 0, 0, 0, 0, 9},
  {0, 0, 4, 0, 0, 0, 0, 3, 0},
  {0, 0, 0, 0, 0, 9, 7, 0, 0}};

Reap@Length[Trace[search[{problem}, Join[#2, #1] &, False]]]

{80070, {{1 4 5 3 2 7 6 9 8}}}
          8 3 9 6 5 4 1 2 7
          6 7 2 9 1 8 5 4 3
          4 9 6 1 8 5 3 7 2
          2 1 8 4 7 3 9 5 6
          7 5 3 2 9 6 4 8 1
          3 6 7 5 4 2 8 1 9
          9 8 4 7 6 1 2 3 5
          5 2 1 8 3 9 7 6 4

となるので、この問題をMathematicaで解くときの、Traceの長さは80070。

一方、AI Escargotはと言うと、

problem={
  {1, 0, 0, 0, 0, 7, 0, 9, 0},
  {0, 3, 0, 0, 2, 0, 0, 0, 8},
  {0, 0, 9, 6, 0, 0, 5, 0, 0},
  {0, 0, 5, 3, 0, 0, 9, 0, 0},
  {0, 1, 0, 0, 8, 0, 0, 0, 2},
  {6, 0, 0, 0, 0, 4, 0, 0, 0},
  {3, 0, 0, 0, 0, 0, 0, 1, 0},
  {0, 4, 0, 0, 0, 0, 0, 0, 7},
  {0, 0, 7, 0, 0, 0, 3, 0, 0}};

Reap@Length[Trace[search[{problem}, Join[#2, #1] &, False]]]

{71766, {{1 6 2 8 5 7 4 9 3}}}
          5 3 4 1 2 9 6 7 8
          7 8 9 6 4 3 5 2 1
          4 7 5 3 1 2 9 8 6
          9 1 3 5 8 6 7 4 2
          6 2 8 7 9 4 1 3 5
          3 5 6 4 7 8 2 1 9
          2 4 1 9 3 5 8 6 7
          8 9 7 2 6 1 3 5 4

となる。解くときのTraceの長さ71766は、先の値80070より小さい。ということは、ここで採用しているアルゴリズムを基準にすれば、今回発表された問題は、確かにAI Escargotより難しい。

しかし、このアルゴリズムを基準にするなら、もっと難しい問題はある（Mathematicaでは時間がかかるからC++版で試す。オプション「-pg」を付けてコンパイルして実行し、gprofでプロファイルを見ればよい）。MathematicaでもC++でも、わざわざコードを書き換えたりしないのがポイント。

要するに、どの隅から解いていくかという話なのだが、ここで使っている方法の場合、どちらの問題も、右下から左下に向かって解くときに最も難しくなる。再帰的な関数searchが、今回発表された問題を180度回転したものの場合は110874回、AI Escargotを180度回転したものの場合は1502267回呼ばれる（どちらもCodepadでは解けない）。

つまり、ここで採用した基準では、世界一難しいのは今回発表された問題ではなく、依然としてAI Escargot（を180度回転したもの）だということになる。

追記：どちらも自力で解けた友人によると、AI Escargotの方が難しかったそうです。もう一つの方は30分ほどだったとか。