バックトラック
１２月４日火曜日、曇り
曇っていたとおもう。たぶん（ずっとオフィスに閉じこもってコードを書いていたので天気を知らない。夜に出たら小雨が降っていた）
＊ ＊ ＊
なんだかんだで「探索」プログラムがどうにも苦手。
かつて Qiita で探索問題を解く、なんて記事をあげたのも、この苦手意識をどうにかしたいから。
さて。
一昨日だったかに書こうとおもって投げだしていた数独ソルバー、バックトラック版を書き上げた。
バックトラックに関しては Wikipedia にも解説がある。
バックトラッキングのアルゴリズムは、単に正しい解を得るまで可能な組み合わせを試していくだけであり、一種の深さ優先探索である。探索の際、ある組み合わせが解でなかったなら、探索木をたどって戻り別の組み合わせを試す。その組み合わせを試しても解でなかった場合、さらに探索木を戻り、新たな組み合わせを試す。探索木を全部サーチしたとき、探索は失敗して終了する。
数独はまさにこの技法の練習のためにあるんじゃないかとおもえるほど、しっくりハマる。
現時点での実装は非常にナイーブで、効率化はまったくしていない。
つまり数字を左上角から順に埋めることしかしていない。
行、列、ブロックのそれぞれで、すでに置かれている数字は候補から外せるので、これを考慮に入れると効率があがる。
また Wikipedia にあるように、次の数字を仮置きする場所を候補が少ない中から選ぶことで、これまた効率よく枝刈りが進むはず。
さらにこの候補は、すでに置かれた数字のうち一番多く置かれているものから選ぶとよさそう。
ベースはできたので、枝刈りの効率を測る方法を考えたい。
そしていくつかの効率向上手段を実装して、それぞれがどのように効率をあげるのか（もしくは却って悪くするのか）を比較できるようにしたい。
＊ ＊ ＊
これとは違ったアプローチも、ぼんやりと頭にあるので実装してみたい。
数独は、いくつかの数字が置かれた状態で始まる。
ところである数字が８つ置かれていたら残りは１箇所に定まる。
７つだったら行と列の入れ替えの自由度が上がるので ……２通り？
ともかく、すでに置かれた数字の位置から逆算して、置けるパターンのテンプレートがいくつか定まるはず。
各数字についてテンプレートの候補を挙げておき、それぞれのテンプレート候補の組み合わせで全てのマスが埋まるものを解として選択する ……みたいな解法。
これはテンプレートの数がどれだけになるかが勝負。
いくつか試してみて、あまりにも膨大になるようなら手をつけないほうがよいだろう。（でも試してみたい。ビットマップのパターンを照合して埋まったものが解ですよ〜 って、いかにも計算機の仕事っぽい）
この記事が気に入ったらサポートをしてみませんか？