ナンプレの対称性
ナンプレの対称性
ブロックに関するルールを除外することでナンプレがラテン方陣に含まれることがわかる。
全てのマスを埋めなければならない。
縦の列に同じ数字が重複してはならない。
横の列に同じ数字が重複してはならない。
盤面の数字を入れ替えることで同じ構造の回答を作成することができる。
$ 9!=362,880通り。
行(列)の置換と転置により同じ構造の回答を作成することができる。
盤面の管の置換により同じ構造の盤面を作成することができる。
$ (3!)^2=6^2通り
盤面の同じ管内の線を置換することで同じ構造の盤面を作成することができる。
1つの管に含まれる3線の置換は、
$ 3!=6通り。
6つの管それぞれで独立して線を置換できるため、
$ 6^6通り。
盤面の転置(行と列の入れ替え)で同じ構造の盤面を作成することができる。
$ 2通り。
置換と転置の組み合わせの総数は
$ 6^8\times2=3,359,232通り。
以上の操作を組み合わせることで同じ構造の盤面を全て作成することができる。
$ 9!\times6^8\times2=1,218,998,108,160通り。
補足:
行入れ替え後に転置する操作は、転置後に列入れ替えをする操作と同じ結果を得る。
列入れ替え後に転置する操作は、転置後に行入れ替えをする操作と同じ結果を得る。
上下反転は階入れ替えと行入れ替えの組み合わせで表現できる。
r1とr9を、r2とr8を、r3とr7を、r4とr6を入れ替える。
その結果、第1階と第3階が入れ替わる
左右反転は塔入れ替えと列入れ替えの組み合わせで表現できる。
c1とc9を、c2とc8を、c3とc7を、c4とc6を入れ替える。
その結果、第1塔と第3塔が入れ替わる
90度回転は転置後に左右反転、あるいは、上下反転後に転置すれば良い。
https://gyazo.com/029b53026dfd7400ce696087f40f487b
https://gyazo.com/4198b03ee9e06022f691a97de515e01a
https://gyazo.com/62a4d31627abc185d600539f14694824
右にあるのは同じ操作を画像に対して施したもの(操作を直感的に見るため)。
実際には操作を組み合わせた結果として同じ盤面に戻ることがあるため、同じ構造の盤面の個数は盤面によって異なる。
この操作で帰着できない互いに異なる解盤面の個数は既に数え上げられており、5,472,730,538 個あるらしい。
その上全ての解盤面を列挙したうえで 130GB に圧縮して保存した人が居るようだ。
http://winnie.kuis.kyoto-u.ac.jp/members/okuno/Public/IPSJ71-Inoue.pdf
最小ヒント数問題が解かれていない頃の物なので最後の章に最小ヒント数問題について言及されている。