JavaScriptでDancingLinksアルゴリズムによる数独ソルバを作った

　昨今のJSエンジンはすごい。とにかく速い。3Dとかもやれちゃう。
なんだかもう、前処理はクライアント側でやらせて、サーバはサボっててもいいんじゃないか。
どんなやつでもかかってこいという感じですか。まあ、一部ブラウザは除きますが・・・

　そんなわけで、JavaScriptで何か重めの処理走らせてみよう。きっと超絶スピードでサクサクやってくれるはずだ！
というモチベーションの元、数独ソルバをjsで作ってみた。

数独をとかないと世界が破滅するようなシチュエーションで使ってみてください。
↓ここにあります。
http://kogecoo.sakura.ne.jp/scripts/dancing_sudoku.html

恐ろしいことにChromeでしか動作確認をしておりません。

以下駄文

書きなぐってポイ、という感じなので色々と不備があるかもしれません。
検算とか手でやったわけじゃないので、ちゃんと解けているかどうかは保障しません。。。
jQuery使っているのでリッチなブラウザ使ってください。コア部分は多分ECMA 3rdでも通じるくらい何もしていないので、誰か携帯用とか書きたければ書いてください。

　数独の解を探すアルゴリズムは、Knuth先生が広告塔をやったDancing Linksというアルゴリズムを使いました。学生のときにJavaで書かされたものを書き直す形で最初はじめたのですが、最終的には原型をとどめていません。
　Dancing Linksは、縦方向と横方向に双方向リンクをもつノードを2次元平面状に並べた構造で実現されていて、Exact Coverな問題に対するバックトラッキングの高速化をするアルゴリズムと知られていると僕は記憶しています。細かい話は元論文が非常に分かりやすいので、興味があればぜひ。
　また、数独のExact Coverとしての解釈はWikipediaが、これまためちゃくちゃ分かりやすいので、こちらも興味があればぜひ。

ちなみにDancing Linksをwebを探すと実装がかなりたくさんあります。ちょっと前は全然無かったんだぜ…
java, c, c++, python, haskell...適用先として面白いんでしょうね。。。

追記

ipod touchの第4世代で動いた！けど画面が足りてない！