アルゴリズム解説
注意:ナンバープレースの解き方に触れています。読みたくない方はご注意ください。
基本
各マスについて1〜9で入る可能性がなくなった数字に×をつけていきます。
どこかのマスに入る数字が確定した時は、同じ行・同じ列・同じブロックにあるその数字に×をつけます。
解き方の手順
以下のステップで解いていきます。状況が進展した場合は第1ステップに戻ります(つまりなるべく単純なステップを用いて解くようにしています)。
Level1では1〜3ステップ、Level2では1〜5ステップのみしか用いないようになっています。Level3では1〜6のすべてのステップを用いて解こうとします。
第1ステップ
各行を見て、ある数字が入る可能性のあるマスが1ヶ所しか残っていない場合は、その数字を入れます。
列やブロックについても同じチェックをします。
第2ステップ
各マスを見て、入る可能性のある数字が1つしか残っていない場合は、その数字を入れます。
第3ステップ
各行を見て、ある数字(nとします)が入る可能性のあるマスが1つのブロックにしか残っていない場合は、そのブロックでいまチェックしている行以外のnに×をつけます。
同じことを、列に関してチェックします。
また、各ブロックから行や列を見て同様のチェックをします。
第4ステップ
各行を見て、ある2つのマスに残っている数字が両方とも2個で同じ数字であったら、その2つのマス以外にあるその2つの数字に×をつけます。
列やブロックについても同じチェックをします。
第5ステップ
各行を見て、ある2個の数字が入る可能性のあるマスが2マスしかない場合は、そのマスにある他の数字に×をつけます。
列やブロックについても同じチェックをします。
第6ステップ
この段階で、入る可能性が残っている数字が1個入ったと仮定します。この状態で1〜5のステップをくり返し、破綻が発生したら最初に入ったと仮定した数字に×をつけます。1〜5のステップを繰り返した結果、破綻せずにやることがなくなった場合はその数字は保留して、次の数字の仮定に入ります。
また、仮定した状態で全てのマスが矛盾なく埋まった場合はその盤面を覚えておき、また別の仮定に入ります。もしその後、別の解答を発見した場合は別解と判断します。
それでもやることがなくなった場合は諦めます。
もどる
|