或るプログラマの一生

会社の S 氏が、会社で配られている保険組合の冊子に載っている数独の問題が解けない、と言ってやってきた。以前解くプログラム作ってましたよね？って聞かれたけど作ったのはイラストロジックだし。もう。

数独はルールが単純で盤面も小さいため、プログラムで解いても面白くない（アルゴリズムを工夫しなくても十分早く解けてしまう）ので、あまりプログラムを作る気はしなかったのですが、まあ一応上のようなことを言われてしまったんで作ってみるか、と。
（パズルそのものが面白くない、と言っているわけではないので念のため）

スタンダードな数独のルールは以下のようになります。

• 盤面は 9×9 マスである。
• 盤面は 3×3 マスの小さなブロック（以下、単に「ブロック」） 9 個に分けられており、ブロックの境界は太線で表示される。
• 各マスには 1～9 までの数字が入る
• 各列・各行・各ブロック には 1～9 までの数字が 1 つずつ入る

で、これをそのまんまアルゴリズムにすると、

• 問題に書いてある数字の入っているマスは「入る数字が確定している」とする
• あるマスに入る数字が 1 種類しかありえない場合は、そこに「入る数字は確定している」とする
• 入る数字が確定しているマスができたら、そのマスが属する列・行・ブロックの中の（自分以外の）マスには、その数字は入らない
• 各列・各行・各ブロックにおいて、ある数字が入る可能性のあるマスが 1 つしかない場合は、そのマスに入る数字はその数字である

となります。小細工を一切せずにこのアルゴリズムを実装したら、最初に述べた問題は 0.5 秒で解けてしまいました（Core 2 Duo E6400 @3.00GHz）。なんだ普通に解けるじゃん S さん。プログラムの公開は後日…

スタンダードなものだけ解けるようなプログラムを書きましたが、改造するとしたら以下のような感じでしょうか。

• 問題をファイルから読み込めるようにする（とりあえず相談された問題を解ければいいやと思って、今のプログラムはソースに直接問題を書いてある）
• 9×9 だけでなく 16×16 や 25×25 といった大きい問題を扱う
• と思っていたら 12×12 なんて問題もあるらしいのでそれも
• ブロックの形が正方形/長方形ではない問題を扱う
• 9×9 の 2 つ以上の領域が一部重なったような形式の問題を扱う

4 番目や 5 番目なんか、どうやってファイルに問題を記述するのか謎ですが。誰かいい案があったら教えてプリーズ。