Wired News – 日本からイギリスに渡ったパズル、大ブームに – : Hotwired

米国でパズルゲームといえば『テトリス』や『ルービック・キューブ』だが、イギリスでは今、日本生まれのパズル『Su Doku』[数独、日本ではナンバープレース、ナンプレなどとも呼ばれる]が大人気だ。クロスワードパズルの数字版といった趣のこのパズルにすっかりはまりこんでしまった人たちが、イギリスでは国中にあふれている。

これは面白そうだ。
しかしこういう単純なパズルをプログラムに解かせようとアルゴリズムを考えてる俺ガイル。
答えはまだ無い。

もちろん総当りで解かせれば簡単なんだけどそれじゃ能が無い。
やっぱり解法から最速のアルゴリズムを見つけなきゃね。
ぱっと思いついたのはこんなとこ。

1. まず9×9のマトリックスを1次元の配列で処理したいんで、[0..26]のバッファを用意。(1行1列を[0]、1行2列を[1]、2行1列を[9]の様にマッピングすると、m行n列のインデックスは[mx9+n-1]。)
2. 次にイニシャル(初期値）の埋め込み。ここはmn値でイニシャルを埋めるだけ。
3. イニシャル値の埋まっている個数の一番多い列（行）を抽出して最上の優先度を持つ行（列）（以下MPC）を決定する。同数の場合は[m,n]値の小さいものを優先し行列では行を優先する。
4. MPCの各セルN[0..9]において各空欄{x}での候補値を導出。
   N[x]は、（[0..9]のうち行方向で使われていないもの)and（[0..9]のうち列方向で使われていないもの）を満たす必要があるのはルールの通り。

5. MPCの空きセルのうち候補値のもっとも少ないものから順に仮の値を設定してMPC上の値を一時確定させる。
6. 再度MPC選定に戻り確定するまで繰り返す。

うーん。あんまり早くなさそうだなぁ。