今回はパズル「変形魔方陣」の解法プログラムを Python3 で作ってみましょう。それでは問題です。
┌─┬─┬─┐ 式
│Ａ│Ｂ│Ｃ│ A + B + E + D = N
├─┼─┼─┤ B + C + F + E = N
│Ｄ│Ｅ│Ｆ│ D + E + H + G = N
├─┼─┼─┤ E + F + I + H = N
│Ｇ│Ｈ│Ｉ│ A + C + I + G = N
└─┴─┴─┘
図 : 変形魔方陣
上図の A から I の場所に 1 から 9 までの数字をひとつずつ配置します。図では、A - B - E - D のように 2 * 2 マスの正方形が 4 つ、大きな正方形 (A - C - I - G) がひとつあります。魔方陣は縦横斜めの合計が等しくなるように数字を配置しますが、今回は上図の式で表すように、正方形の頂点の合計が等しくなるような配置を見つけてください。
出典は 『Ｃマガ電脳クラブ第 92 回 変形魔方陣』, C MAGAZINE 1998 年 8 月号, ソフトバンク です。Ｃマガ電脳クラブの問題は、2 * 2 マスの数字の合計が等しくなることが条件でしたが、今回は大きな正方形も条件に加えてみました。
Ａ
／ ＼ A + B + D + F = 20
Ｂ Ｃ
／ ＼ A + C + E + I = 20
Ｄ Ｅ
／ ＼ F + G + H + I = 20
Ｆ───Ｇ───Ｈ───Ｉ
図 : 変形魔方陣
上図の三角形の A から I の場所に 1 から 9 までの数字をひとつずつ配置します。直線上にある 4 つの数字の和が、3 本の直線で 20 になる配置を求めてください。
┌─┬─┬─┐
│Ａ│Ｂ│Ｃ│ 式
├─┼─┼─┤ A + B + C = N
│Ｄ│ │Ｅ│ A + D + F = N
├─┼─┼─┤ C + E + H = N
│Ｆ│Ｇ│Ｈ│ F + G + H = N
└─┴─┴─┘
図 : 変形魔方陣
上図の A から H の場所に 1 から 8 までの数字をひとつずつ配置します。4 辺の合計が等しくなるような配置を見つけてください。なお、合計の値 (N) は 12, 13, 14, 15 の 4 通りの場合があります。
ところで、問題３は数字 (1, 2, 3, 4, 5, 6, 7, 8) を使いましたが、数字を奇数 (1, 3, 5, 7, 9, 11, 13, 15) にする、または、数字を偶数 (2, 4, 6, 8, 10, 12, 14, 16) にするとどうなるでしょうか。実は、問題３の答えがわかると簡単に解くことができます。答えを見る前に、ちょっと考えてみてくださいね。
┌─┬─┬─┐
│Ａ│Ｂ│Ｃ│ 式
├─┼─┼─┤ A + B + C = N
│Ｄ│ │Ｅ│ A + D + F = N
├─┼─┼─┤ C + E + H = N
│Ｆ│Ｇ│Ｈ│ F + G + H = N
└─┴─┴─┘
図 : 素数の変形魔方陣
上図の A から H の場所に素数 (3, 5, 7, 11, 13, 17, 19, 23) をひとつずつ配置します。4 辺の合計が等しくなるような配置を見つけてください。なお、合計の値 (N) も素数になります。
┌─┬─┬─┐
│Ａ│Ｂ│Ｃ│ 式
├─┼─┼─┤ A + B + C = N
│Ｄ│ │Ｅ│ A + D + F = N
├─┼─┼─┤ C + E + H = N
│Ｆ│Ｇ│Ｈ│ F + G + H = N
└─┴─┴─┘
図 : 変形魔方陣
上図の A から H の場所に 2 と 5 を除く 0 から 9 までの数字 (0, 1, 3, 4, 6, 7, 8, 9) をひとつずつ配置します。4 辺の合計が等しくなるような配置を見つけてください。
それではプログラムを作りましょう。最初に順列を生成する関数 permutations() を作ります。
リスト : 順列の生成
def permutations(check1, check2, xs, ps = [], print_board = print):
if len(ps) == len(xs):
if check1(ps): print_board(ps)
else:
for x in xs:
if x in ps or check2(ps, x): continue
ps.append(x)
permutations(check1, check2, xs, ps, print_board)
ps.pop()
引数 check1, check2, print_board は関数です。check1() は解の条件を満たしているかチェックします。check2() は枝刈りの条件をチェックします。print_board() は盤面を表示します。引数 xs は選択する要素、ps は選択した要素を格納します。
ps と xs の長さが等しい場合、すべての要素を選択しました。順列がひとつ完成したので、check1() を呼び出して条件を満たしているかチェックします。xs から要素 x を選ぶときは、ps に xs が無いことと、枝刈りの条件 check2() を満たしていないことを確認します。
解法プログラムは次のようになります。
リスト : 変形魔方陣１
# 盤面
# 0 1 2
# 3 4 5
# 6 7 8
# ５つの枠
line01 = [
[0,1,3,4], [1,2,4,5], [3,4,6,7],
[4,5,7,8], [0,2,6,8]
]
# 条件のチェック
def check011(ps):
def add(a,b,c,d):
return ps[a] + ps[b] + ps[c] + ps[d]
xs = [add(*ls) for ls in line01]
return xs.count(xs[0]) == 5
# 重複解の排除
def check012(ps, x):
if len(ps) == 2 and ps[0] > x: return True
if len(ps) == 6 and ps[2] > x: return True
if len(ps) == 8 and ps[0] > x: return True
return False
# 問題１
def solver01():
permutations(check011, check012, range(1, 10))
リスト line01 に 5 つの枠 (正方形) を定義します。関数 check011() は 5 つの枠の合計値が等しければ True を返します。関数 check012() は重複解を排除するための条件をチェックします。これは「魔方陣」で説明した方法と同じです。あとは permutations() を呼び出すだけです。
対称解 (回転解と鏡像解) を除くと、解は 1 通りしかありません。
>>> solver01() [1, 8, 3, 6, 5, 4, 7, 2, 9]
┌─┬─┬─┐ │１│８│３│ ├─┼─┼─┤ │６│５│４│ ├─┼─┼─┤ │７│２│９│ └─┴─┴─┘
最初に重複解のチェック方法を説明します。次の図を見てください。
０
／ ＼
１ ８
／ ＼
２ ７
／ ＼
３───４───５───６
図 : 変形魔方陣の盤面
変形魔方陣の場合、回転解が 3 種類あって、鏡像解が 2 種類あります。3 つの頂点の大小関係をチェックすることで、これらの対称解を排除することができます。盤面を配列 ps で表すことにすると、具体的には次の条件を満たす解を探します。
ps[0] < ps[3] < ps[6]
このほかに、頂点の間にある 2 つの数字を入れ替えただけの解もあります。これらを重複解と考えて排除することにしましょう。具体的には、次の条件を追加します。
ps[1] < ps[2] ps[4] < ps[5] ps[7] < ps[8]
このように、数字の大小関係をチェックすることで、重複解を排除することができます。プログラムは次のようになります。
リスト : 変形魔方陣２
# 直線
line02 = [
[0,1,2,3], [3,4,5,6], [6,7,8,0]
]
# 条件のチェック
def check021(ps):
def add(a,b,c,d):
return ps[a] + ps[b] + ps[c] + ps[d]
xs = [add(*ls) for ls in line02]
return xs[0] == 20 and xs.count(xs[0]) == 3
# 重複解の排除
def check022(ps, x):
if len(ps) == 2 and ps[1] > x: return True
if len(ps) == 3 and ps[0] > x: return True
if len(ps) == 5 and ps[4] > x: return True
if len(ps) == 6 and ps[3] > x: return True
if len(ps) == 8 and ps[7] > x: return True
return False
# 問題２
def solver02():
permutations(check021, check022, range(1, 10))
>>> solver02() [1, 6, 8, 5, 2, 4, 9, 3, 7] [2, 4, 9, 5, 1, 6, 8, 3, 7] [2, 6, 7, 5, 3, 4, 8, 1, 9] [3, 4, 8, 5, 2, 6, 7, 1, 9] [4, 2, 9, 5, 1, 8, 6, 3, 7] [4, 3, 8, 5, 2, 7, 6, 1, 9]
解は全部で 6 通りになりました。
ところで、直線の値は 20 のほかにもいくつかあります。プログラムを次のように修正するだけで簡単に求めることができます。
リスト : 変形魔方陣２ (A)
def check021a(ps):
def add(a,b,c,d):
return ps[a] + ps[b] + ps[c] + ps[d]
xs = [add(*ls) for ls in line02]
return xs.count(xs[0]) == 3
def print_board2(ps):
print(f'{sum(ps[:4])}: {ps}')
def solver02a():
permutations(check021a, check022, range(1, 10), [], print_board2)
それでは、実行結果を示します。
>>> solver02a() 17: [1, 5, 9, 2, 4, 8, 3, 6, 7] 19: [1, 5, 9, 4, 2, 6, 7, 3, 8] 17: [1, 6, 8, 2, 5, 7, 3, 4, 9] 19: [1, 6, 8, 4, 3, 5, 7, 2, 9] 20: [1, 6, 8, 5, 2, 4, 9, 3, 7] 20: [2, 4, 9, 5, 1, 6, 8, 3, 7] 19: [2, 5, 9, 3, 1, 8, 7, 4, 6] 20: [2, 6, 7, 5, 3, 4, 8, 1, 9] 19: [2, 6, 8, 3, 4, 5, 7, 1, 9] 21: [3, 2, 9, 7, 1, 5, 8, 4, 6] 20: [3, 4, 8, 5, 2, 6, 7, 1, 9] 21: [3, 4, 8, 6, 1, 5, 9, 2, 7] 21: [3, 5, 6, 7, 2, 4, 8, 1, 9] 21: [3, 5, 7, 6, 2, 4, 9, 1, 8] 20: [4, 2, 9, 5, 1, 8, 6, 3, 7] 20: [4, 3, 8, 5, 2, 7, 6, 1, 9] 23: [7, 2, 6, 8, 1, 5, 9, 3, 4] 23: [7, 3, 5, 8, 2, 4, 9, 1, 6]
直線の値は 17, 19, 20, 21, 23 の 5 通りで、解は全部で 18 通りになりました。頂点に配置される数字の組み合わせは次のようになります。
17: (1, 2, 3) 19: (1, 4, 7), (2, 3, 7) 20: (1, 5, 9), (2, 5, 8), (3, 5, 7), (4, 5, 6) 21: (3, 6, 9), (3, 7, 8) 23: (7, 8, 9)
基本的な考え方は問題１と同じなので、説明は割愛させていただきます。詳細はプログラムリストをお読みください。
リスト : 変形魔方陣３
# 盤面
# 0 1 2
# 3 4
# 5 6 7
# 直線
line03 = [
[0,1,2], [0,3,5], [2,4,7], [5,6,7]
]
# 条件のチェック
def check031(ps):
def add(a,b,c):
return ps[a] + ps[b] + ps[c]
xs = [add(*ls) for ls in line03]
return xs.count(xs[0]) == 4
# 重複解の排除
def check032(ps, x):
if len(ps) == 2 and ps[0] > x: return True
if len(ps) == 5 and ps[2] > x: return True
if len(ps) == 7 and ps[0] > x: return True
return False
# 問題３
def solver03():
permutations(check031, check032, range(1, 9))
解の個数は対称解 (回転解と鏡像解) を除いた場合です。
>>> solver03() [1, 6, 7, 5, 3, 8, 2, 4] [1, 7, 5, 4, 6, 8, 3, 2] [1, 8, 3, 5, 7, 6, 4, 2] [1, 8, 4, 7, 3, 5, 2, 6] [3, 5, 7, 4, 2, 8, 1, 6] [3, 7, 4, 6, 2, 5, 1, 8]
┌─┬─┬─┐ │１│８│３│ ├─┼─┼─┤ │５│ │７│ ├─┼─┼─┤ │６│４│２│ └─┴─┴─┘
┌─┬─┬─┐ ┌─┬─┬─┐ │１│７│５│ │１│８│４│ ├─┼─┼─┤ ├─┼─┼─┤ │４│ │６│ │７│ │３│ ├─┼─┼─┤ ├─┼─┼─┤ │８│３│２│ │５│２│６│ └─┴─┴─┘ └─┴─┴─┘
┌─┬─┬─┐ ┌─┬─┬─┐ │１│６│７│ │３│７│４│ ├─┼─┼─┤ ├─┼─┼─┤ │５│ │３│ │６│ │２│ ├─┼─┼─┤ ├─┼─┼─┤ │８│２│４│ │５│１│８│ └─┴─┴─┘ └─┴─┴─┘
┌─┬─┬─┐ │３│５│７│ ├─┼─┼─┤ │４│ │２│ ├─┼─┼─┤ │８│１│６│ └─┴─┴─┘
偶数 (2, 4, 6, 8, 10, 12, 14, 16) の場合は、問題２の数字を 2 倍することで求めることができます。奇数 (1, 3, 5, 7, 9, 11, 13, 15) の場合は、数字を 2 倍して -1 することで求めることができます。下図に一例を示します。
┌─┬─┬─┐ ┌─┬─┬─┐ ┌─┬─┬─┐ │１│８│３│ │２│16│６│ │１│15│５│ ├─┼─┼─┤ ├─┼─┼─┤ ├─┼─┼─┤ │５│ │７│ │10│ │14│ │９│ │13│ ├─┼─┼─┤ ├─┼─┼─┤ ├─┼─┼─┤ │６│４│２│ │12│８│４│ │11│７│３│ └─┴─┴─┘ └─┴─┴─┘ └─┴─┴─┘ 問題２の解 （Ａ）偶数の場合 （Ｂ）奇数の場合
リスト : 変形魔方陣４
def solver04():
permutations(check031, check032, (3, 5, 7, 11, 13, 17, 19, 23))
>>> solver04() [3, 23, 5, 17, 19, 11, 13, 7]
┌─┬─┬─┐ 合計値 N = 31（素数） │３│23│５│ ├─┼─┼─┤ │17│ │19│ ├─┼─┼─┤ │11│13│７│ └─┴─┴─┘
リスト : 変形魔方陣５
def solver05():
permutations(check031, check032, (0, 1, 3, 4, 6, 7, 8, 9))
>>> solver05() [6, 4, 7, 3, 1, 8, 0, 9]
┌─┬─┬─┐ │６│４│７│ 合計値 N = 17 ├─┼─┼─┤ │３│ │１│ ├─┼─┼─┤ │８│０│９│ └─┴─┴─┘
辺の値 N は 17 になります。ちなみに、1 と 7 を除いた数字 (0, 2, 3, 4, 5, 6, 8, 9) をひとつずつ使って、4 辺の値が等しくなるように配置することもできます。興味のある方は挑戦してみてください。
#
# magic2.py : 変形魔方陣
#
# Copyright (C) 2022 Makoto Hiroi
#
# 順列の生成
def permutations(check1, check2, xs, ps = [], print_board = print):
if len(ps) == len(xs):
if check1(ps): print_board(ps)
else:
for x in xs:
if x in ps or check2(ps, x): continue
ps.append(x)
permutations(check1, check2, xs, ps, print_board)
ps.pop()
#
# 問題１
#
# 盤面
# 0 1 2
# 3 4 5
# 6 7 8
line01 = [
[0,1,3,4], [1,2,4,5], [3,4,6,7],
[4,5,7,8], [0,2,6,8]
]
# 条件のチェック
def check011(ps):
def add(a,b,c,d):
return ps[a] + ps[b] + ps[c] + ps[d]
xs = [add(*ls) for ls in line01]
return xs.count(xs[0]) == 5
# 重複解の排除
def check012(ps, x):
if len(ps) == 2 and ps[0] > x: return True
if len(ps) == 6 and ps[2] > x: return True
if len(ps) == 8 and ps[0] > x: return True
return False
def solver01():
permutations(check011, check012, range(1, 10))
#
# 問題２
#
# 盤面
# 0
# 1 8
# 2 7
# 3 4 5 6
line02 = [
[0,1,2,3], [3,4,5,6], [6,7,8,0]
]
# 条件のチェック
def check021(ps):
def add(a,b,c,d):
return ps[a] + ps[b] + ps[c] + ps[d]
xs = [add(*ls) for ls in line02]
return xs[0] == 20 and xs.count(xs[0]) == 3
def check021a(ps):
def add(a,b,c,d):
return ps[a] + ps[b] + ps[c] + ps[d]
xs = [add(*ls) for ls in line02]
return xs.count(xs[0]) == 3
# 重複解の排除
def check022(ps, x):
if len(ps) == 2 and ps[1] > x: return True
if len(ps) == 3 and ps[0] > x: return True
if len(ps) == 5 and ps[4] > x: return True
if len(ps) == 6 and ps[3] > x: return True
if len(ps) == 8 and ps[7] > x: return True
return False
def solver02():
permutations(check021, check022, range(1, 10))
def print_board2(ps):
print(f'{sum(ps[:4])}: {ps}')
def solver02a():
permutations(check021a, check022, range(1, 10), [], print_board2)
#
# 問題３
#
# 盤面
# 0 1 2
# 3 4
# 5 6 7
line03 = [
[0,1,2], [0,3,5], [2,4,7], [5,6,7]
]
def check031(ps):
def add(a,b,c):
return ps[a] + ps[b] + ps[c]
xs = [add(*ls) for ls in line03]
return xs.count(xs[0]) == 4
# 重複解の排除
def check032(ps, x):
if len(ps) == 2 and ps[0] > x: return True
if len(ps) == 5 and ps[2] > x: return True
if len(ps) == 7 and ps[0] > x: return True
return False
def solver03():
permutations(check031, check032, range(1, 9))
#
# 問題４
#
def solver04():
permutations(check031, check032, (3, 5, 7, 11, 13, 17, 19, 23))
#
# 問題５
#
def solver05():
permutations(check031, check032, (0, 1, 3, 4, 6, 7, 8, 9))