制約充足問題 python-constraint

制約充足問題

簡単な制約充足問題を解く例として、次の条件を満たす整数の組み合わせを見つける問題を考えましょう。

条件:

  1. 3つの整数$ ( x, y, z ) $を見つける。
  2. $ ( x, y, z ) $は 1 から 10 までの整数。
  3. $ ( x + y + z = 20 ) $の条件を満たす。

これをpython-constraintを使って解きます。

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
from constraint import Problem

def find_numbers():
    problem = Problem()

    # 変数の定義
    problem.addVariable('x', range(1, 11))
    problem.addVariable('y', range(1, 11))
    problem.addVariable('z', range(1, 11))

    # 制約の設定
    def constraint_function(x, y, z):
        if x + y + z == 20:
            return True

    problem.addConstraint(constraint_function, ['x', 'y', 'z'])

    solutions = problem.getSolutions()
    return solutions

solutions = find_numbers()
if solutions:
    print("整数の組み合わせ:")
    for solution in solutions:
        print(f"x: {solution['x']}, y: {solution['y']}, z: {solution['z']}")
else:
    print("条件を満たす組み合わせは見つかりませんでした。")

このコードは、1から10までの整数$ (x, y, z) $の組み合わせを見つけて、条件$ (x + y + z = 20) $を満たす解を見つけます。

解が見つかれば、整数の組み合わせが出力されます。

[実行結果]

整数の組み合わせ:
x: 10, y: 9, z: 1
x: 10, y: 8, z: 2
x: 10, y: 7, z: 3
x: 10, y: 6, z: 4
x: 10, y: 5, z: 5
x: 10, y: 4, z: 6
x: 10, y: 3, z: 7
x: 10, y: 2, z: 8
x: 10, y: 1, z: 9
x: 9, y: 10, z: 1
x: 9, y: 9, z: 2
x: 9, y: 8, z: 3
x: 9, y: 7, z: 4
x: 9, y: 6, z: 5
x: 9, y: 5, z: 6
x: 9, y: 4, z: 7
x: 9, y: 3, z: 8
x: 9, y: 2, z: 9
x: 9, y: 1, z: 10
x: 8, y: 10, z: 2
x: 8, y: 9, z: 3
x: 8, y: 8, z: 4
x: 8, y: 7, z: 5
x: 8, y: 6, z: 6
x: 8, y: 5, z: 7
x: 8, y: 4, z: 8
x: 8, y: 3, z: 9
x: 8, y: 2, z: 10
x: 7, y: 10, z: 3
x: 7, y: 9, z: 4
x: 7, y: 8, z: 5
x: 7, y: 7, z: 6
x: 7, y: 6, z: 7
x: 7, y: 5, z: 8
x: 7, y: 4, z: 9
x: 7, y: 3, z: 10
x: 6, y: 10, z: 4
x: 6, y: 9, z: 5
x: 6, y: 8, z: 6
x: 6, y: 7, z: 7
x: 6, y: 6, z: 8
x: 6, y: 5, z: 9
x: 6, y: 4, z: 10
x: 5, y: 10, z: 5
x: 5, y: 9, z: 6
x: 5, y: 8, z: 7
x: 5, y: 7, z: 8
x: 5, y: 6, z: 9
x: 5, y: 5, z: 10
x: 4, y: 10, z: 6
x: 4, y: 9, z: 7
x: 4, y: 8, z: 8
x: 4, y: 7, z: 9
x: 4, y: 6, z: 10
x: 3, y: 10, z: 7
x: 3, y: 9, z: 8
x: 3, y: 8, z: 9
x: 3, y: 7, z: 10
x: 2, y: 10, z: 8
x: 2, y: 9, z: 9
x: 2, y: 8, z: 10
x: 1, y: 10, z: 9
x: 1, y: 9, z: 10

ソースコード解説

このコードは、Pythonのpython-constraintライブラリを使用して、特定の制約を満たす整数の組み合わせを見つける例です。

1. ライブラリのインポートと関数定義:

  • from constraint import Problem：constraintライブラリからProblemクラスをインポートします。
  • find_numbers()関数：制約充足問題を解くための関数を定義します。

2. 制約充足問題の定義:

  • problem = Problem()：制約充足問題を定義するためのProblemオブジェクトを作成します。
  • problem.addVariable('x', range(1, 11))：変数 x を1から10の整数の範囲で定義します。
  • problem.addVariable('y', range(1, 11))：変数 y を1から10の整数の範囲で定義します。
  • problem.addVariable('z', range(1, 11))：変数 z を1から10の整数の範囲で定義します。

3. 制約の設定:

  • constraint_function()関数：x + y + z = 20 となるような条件を満たす制約関数を定義します。
  • problem.addConstraint(constraint_function, ['x', 'y', 'z'])：constraint_functionを使用して、x + y + z = 20 の制約を追加します。

4. 問題の解決:

  • problem.getSolutions()：Problemオブジェクトを解き、条件を満たす整数の組み合わせを探します。

5. 解の表示:

  • solutionsリストに解が含まれている場合は、各解の x, y, z の値を表示します。
  • 解が見つからなかった場合は、条件を満たす組み合わせが見つからなかったことを通知します。