python-constraint 魔法陣

python-constraint 魔法陣

魔法陣を解く問題を考えます。

魔法陣とは、整数の(n×n)正方行列で、行・列および対角線の各要素の和がすべて同じになるものです。

魔法陣問題の解決

以下の例では、3×3魔法陣を解きます。

3×3魔法陣の各行、列、および対角線の和は15である必要があります。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
import constraint

# 魔法陣のサイズ
n = 3

# 魔法陣の各セルに変数を割り当てる
problem = constraint.Problem()

# 各セルは1から9の整数を持つ
problem.addVariables(range(n * n), range(1, n * n + 1))

# 各セルの値は一意である必要がある
problem.addConstraint(constraint.AllDifferentConstraint())

# 行、列、対角線の和がすべて等しくなる制約を追加
magic_sum = n * (n * n + 1) // 2

# 行の制約
for row in range(n):
problem.addConstraint(
lambda a, b, c: a + b + c == magic_sum,
[row * n + i for i in range(n)]
)

# 列の制約
for col in range(n):
problem.addConstraint(
lambda a, b, c: a + b + c == magic_sum,
[col + n * i for i in range(n)]
)

# 対角線の制約
problem.addConstraint(
lambda a, b, c: a + b + c == magic_sum,
[i * (n + 1) for i in range(n)]
)
problem.addConstraint(
lambda a, b, c: a + b + c == magic_sum,
[(i + 1) * (n - 1) for i in range(n)]
)

# 解を取得
solutions = problem.getSolutions()

# 結果を表示
for solution in solutions:
for row in range(n):
print([solution[row * n + col] for col in range(n)])
print()

説明

  1. 問題定義:

    • 魔法陣のサイズ n = 3 を定義します。
    • 各セルに変数を割り当て、各変数は1から9までの値を取ることができます。
  2. 制約の追加:

    • constraint.AllDifferentConstraint() を使用して、各セルの値が一意であることを保証します。
    • 各行、列、および対角線の和が magic_sum になるように制約を追加します。
  3. 解の取得と表示:

    • problem.getSolutions() を使用してすべての解を取得し、各解を表示します。

このコードは3×3魔法陣を解くもので、すべての解を表示します。

他のサイズの魔法陣に対しても、同様の方法で解くことができます。

ただし、サイズが大きくなると計算時間が増加するため注意が必要です。

結果解説

[実行結果]

[6, 1, 8]
[7, 5, 3]
[2, 9, 4]

[6, 7, 2]
[1, 5, 9]
[8, 3, 4]

[8, 1, 6]
[3, 5, 7]
[4, 9, 2]

[8, 3, 4]
[1, 5, 9]
[6, 7, 2]

[4, 3, 8]
[9, 5, 1]
[2, 7, 6]

[4, 9, 2]
[3, 5, 7]
[8, 1, 6]

[2, 9, 4]
[7, 5, 3]
[6, 1, 8]

[2, 7, 6]
[9, 5, 1]
[4, 3, 8]

これは、3×3魔法陣のすべての可能な解を表示した結果です。

3×3魔法陣は、各行、各列、そして2つの対角線の数の合計がすべて15になるような配置です。

以下に各魔法陣の配置を解説します。

  1. 最初の魔法陣:

    1
    2
    3
    [6, 1, 8]
    [7, 5, 3]
    [2, 9, 4]
    • 各行の和: 6+1+8=15, 7+5+3=15, 2+9+4=15
    • 各列の和: 6+7+2=15, 1+5+9=15, 8+3+4=15
    • 対角線の和: 6+5+4=15, 8+5+2=15
  2. 二番目の魔法陣:

    1
    2
    3
    [6, 7, 2]
    [1, 5, 9]
    [8, 3, 4]
    • 各行の和: 6+7+2=15, 1+5+9=15, 8+3+4=15
    • 各列の和: 6+1+8=15, 7+5+3=15, 2+9+4=15
    • 対角線の和: 6+5+4=15, 2+5+8=15
  3. 三番目の魔法陣:

    1
    2
    3
    [8, 1, 6]
    [3, 5, 7]
    [4, 9, 2]
    • 各行の和: 8+1+6=15, 3+5+7=15, 4+9+2=15
    • 各列の和: 8+3+4=15, 1+5+9=15, 6+7+2=15
    • 対角線の和: 8+5+2=15, 6+5+4=15

これらの結果は、すべて3×3魔法陣であり、どの行、列、および対角線の和もすべて15になります。

このように、魔法陣の問題は数学的な整合性を満たすように数値を配置するパズルです。