世界一難しいナンプレをヒントエンジンで解いてみました

公式に世界一難しいと認められたナンプレはありません。何を基準にするかで変わります。私たちは、ナンプレアプリのヒントエンジンを使い、プレイヤーが解くときと同じように、その時点で使える最も簡単な解法で1手ずつ進めて調べました。

調べ方

ヒントエンジンは、私たちのアプリのヒントと同じコードです。数字を入れられる最も簡単な解法を探して数字を入れ、また探すことを、盤面が埋まるまで繰り返します。最後に試す解法がフォーシングチェーンです。それでも進めない場合、エンジンは入る数字を把握していますが、その根拠を説明できる手順がありません。ナンプレソルバーで、すべての手順を確認できます。

検証結果

ここからわかること

• 最初に入っている数字が少なくても、問題が難しくなるとは限りません。総当たりのプログラム向けの問題には、答えが1つだけのナンプレで最小となる17個の数字が入っていますが、人ならシングルだけで解けます。Inkalaの2012年の問題には21個の数字が入っていますが、それでも数字を仮に置いて試す必要があります。
• コンピューターにとっての難しさと、人にとっての難しさは異なります。すべての数字を順番に試すプログラムは、総当たりのプログラム向けの問題で膨大な回数を試す必要がありますが、人なら当てずっぽうを使う必要は一度もありません。
• アプリで最も難しいレベルでも、数字を仮に置いて試す必要はありません。全60,000問のどれにもフォーシングチェーンは必要ありません。「エクストリーム」レベルでは、最も難しい手順の大半がALS-XZで、その割合は86.3%です。

どの問題が最も難しいかは、基準によって変わります。SudokuWiki独自の基準では、Inkalaの2012年の問題は、David Filmerが作った2問に次いで3位です。 SudokuWiki: Arto Inkala Sudoku