変形魔方陣
一週間、空いてしまいました。
ちょっとリハビリのために、今日はコンピューターパズル問題の話。
もちろん数学のエッセンス多めです。キーワードは、数学的裏付けと式変形。
変形魔方陣
かつて存在した、「Cマガジン」という雑誌の、コンピューターパズルのコーナー「Cマガ電脳クラブ」から、個人的に思い入れの深い1問*1。
問題は以下の通り（出典：Cマガジン 1998年8月号*2）：
+---+---+---+ | A | B | C | A + B + D + E = N +---+---+---+ B + C + E + F = N | D | E | F | D + E + G + H = N +---+---+---+ E + F + H + I = N | G | H | I | +---+---+---+ 上の図のA～Iに、1～9の数を1つずつ入れて、2x2の4つの小正方形のマスの中の数の和が一定値(=N)になる（上右の4つの式がすべて成立する）ような配置を見つけてください。 全部で何通りあるでしょう？ （ただし、回転・反転して同じ配置になるものは1つと数えます（区別しません））
普通「魔方陣」というと、縦・横・ななめの各列の和が一定値（これを『定和』と言います）になる、というもの。
その条件を少し変形した魔方陣、ということです。
よくある解答
解答を導き出すだけなら、結構簡単です。
1～9の順列を考えて、それが条件を満たすかどうか調べて、回転・反転解になっていないか調べて、OKならカウントアップする。それだけで良いのですから。
ただしそれだと、あまりにも効率が悪くなってしまいます。そこで少しでも効率よくするために、例えば以下のような工夫を入れます。
- 回転・反転解を先に排除する（枝刈り1）
- なるべく早い段階で定和を決定し、そこから基準に合致しない組合せを排除する（枝刈り2）
これで行ってみましょう。コーディングしてみました。今回はPythonです。
def solve():
flgs = [False for i in range(9)]
arr = [0 for i in range(9)]
arr_idxs = [1, 3, 5, 7, 4, 0, 2, 6, 8]
def solver(i, n, cnt):
for idx in [m for m in range(9) if not flgs[m]]:
flgs[idx] = True
arr[arr_idxs[i]] = idx
if i == 8:
if arr[4] + arr[5] + arr[7] + arr[8] == n:
print_answer(arr)
cnt += 1
else:
if i == 5:
n = arr[0] + arr[1] + arr[3] + arr[4]
if chkOK(arr, i, n):
cnt = solver(i + 1, n, cnt)
flgs[idx] = False
return cnt
cnt = solver(0, 0, 0)
print "Count: %d" % cnt
return cnt
def chkOK(arr, i, n):
if i == 1:
return arr[1] < arr[3] # E1
elif i == 2:
return arr[3] < arr[5] # E1
elif i == 3:
return arr[1] < arr[7] # E1
elif i == 6:
return arr[1] + arr[2] + arr[4] + arr[5] == n # E2
elif i == 7:
return arr[3] + arr[4] + arr[6] + arr[7] == n # E2
return True
def print_answer(arr):
print "%2d%2d%2d\n%2d%2d%2d\n%2d%2d%2d\n" % tuple(map(lambda x: x+1, arr))
if __name__=='__main__':
solve()
再帰を利用したらわりとコンパクトにまとまりました。もちろんちゃんと正しい答えが出ます。
ソース中のchkOK関数が枝刈りをしているところで、「#E1」が「枝刈り1」、「#E2」が「枝刈り2」です。
実行時間を計ってみました（無駄に benchmarker モジュールを利用）。
## user sys total real solve x 100 8.3400 0.0100 8.3500 8.3415
100回繰り返して 8.34秒。つまり、だいたい 0.083秒。うん。これでも決して遅くはないですね。
でも今回は、この速さには満足せず、「もっと効率よく早く答えが出せないか」を、数学的観点から考えてみましょう。
数学的考察
前節で、何気に9つの数を0～8で処理して、表示するときだけ+1して1～9となるようにしています。
以下もこの前提で進めます。
改めて、今与えられている条件は以下の4つの式です。
A + B + D + E = N …(1) B + C + E + F = N …(2) D + E + G + H = N …(3) E + F + H + I = N …(4)
この4つの式から、以下の式が導かれます。
(A + C + G + I) + 2(B + D + F + H) + 4E = 4N …(5)
はい、全部辺々足し合わせただけ（(5)=(1)+(2)+(3)+(4)）です。簡単ですね。
あと、A～Iは0～8の数が1つずつ出てくるはずなので、以下も成り立ちます。
A + B + C + D + E + F + G + H + I = 36 …(6)
(5) から (6) を引いてみましょう。
B + D + F + H + 3E = 4N - 36 …(7)
変形するとこうなります。
N = (36 + B + D + F + H + 3E) / 4 …(7)'
これが何を意味しているか、分かりますか？
N（＝定和）が、B, D, E, F, H の5つの文字の式で表されています。
B, D, F, H は上下左右の数、E は真ん中の数です。
そう。
この魔方陣の定和は、上下左右と真ん中の数が決まればもう決まってしまうのです。
前節のプログラムでは、上下左右真ん中に加えて、左上（A）まで決めた時に定和を決めていた（N=A+B+D+E だから）のですが、実はその必要はなかった、ということですね。
- 5つの数を決めたところで定和を求める（効率化1）
さらに式(7)'によく注意すると、4で割っていますがその商が整数になる保証はありません。でも定和って整数のはずですよね。つまりここでもまた枝刈りができるわけです。
- 求めた定和が整数かどうか確認し、整数にならないものは排除する（枝刈り3）
残るは四隅の数ですが、上下左右の数が決まって、定和も求まっています。だったらそこから引き算するだけで出ちゃいます。
A = N - B - D - E …(1)' C = N - B - E - F …(2)' G = N - D - E - H …(3)' I = N - E - F - H …(4)'
あとはこれらが、0～8の数のうちで、今までに決まった数（B, D, E, F, H）とかぶらないか確認するだけでOK。つまり。
- 四隅（A, C, G, I）は順列をすべて生成してチェックするのではなく、定和と他の数から算出し、妥当性をチェックする（効率化2）
さらにおまけ。
実は以下の式も成立します（証明は読者への宿題にしますｗ）。
A + I = C + G
I = C + G - A …(8)
ここから、四隅のうち3つの数が決まれば残り1つも算出できます。
私の解答
以上を踏まえて、解答プログラムを書きなおしてみました。
def solve():
flgs = [False for i in range(9)]
arr = [0 for i in range(9)]
arr_idxs = [1, 3, 5, 7, 4, 0, 2, 6, 8]
def solver(i, cnt):
rstart = 0
if i == 1 or i == 3:
rstart = arr[1] + 1
elif i == 2:
rstart = arr[3] + 1
rend = 9
if i == 0:
rend = 7
elif i == 1:
rend = 8
for idx in [m for m in range(rstart, rend) if not flgs[m]]: # E1
flgs[idx] = True
arr[arr_idxs[i]] = idx
if i == 4:
n4 = 36 + arr[1] + arr[3] + arr[5] + arr[7] + 3 * arr[4] # K1
if n4 % 4 == 0: # E3
n = n4 / 4
a0 = n - arr[1] - arr[3] - arr[4] #K2
a2 = n - arr[1] - arr[4] - arr[5] #K2
a6 = n - arr[3] - arr[4] - arr[7] #K2
#a8 = n - arr[4] - arr[5] - arr[7] #K2
a8 = a2 + a6 - a0
if len([m for m in range(9) if not (flgs[m] or m in [a0,a2,a6,a8])])==0: #K2
arr[0] = a0
arr[2] = a2
arr[6] = a6
arr[8] = a8
print_answer(arr)
cnt += 1
else:
cnt = solver(i+1, cnt)
flgs[idx] = False
return cnt
cnt = solver(0, 0)
print "Count: %d" % cnt
return cnt
def print_answer(arr):
print "%2d%2d%2d\n%2d%2d%2d\n%2d%2d%2d\n" % tuple(map(lambda x: x+1, arr))
if __name__=='__main__':
solve()
何気に枝刈り1も少し工夫して効率化してたりします。
実行時間を計ってみました。
## user sys total real solve x 100 0.6300 0.0100 0.6400 0.6346
同じ100回の繰り返しで0.63秒。1回あたり約0.006秒。1/10以下になりました。
私が応募した回答は、ほぼこれと同じ内容をC言語で記述したものでした。
（さらなる効率化のために、再帰を使わずループをベタにネストしていたような気がします）
DOSでBCC32か何かを使用して、実行時間は1000回実行して数秒台（つまり0.00X秒）だったと思います。
まとめ
数学というより、今回やっていることは単純な式変形だけです。
でも、それによって「今まで順番に調べてあてはめてきたもの（例：定和）が、ある程度までは実は途中でもう決まってしまう」ことが分かりました。今回は、その「もう分かっていることをうまく利用して無駄な検索を減らす」という効率化の話でした。
今回は3×3なので検索量も元々たかが知れていましたが、もっと大きな量を検索しなければいけないときは、以下に効率よく無駄を減らせるか、はとても重要になってきます。
