昨日も数独ソルバー野続を作業していましたが、もう無理だ！プログラムにバグがあって必ずフリーズしてしまう！と頭がパンクして、昨日は京王のダイヤDBを作って眺める作業に逃避してしまいました。

疲れたので答え見てやる！とweb検索すると引っかかったのが次のサイトでした。

ame%20class=

 

12761194 shares

http://ame%20class=

http://ame%20class=

nihemak.hatenablog.com

例えば空のマス目の数が30、そこに入る候補の数の平均が4になるとすれば探索範囲数は下記のようにしぼられます。(これでも処理時間は相当かかります。)
　42391158275216203514294433201(9の3乗)→1152921504606846976(4の30乗) 

ああ、これは時間がかかるのも当たり前ですね。9*9のマスしかないならブラウザ上でも処理時間は全然かからないでしょ、と思っていたのが甘かった。天文学的数字になるんじゃしょうがないです。

私がとった方法は「候補が複数あればそれに応じて分岐を作成、数字を入れていって矛盾があればその分岐は無効、最後まで残った分岐を採用」というやり方ですが、これは分岐が天文学的数字になってメモリも処理時間もバカみたいに食います。で、ブラウザに「反応が無いですよ」と言われてしまってアウトとなりました。

この記事を読んで、数独ソルバーというのはルールの実装は実に単純なので「いかにして処理の無駄をなくし正解を素早く見つけるか」が勝負になるということがわかりました。

来週もチャレンジしてみよう。

10行で解くおそろしいコードもあるらしいです。すごい

Qiita

ES6 generatorで実装する10行数独ソルバー - Qiita

http://qiita.com/bellbind/items/d735b5e189f222fdef71

最近、(http://www.gizmodo.jp/2015/05/c.html)という話がありました(拡張子がcppなだけの(https://dr...

ブラウザ上で実用になる程度のjavascriptのコードが書けたら自分としては満足です。

(追記)K, Perl, Rubyなら2行なんてバカみたいなコードもあります。世界広すぎ

ShortestSudokuSolver

Tweet