数独

数独がSUDOKUというそのまんまな名前で英国で大流行らしいので、流行にあやかって久しぶりに解答プログラムを組んでみる。前にC言語で数バージョン作ったので、今回はRubyで作成。

速度ではCで作ったものには絶対に勝てないので、今回は配列(Array)を継承したクラスを使用して、なるべく配列の機能だけで作成した。

アルゴリズムとしては、ひたすら左上から埋めていき、破綻したら後戻りというお馬鹿なアルゴリズムで、ここにある問題で重複解をチェックしない場合でも5分程度かかる。Cの場合は重複解をチェックしても数秒のオーダーなので、軽く数百倍の差があることになる。ただ、実質50行程度、純粋なアルゴリズム部分は30行に満たないので、結構インパクトはあると思う。

Rubyバージョンは次の勉強会に向けての余興で、本命は問題の(半)自動生成ツールである。これについての考察は、またそのうち。

追記

数独ソルバーRuby手抜きバージョンをここにアップしました。