ナンプレ問題 PuLP

ナンプレ問題

下記のナンプレ問題を、PuLPを使って解いて下さい。

5 3 0 0 7 0 0 0 0 
6 0 0 1 9 5 0 0 0 
0 9 8 0 0 0 0 6 0 
8 0 0 0 6 0 0 0 3 
4 0 0 8 0 3 0 0 1 
7 0 0 0 2 0 0 0 6 
0 6 0 0 0 0 2 8 0 
0 0 0 4 1 9 0 0 5 
0 0 0 0 8 0 0 7 9

解法・ソースコード

ソースコードの構造と各部分の役割について説明します。

①問題の定義

まず、問題を定義するために pulp.LpProblem() 関数を使用しています。

この関数には、問題の名前と目的関数の種類を指定します。

ここでは、ナンプレ問題を解くために、”Sudoku Problem”という名前の問題を定義し、目的関数として pulp.LpMinimize を使用しています。

ただし、ナンプレ問題には目的関数が存在しないため、この値は問題の解法に影響しません。

②変数の定義

問題で扱う変数を定義します。

pulp.LpVariable.dicts() 関数を使用して、choices という名前の辞書を作成しています。

この辞書には、各マスに対応する9つの変数が含まれています。

つまり、choices[i][j][k] は、マス(i, j)に数字kが入っているかどうかを表す0または1の変数になります。

ここでは、cat=’Binary’という引数を指定することで、変数が0または1の整数値しかとらないようにしています。

③制約条件の定義

問題の制約条件を定義します。

各マスには1つの数字しか入らないことを表す制約条件を設定しています。

具体的には、各マスに入る数字の変数の和が1であるという条件を表しています。

④各行には1から9までの数字が1回ずつ現れる

各行には1から9までの数字が1回ずつ現れることを表す制約条件を設定しています。

⑤各列には1から9までの数字が1回ずつ現れる

④と同様に、各列には1から9までの数字が1回ずつ現れることを表す制約条件も設定しています。

⑥各3x3ブロックには1から9までの数字が1回ずつ現れる

各ブロックには1から9までの数字が1回ずつ現れることを表す制約条件も設定しています。

具体的には、各数字がブロック内のある1つのマスに現れるという条件を表しています。

各ブロックの左上のマスを(row, col)として、3x3のブロック内の各マスに対して、そのマスにnumが入っているかどうかを表す変数の和が1であるという制約条件を表しています。

⑦初期状態を設定

初期状態が与えられている場合は、その状態に合わせた制約条件も設定しています。

初期状態に数字が入っているマスに対して、そのマスに対応する変数を1に固定するという制約条件を表しています。

⑧解を求める

problem.solve() で定義した問題を解きます。

⑨解の表示

各変数がとる値を choices[row][col][num].value() で取得し、それを元に解を作成しています。

最終的には、解を二次元配列として solution に保存し、それを行ごとに表示しています。

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
50
51
52
53
54
55
56
57
58
59
60
61
62
import pulp

# ①問題の定義
problem = pulp.LpProblem("Sudoku Problem", pulp.LpMinimize)

# ②変数の定義
choices = pulp.LpVariable.dicts("Choice", (range(1, 10), range(1, 10), range(1, 10)), cat='Binary')

# ③制約条件の定義
# 各マスは1つの数字に限定される
for row in range(1, 10):
    for col in range(1, 10):
        problem += pulp.lpSum([choices[row][col][num] for num in range(1, 10)]) == 1

# ④各行には1から9までの数字が1回ずつ現れる
for row in range(1, 10):
    for num in range(1, 10):
        problem += pulp.lpSum([choices[row][col][num] for col in range(1, 10)]) == 1

# ⑤各列には1から9までの数字が1回ずつ現れる
for col in range(1, 10):
    for num in range(1, 10):
        problem += pulp.lpSum([choices[row][col][num] for row in range(1, 10)]) == 1

# ⑥各3x3ブロックには1から9までの数字が1回ずつ現れる
for row in range(1, 10, 3):
    for col in range(1, 10, 3):
        for num in range(1, 10):
            problem += pulp.lpSum([choices[i][j][num] for i in range(row, row + 3) for j in range(col, col + 3)]) == 1

# ⑦初期状態を設定
# ナンプレ問題の初期状態には、空きマスを0として表現します。
initial_state = [
    [5, 3, 0, 0, 7, 0, 0, 0, 0],
    [6, 0, 0, 1, 9, 5, 0, 0, 0],
    [0, 9, 8, 0, 0, 0, 0, 6, 0],
    [8, 0, 0, 0, 6, 0, 0, 0, 3],
    [4, 0, 0, 8, 0, 3, 0, 0, 1],
    [7, 0, 0, 0, 2, 0, 0, 0, 6],
    [0, 6, 0, 0, 0, 0, 2, 8, 0],
    [0, 0, 0, 4, 1, 9, 0, 0, 5],
    [0, 0, 0, 0, 8, 0, 0, 7, 9]
]

for row in range(9):
    for col in range(9):
        if initial_state[row][col] != 0:
            problem += choices[row+1][col+1][initial_state[row][col]] == 1

# ⑧解を求める
problem.solve()

# ⑨解の表示
solution = [[0]*9 for _ in range(9)]
for row in range(1, 10):
    for col in range(1, 10):
        for num in range(1, 10):
            if choices[row][col][num].value() == 1:
                solution[row-1][col-1] = num

for row in solution:
    print(row)

このコードを実行すると、下記の結果を得ることができます。

[実行結果]
[5, 3, 4, 6, 7, 8, 9, 1, 2]
[6, 7, 2, 1, 9, 5, 3, 4, 8]
[1, 9, 8, 3, 4, 2, 5, 6, 7]
[8, 5, 9, 7, 6, 1, 4, 2, 3]
[4, 2, 6, 8, 5, 3, 7, 9, 1]
[7, 1, 3, 9, 2, 4, 8, 5, 6]
[9, 6, 1, 5, 3, 7, 2, 8, 4]
[2, 8, 7, 4, 1, 9, 6, 3, 5]
[3, 4, 5, 2, 8, 6, 1, 7, 9]

PuLPを使ってナンプレ問題を解くことができました。