GWで実家に帰ったとき、父がナンプレにハマッってました。
数独とも言われるパズルです。数独はどっかの商標かな。
私自身は、そんなに解いたことはありません。多くて10題くらいでしょう。
父が解いてるのを見て、コンピュータで解くための
解法アルゴリズムを考えてしまう辺りが私の性(さが)なんでしょう。
ナンプレ。まぁご存知だとは思いますが簡単にルールを言うと
・9*9のマス目に数字を入れる。数字は1~9。
・3*3のブロックでマス目を9グループに区切る。
・縦横、そして3*3のグループ内に同じ数は入らない。
こんな感じかな?
で、解法なんですが、全部頭の中で考えただけなので検証まったくしてません。
だから間違ってるかもw
1)総当り法
全てのマス目に数字を入れるパターンを全部調べる。
9*9のマス目それぞれに1~9が入るので、9^81通り?
時間さえ掛ければ必ず解けるはず。
でも美しくない!バーッド!
2)仮置き法
父が問題を解くプログラムを見たことがあると言ってました。
左上から右に順番にルールに適合する範囲で数字を仮置きしていくもの。
右端まで行ったら一段下がってまた右端まで。
ルールに適合する数字が無いなら、直前のマスの数字が間違っている。
この場合は一つ戻ってやり直し。
当然、ドンドン戻る場合もあります。
総当りでは全部置いてから整合性チェックしてましたが
こっちは置きながらチェック。
判定しないパターンがあるから、総当りよりは短時間で
これも必ず解けるはず。でもこれも美しくない。
3)消去法
普通の人が問題を解く場合の考え方はこれでしょう。
あるマス目に着目して、そのマス目に「入らない」数字を調べる。
入らない数字が8個なら、そのマス目に入るのは残り1つの数字になります。
で、どうやって消去していくか、というのが重要なのです。
3-1)位置類推法
同じ数字同士を比較して、位置を類推する方法です。
例えば、同じ数字が8個あれば残り1個の場所は決まります。
もっと狭く言うと、左上のブロックに「1」が無く
中上、右上、左中、左下の4つのブロックに「1」があれば
左上の「1」の場所は確定します。
一見、消去法に見えませんが、4つの「1」から左上のブロックでは
8マスが「1」の可能性が消去されています。
3)の消去法はマス目に対して「唯一」の解が決定する場合なら解けます。
ただし、唯一に決定しない場合は解けない。
4)グループ類推法
分かりにくいので、例を挙げて説明。
同じ3*3マスのブロック内とします。
左上のマス目の数字候補が{1,2}、右上の数字候補が{1,2}
左下の候補が{1,2,3}。
この情報から、左下は3だと分かります。
これを一般化すると…、
同じグループ内(ブロック・縦・横問わず)において
数字n個による同じ組み合わせ候補(A群とする)がn+1個マス目にある場合
そのマス目の中で候補がA群以外に唯一存在する場合(bとする)は、
bがそのマス目の解である。
こんなところでしょうか。
この方法を使っても解けない問題はあるでしょう。
どんな問題になるかは分かりません。
(問題としてどうか、という議論はありますが)
回転・鏡像・可換な問題は本質が同じなのに複数の表現があることになるので
その場合は、これだけでは解けないことになります。
極端な例として中央1マスにしか数字が無い場合を考える。
ある解が見つかったとして…
90度回転させても、やはり解としては正しい⇒回転
左右反転させても、やはり解としては正しい⇒鏡像
左右の3ブロックずつをまるごと入れ替えても(略)⇒可換
このチェックは面倒ですね。保留とします。
以上の方法を組み合わせて、解法を考える。
①マス目を(3)の方法で埋めていく。
②①により唯一の数字が決まるマス目がなくなるまで繰り返す。
③(3)で埋まるマス目が無い場合、(4)の方法でマス目を埋める。
④1つ埋めた状態から①に戻って再度埋めていく。
⑤③でも一つも埋めることが出来ない場合、さぁどうしよう。
空いてるマス目に対し、ここから仮置き法を行う。
多分、これで解けはするはず。
でも、まだエレガントな方法があるんじゃないかなぁ。
そこで仮置き法を行う順番を工夫するという手を考える。
(左上からではなく、解候補が少ないマス目から置くとか)
うん、少しそれを考えてみよう。
⑥解候補数が最も小さいマス目を調べる(必然的に候補数は2以上)。
⑦数字を仮置き。
⑧=①’マス目を(3)の方法で埋めていく。
⑨=②’①’により唯一の数字が決まるマス目がなくなるまで繰り返す。
ただし、矛盾が発生した場合は、⑦で置いた数字が間違っていたことになる。
別の数字の仮置きをして⑧に戻る。
⑩=③’(4)の方法でマス目を埋める。
ただし、矛盾が発生した場合は、⑦で置いた数字が間違っていたことになる。
別の数字の仮置きをして⑧に戻る。
⑪=④’その状態から①’に戻って再度埋めていく。
⑫③’でも一つも埋めることが出来ない場合、さぁどうしよう。
仮置きにレベルを考える。
⑦の仮置きをレベル1とし、⑬の仮置きをレベル2とする。
⑦~⑪と同様のプロセスを仮置きレベルを上げて⑬~⑰で行う。
矛盾があれば⑬に戻る。⑬で全ての候補が誤りであることが分かれば
仮置きレベルを一つ下げて、その仮置き(ここでは⑦)が誤りだったと判断する。
ルールに従った単純な仮置きよりも
仮置きで確定できる情報を一通り精査して真偽を確認したほうが
エレガントな気がします。
あ~眠い。この文章ちゃんとまとまってるのかなぁ?
脳内シミュレーションしかしてないので間違い指摘歓迎。
数独とも言われるパズルです。数独はどっかの商標かな。
私自身は、そんなに解いたことはありません。多くて10題くらいでしょう。
父が解いてるのを見て、コンピュータで解くための
解法アルゴリズムを考えてしまう辺りが私の性(さが)なんでしょう。
ナンプレ。まぁご存知だとは思いますが簡単にルールを言うと
・9*9のマス目に数字を入れる。数字は1~9。
・3*3のブロックでマス目を9グループに区切る。
・縦横、そして3*3のグループ内に同じ数は入らない。
こんな感じかな?
で、解法なんですが、全部頭の中で考えただけなので検証まったくしてません。
だから間違ってるかもw
1)総当り法
全てのマス目に数字を入れるパターンを全部調べる。
9*9のマス目それぞれに1~9が入るので、9^81通り?
時間さえ掛ければ必ず解けるはず。
でも美しくない!バーッド!
2)仮置き法
父が問題を解くプログラムを見たことがあると言ってました。
左上から右に順番にルールに適合する範囲で数字を仮置きしていくもの。
右端まで行ったら一段下がってまた右端まで。
ルールに適合する数字が無いなら、直前のマスの数字が間違っている。
この場合は一つ戻ってやり直し。
当然、ドンドン戻る場合もあります。
総当りでは全部置いてから整合性チェックしてましたが
こっちは置きながらチェック。
判定しないパターンがあるから、総当りよりは短時間で
これも必ず解けるはず。でもこれも美しくない。
3)消去法
普通の人が問題を解く場合の考え方はこれでしょう。
あるマス目に着目して、そのマス目に「入らない」数字を調べる。
入らない数字が8個なら、そのマス目に入るのは残り1つの数字になります。
で、どうやって消去していくか、というのが重要なのです。
3-1)位置類推法
同じ数字同士を比較して、位置を類推する方法です。
例えば、同じ数字が8個あれば残り1個の場所は決まります。
もっと狭く言うと、左上のブロックに「1」が無く
中上、右上、左中、左下の4つのブロックに「1」があれば
左上の「1」の場所は確定します。
一見、消去法に見えませんが、4つの「1」から左上のブロックでは
8マスが「1」の可能性が消去されています。
3)の消去法はマス目に対して「唯一」の解が決定する場合なら解けます。
ただし、唯一に決定しない場合は解けない。
4)グループ類推法
分かりにくいので、例を挙げて説明。
同じ3*3マスのブロック内とします。
左上のマス目の数字候補が{1,2}、右上の数字候補が{1,2}
左下の候補が{1,2,3}。
この情報から、左下は3だと分かります。
これを一般化すると…、
同じグループ内(ブロック・縦・横問わず)において
数字n個による同じ組み合わせ候補(A群とする)がn+1個マス目にある場合
そのマス目の中で候補がA群以外に唯一存在する場合(bとする)は、
bがそのマス目の解である。
こんなところでしょうか。
この方法を使っても解けない問題はあるでしょう。
どんな問題になるかは分かりません。
(問題としてどうか、という議論はありますが)
回転・鏡像・可換な問題は本質が同じなのに複数の表現があることになるので
その場合は、これだけでは解けないことになります。
極端な例として中央1マスにしか数字が無い場合を考える。
ある解が見つかったとして…
90度回転させても、やはり解としては正しい⇒回転
左右反転させても、やはり解としては正しい⇒鏡像
左右の3ブロックずつをまるごと入れ替えても(略)⇒可換
このチェックは面倒ですね。保留とします。
以上の方法を組み合わせて、解法を考える。
①マス目を(3)の方法で埋めていく。
②①により唯一の数字が決まるマス目がなくなるまで繰り返す。
③(3)で埋まるマス目が無い場合、(4)の方法でマス目を埋める。
④1つ埋めた状態から①に戻って再度埋めていく。
⑤③でも一つも埋めることが出来ない場合、さぁどうしよう。
空いてるマス目に対し、ここから仮置き法を行う。
多分、これで解けはするはず。
でも、まだエレガントな方法があるんじゃないかなぁ。
そこで仮置き法を行う順番を工夫するという手を考える。
(左上からではなく、解候補が少ないマス目から置くとか)
うん、少しそれを考えてみよう。
⑥解候補数が最も小さいマス目を調べる(必然的に候補数は2以上)。
⑦数字を仮置き。
⑧=①’マス目を(3)の方法で埋めていく。
⑨=②’①’により唯一の数字が決まるマス目がなくなるまで繰り返す。
ただし、矛盾が発生した場合は、⑦で置いた数字が間違っていたことになる。
別の数字の仮置きをして⑧に戻る。
⑩=③’(4)の方法でマス目を埋める。
ただし、矛盾が発生した場合は、⑦で置いた数字が間違っていたことになる。
別の数字の仮置きをして⑧に戻る。
⑪=④’その状態から①’に戻って再度埋めていく。
⑫③’でも一つも埋めることが出来ない場合、さぁどうしよう。
仮置きにレベルを考える。
⑦の仮置きをレベル1とし、⑬の仮置きをレベル2とする。
⑦~⑪と同様のプロセスを仮置きレベルを上げて⑬~⑰で行う。
矛盾があれば⑬に戻る。⑬で全ての候補が誤りであることが分かれば
仮置きレベルを一つ下げて、その仮置き(ここでは⑦)が誤りだったと判断する。
ルールに従った単純な仮置きよりも
仮置きで確定できる情報を一通り精査して真偽を確認したほうが
エレガントな気がします。
あ~眠い。この文章ちゃんとまとまってるのかなぁ?
脳内シミュレーションしかしてないので間違い指摘歓迎。
あー懸賞付のやつ専門にやってるプロとかには需要あるか・・・
そんなもの関係ないっすw
効率の良い解法を確立することに意義があるのです。
登山家の山に登る理由が「そこに山があるから」みたいなものですね^-^
ぜんぜんブログ関係見てなかったw
ちゃんと更新しなさいw
おやすみなさいw
帰宅が遅くなってきたとかいうのもあるけど