魔方陣のように数字を入れる総パターン

質問

□□□□ 4
□□□□ 4
□□□□ 4
□□□□ 4
４ ４ ４ ４
こんな感じで４×４のマスを置いて、
このマスの中に0-4の数字を自由に入れる
ただし、すべてのマスに数字を入れたときの縦横の数字合計が
すべて４ずつになるパターンはどれだけ作れるでしょうか？

単純に組み合わせの要領で計算しようとすると二方向へ対処する事が出来ませんでした。
どのようにすれば解くことが出来ますか？

回答No.1

nag0720

プログラムを組んで総当たりで調べるのが一番早いでしょうね。
エクセルのVBAでコードを書いてみたら、10147通りありました。

計算で出すとしたら、とりあえず２つの方法が浮かびました。

１つは、

４×４のマスを、２×２の４つに分割して、
２×２の数の合計の組み合わせを考えると、次の９通りになります。
80　　71　　62　　53　　44　　35　　26　　17　　08
08　　17　　26　　35　　44　　53　　62　　71　　80

２×２の数の合計が8になる組み合わせは、
40　　31　　22　　13　　04
04　　13　　22　　31　　40
の５通りなので、
80
08
になる組み合わせの数は、5×5=25通り

２×２の数の合計が7になる組み合わせは、
40　　31　　31　　30　　30　　22　　21　・・・・
03　　12　　03　　13　　04　　21　　22　・・・・
などの16通りあり、
71
17
になる組み合わせの数は、7になる組み合わせが決まれば、1になる組み合わせも確定するので、16×16=256通り

というようにしていけば計算できます。
ただし、
62
26
の組み合わせは、6になる組み合わせが決まっても、2に組み合わせも複数あるかもしれないので、計算はさらに複雑になります。

もうひとつの方法は、

まず、マスの中に0か1の数字を入れて、縦横の合計が1になる組み合わせを考えます。
例えば、
1000
0100
0010
0001
や
1000
0100
0001
0010
などです。
他にも、各行を入れ替えたものも条件を満たすので、
全部で4!=24通りあります。

マスの中に0-4の数字を入れて、縦横の合計が4になる組み合わせは、
上記の24種類の中から４つ選んで足したのもになります。
例えば、
1000
0100
0010
0001
を４つ足せば、
4000
0400
0040
0004
になります。
その組み合わせの数は、24種類の中から４つ選ぶ重複組み合わせなので、
24H4=27C4=17550通り

ただし、この17550通りの中には、重複してカウントしているものがあります。
例えば、
1100
1100
0011
0011
は、
1000
0100
0010
0001
と
0100
1000
0001
0010
を足した場合と、

1000
0100
0001
0010
と
0100
1000
0010
0001
を足した場合の２通りあるので、この重複している分を差し引く必要があります。

どちらの方法にしてもかなりの時間をかけて丁寧に調べないと解けないでしょう。

お礼

ありがとうございます
2*2へ分割するという方法は目に鱗ですが、
組み合わせ的にはどうにもならない部分が出てしまうのですね。
ふと思いついたような問題なのに、かなり奥が深そう