4x4数独の解答列挙 - kozima の雑記

エロと風俗情報満載どう抜く？の、問題数ではなく解答数の数え上げを紙と鉛筆でやってみました。

とりあえず分類

最上段が 1234 の場合を考える。

1 2 3 4
- - - -
- - - -
- - - -

二段目まで埋めると次の四通り。

1 2 3 4   1 2 3 4   1 2 3 4   1 2 3 4
3 4 1 2   3 4 2 1   4 3 1 2   4 3 2 1
- - - -   - - - -   - - - -   - - - -
- - - -   - - - -   - - - -   - - - -

両端の二つのパターンは、右二列を入れ替えて 3, 4 を交換する操作で一対一に対応する。
真ん中の二つも同様。

最初の形の解

一列目の埋め方が二通り。

1 2 3 4   1 2 3 4
3 4 1 2   3 4 1 2
2 - - -   4 - - -
4 - - -   2 - - -

それぞれに対して三列目が一意に決まる。

1 2 3 4   1 2 3 4
3 4 1 2   3 4 1 2
2 - 4 -   4 - 2 -
4 - 2 -   2 - 4 -

これらに対して二列目の埋め方がやはり二通りずつあり、結局以下の四通り。

1 2 3 4   1 2 3 4   1 2 3 4   1 2 3 4
3 4 1 2   3 4 1 2   3 4 1 2   3 4 1 2
2 1 4 3   4 1 2 3   2 3 4 1   4 3 2 1
4 3 2 1   2 3 4 1   4 1 2 3   2 1 4 3

二番目の形の解

一列目の埋め方が二通り。

1 2 3 4   1 2 3 4
3 4 2 1   3 4 2 1
2 - - -   4 - - -
4 - - -   2 - - -

それぞれについてもうひとつの 2, 4 の場所が一意に決まる。

1 2 3 4   1 2 3 4
3 4 2 1   3 4 2 1
2 - 4 -   4 - - 2
4 - - 2   2 - 4 -

これから他の場所も一意に決まる。

1 2 3 4   1 2 3 4
3 4 2 1   3 4 2 1
2 1 4 3   4 3 1 2
4 3 1 2   2 1 4 3

結論

というわけで、 (2+4) * 2 * 4! = 288 通りあることがわかりました。めでたしめでたし。