python-constraintによる制約プログラミング

制約プログラミングを扱うときに最初に理解しなければならないことは、コードを書くために座っているときの我々の通常の思考方法とは、考え方が非常に異なるということです。

制約プログラミングは、私たちが普段使っている命令型パラダイムとは対照的に、宣言型プログラミングパラダイムの一例です。

プログラミングパラダイムとは何ですか？

パラダイムとは、何かの「例」「型」という意味です。プログラミングパラダイムは、しばしば「考え方」や「プログラミングの方法」と表現されます。最も一般的な例として、手続き型プログラミング（C言語など）、オブジェクト指向プログラミング（Javaなど）、関数型プログラミング（Haskellなど）などがある。

ほとんどのプログラミングパラダイムは、命令型パラダイムと宣言型パラダイムのどちらかのグループに分類することができる。

命令型プログラミングと宣言型プログラミングの違いは何ですか？

• 命令型プログラミングは、簡単に言うと、開発者が目標（何らかの結果）を達成するための解決策・アルゴリズムを記述することを基本としています。これは、命令を段階的に実行しながら、代入文によってプログラムの状態を変化させることで実現します。したがって、命令をどのような順序で記述するかは大きな違いです。
• 宣言型プログラミングはその逆で、ゴールを達成するための手順を書かず、ゴールを記述し、コンピュータが解決策を与えてくれるものです。よく知られている例としては、SQLがあります。どのようにすれば必要な結果が得られるかをコンピュータに指示するのでしょうか？いいえ、必要なものを記述するのです。あるテーブルの、ある列の、ある条件を満たした値が必要なのです。

python-constraintモジュールのインストール

この記事では、python-constraintというモジュールを使います（注：Pythonには “constraint “というモジュールがありますが、これは我々が欲しいものではありません）。このモジュールは、制約プログラミングのアイデアをPythonにもたらすことを目的としています。

このモジュールをインストールするには、ターミナルを開いて、次のように実行します。

$ pip install python-constraint

Python-constraintの基本的な使い方

このモジュールを使って書かれたプログラムの一般的なスケルトンは以下の通りです。 (注意: import constraint を使い、import python-constraint ではありません)

• インポート constraint
• 問題となる変数を定義します。
• 変数とその区間を問題に追加します。
• 組み込み/カスタム制約を問題に追加します。
• 解を取得します。
• 解を調べて必要なものを見つける

先に述べたように、制約プログラミングは宣言的なプログラミングの一種です。ステートメントの順序は、最終的にすべてがそこにある限り、問題ではありません。通常、このような問題を解決するために使われます。

例A

Find all (x,y) where x ∈ {1,2,3} and 0 <= y < 10, and x + y >= 5

この文章を見ると、x と y が満たさなければならないいくつかの条件 (これを制約と呼ぶことにします) が見えます。

例えば、x は 1,2,3 という値に「制約」され、y は 10 より小さく、それらの和は 5 以上でなければならない。これは、制約プログラミングを用いて、数行のコードで、数分間で行われます。

上の問題を見て、あなたはおそらく「だから何？Pythonで2つのforループとコーヒーカップ半分を使えば、10分以内にできる」と思ったことでしょう。

しかし、この例を通して、制約プログラミングがどのようなものかを理解することができます。

import constraint


problem = constraint.Problem()


problem.addVariable('x', [1,2,3])
problem.addVariable('y', range(10))


def our_constraint(x, y):
    if x + y >= 5:
        return True


problem.addConstraint(our_constraint, ['x','y'])


solutions = problem.getSolutions()


# Easier way to print and see all solutions
# for solution in solutions:
#    print(solution)


# Prettier way to print and see all solutions
length = len(solutions)
print("(x,y) ∈ {", end="")
for index, solution in enumerate(solutions):
    if index == length - 1:
        print("({},{})".format(solution['x'], solution['y']), end="")
    else:
        print("({},{}),".format(solution['x'], solution['y']), end="")
print("}")

出力

(x,y) ∈ {(3,9),(3,8),(3,7),(3,6),(3,5),(3,4),(3,3),(3,2),(2,9),(2,8),(2,7),(2,6),(2,5),(2,4),(2,3),(1,9),(1,8),(1,7),(1,6),(1,5),(1,4)}

このプログラムを順を追って見ていきましょう。私たちは2つの変数、xとyを持っていました。私たちはそれらをそれぞれの許容範囲とともに問題に追加しました。

この2行は次のような意味である。

I'm adding a variable x that can only have values [1,2,3], and a variable y that can only have values [0,1,2,..,9]

次に、カスタム制約（つまり、x + y >= 5）を定義します。制約のメソッドは、変数の値の組み合わせが許容範囲内であれば True を、許容範囲外であれば None を返すことになっています。

私たちの our_constraint() メソッドでは、「許容できる状況は x + y >= 5 のときだけで、それ以外は最終解に (x,y) のそれらの値を含めないようにする」と述べています。

制約を定義した後、それを問題に追加する必要があります。.addConstraint()` メソッドの構造は次のとおりです。

addConstraint(which_constraint, list_of_variable_order)

注：この場合、2番目のパラメータとして [x,y] または [y,x] と書くことは問題ではありませんが、ほとんどの場合、順序は重要です。

その後、problem.getSolutions() で解を取得し（すべての条件を満たす変数値の組み合わせのリストを返す）、それを繰り返し処理します。

注意：例えば、x /= yの組み合わせのみを取得したい場合は、解を取得する前に組み込みの制約を追加します。

problem.addConstraint(constraint.AllDifferentConstraint())

すべての組み込み制約のリストはこちらで見ることができます。これで、この種のタスクを実行するのに必要な知識はほぼすべて揃いました。

ウォームアップの例

例B

ここで、制約プログラミングが楽しく使えるタイプの問題、暗号算術パズルを紹介します。次のような暗号パズルは、各文字が異なる数字を表します（先頭の文字が0であることはありえません）。

TWO + TWO = FOUR

これを普通のPythonで解くとどうなるか、考えてみてください。実際、命令型プログラミングを使ったこの問題の解法を調べてみることをお勧めします。

例題Dを自力で解くために必要な知識も得られるはずです。

T’と’F’は先頭の文字、つまり数字の1桁目なので、0にはならないことに注意してください。

import constraint


problem = constraint.Problem()


# We're using .addVariables() this time since we're adding
# multiple variables that have the same interval.
# Since Strings are arrays of characters we can write
# "TF" instead of ['T','F'].
problem.addVariables("TF", range(1, 10))
problem.addVariables("WOUR", range(10))


# Telling Python that we need TWO + TWO = FOUR
def sum_constraint(t, w, o, f, u, r):
    if 2*(t*100 + w*10 + o) == f*1000 + o*100 + u*10 + r:
        return True


# Adding our custom constraint. The
# order of variables is important!
problem.addConstraint(sum_constraint, "TWOFUR")


# All the characters must represent different digits,
# there's a built-in constraint for that
problem.addConstraint(constraint.AllDifferentConstraint())


solutions = problem.getSolutions()
print("Number of solutions found: {}
".format(len(solutions)))


# .getSolutions() returns a dictionary
for s in solutions:
    print("T = {}, W = {}, O = {}, F = {}, U = {}, R = {}"
        .format(s['T'], s['W'], s['O'], s['F'], s['U'], s['R']))

このコードを実行すると、可能な解答が表示されます。

Number of solutions found: 7


T = 7, W = 6, O = 5, F = 1, U = 3, R = 0
T = 7, W = 3, O = 4, F = 1, U = 6, R = 8
T = 8, W = 6, O = 7, F = 1, U = 3, R = 4
T = 8, W = 4, O = 6, F = 1, U = 9, R = 2
T = 8, W = 3, O = 6, F = 1, U = 7, R = 2
T = 9, W = 2, O = 8, F = 1, U = 5, R = 6
T = 9, W = 3, O = 8, F = 1, U = 7, R = 6

例C

You recently got a job as a cashier. You're trying to convince your friend that it's hard work, there are just SO many ways to give someone their change back! Your "friend" shakes his head, obviously not believing you. He says "It can't be that bad. How many ways can there POSSIBLY be to give someone their change back, for like 60 cents?".


Your response is, of course, to sit and quickly write a program that would prove your point. You have a decent amount of pennies (1 cent), nickels (5 cents), dimes (10 cents) and quarters (25 cents), and a lot of kinda suspicious coins worth 3 cents each. Calculate in how many ways you can return change for 60 cents.

注意：結果が表示される順番は、変数を追加した順番と同じとは限りません。つまり，結果が (a,b,c,d,e) の場合，1セント硬貨がa枚，3セント硬貨がb枚，などということはわからない．

ですから、変数とその値を明示的に表示しなければなりません。この結果、組み込みの .ExactSumConstraint() を、2パラメータ形式の ExactSumConstraint(50,[1,3,5,10,20]) として使用することができなくなります。

ここでの2番目のパラメータは、各変数の「重み」（何倍にするか）であり、どの変数がどのような重みになるかは保証されていません。

よくある間違いで、変数が追加された順番に重みが割り当てられると仮定してしまいますが、代わりに以下のコードでは、この組み込み制約の3パラメータ形式を使用しています。

import constraint


problem = constraint.Problem()


# The maximum amount of each coin type can't be more than 60
# (coin_value*num_of_coints) <= 60


problem.addVariable("1 cent", range(61))
problem.addVariable("3 cent", range(21))
problem.addVariable("5 cent", range(13))
problem.addVariable("10 cent", range(7))
problem.addVariable("20 cent", range(4))


problem.addConstraint(
    constraint.ExactSumConstraint(60,[1,3,5,10,20]),
    ["1 cent", "3 cent", "5 cent","10 cent", "20 cent"]
)
# Where we explicitly give the order in which the weights should be allocated


# We could've used a custom constraint instead, BUT in this case the program will
# run slightly slower - this is because built-in functions are optimized and
# they find the solution more quickly
# def custom_constraint(a, b, c, d, e):
#     if a + 3*b + 5*c + 10*d + 20*e == 60:
#         return True
#     problem.addConstraint(o, ["1 cent", "3 cent", "5 cent","10 cent", "20 cent"])


# A function that prints out the amount of each coin
# in every acceptable combination
def print_solutions(solutions):
    for s in sols:
        print("---")
        print("""
        1 cent: {0:d}
        3 cent: {1:d}
        5 cent: {2:d}
        10 cent: {3:d}
        20 cent: {4:d}""".format(s["1 cent"], s["3 cent"], s["5 cent"], s["10 cent"], s["20 cent"]))
        # If we wanted to we could check whether the sum was really 60
        # print("Total:", s["1 cent"] + s["3 cent"]*3 + s["5 cent"]*5 + s["10 cent"]*10 + s["20 cent"]*20)
        # print("---")


solutions = problem.getSolutions()
#print_solutions(solutions)
print("Total number of ways: {}".format(len(solutions)))

このコードを実行すると、次のような結果が得られます。

Total number of ways: 535

例D

CRASH + ERROR + REBOOT = HACKER

例BとDは、制約を使用する場合、いくつかの変数が上下し、より冗長な制約があるだけで、ほぼ同じです。これは制約プログラミングの一つの良い点で、少なくともコーディングに費やした時間が関係している場合には、良いスケーラビリティを発揮します。このパズルには1つの解しかなく、それはA=3 B=7 C=8 E=2 H=6 K=0 O=1 R=5 S=9 T=4となります。

これらのタイプの課題（特に暗号化）は、どちらかというと、制約プログラミングがどのように機能するかを簡単に示すための遊びとして使われますが、制約プログラミングが実用的な価値を持つ状況もあります。

ある地域をカバーする最小の放送局数を計算したり、交通の流れが最適になるように信号機を設置する方法を見つけたりすることができるのです。一般論として、制約条件は、可能な組み合わせがたくさんある場合に使われます。

これらの例は、この記事の範囲では複雑すぎますが、制約プログラミングが実世界で使用できることを示すのに役立っています。

よりハードな例

例E

You wish to pack chocolates for your mother. Luckily you work in a chocolate factory that has a lot of leftover chocolate. You have a few chocolate types at your disposal.


Your goal is to bring her the sweetest chocolate possible, that you can pack in your bag and sneak through security, and that wouldn't pass a certain net value for which you'd go to prison if you got caught.


Security most likely won't get suspicious if you bring less than 3kg. You can fit 1 dm^3 of chocolate in your bag. You won't go to jail if you steal less than $300 worth of chocolate.

では、腕まくりをして、さっそく始めてみましょう。これまでの例題を理解していれば、それほど難しくはないはずです。

まず、各チョコレートをその種類だけ持ってきた場合、どれだけの量を持つことができるかを考え、間隔の上限を求めます。例えば、チョコレートAは、重さによって最大30本、価値によって最大37本、体積によって最大100本持っていくことができます。

これらの数字のうち最小のものは30であり、これがチョコレートAの最大個数である。同じ手順で、残りの最大数、B – 44、C – 75、D – 100を求めることができます。

import constraint


problem = constraint.Problem()


problem.addVariable('A', range(31))
problem.addVariable('B', range(45))
problem.addVariable('C', range(76))
problem.addVariable('D', range(101))


# We have 3kg = 3,000g available
def weight_constraint(a, b, c, d):
    if (a*100 + b*45 + c*10 + d*25) <= 3000:
        return True


# We have 1dm^3 = 1,000cm^3 available
def volume_constraint(a, b, c, d):
    if (a*8*2.5*0.5 + b*6*2*0.5 * c*2*2*0.5 + d*3*3*0.5) <= 1000:
        return True


# We can't exceed $300
def value_constraint(a, b, c, d):
    if (a*8 + b*6.8 + c*4 + d*3) < 300:
        return True


problem.addConstraint(weight_constraint, "ABCD")
problem.addConstraint(volume_constraint, "ABCD")
problem.addConstraint(value_constraint, "ABCD")


maximum_sweetness = 0
solution_found = {}
solutions = problem.getSolutions()


for s in solutions:
    current_sweetness = s['A']*10 + s['B']*8 + s['C']*4.5 + s['D']*3.5
    if current_sweetness > maximum_sweetness:
        maximum_sweetness = current_sweetness
        solution_found = s


print("""
The maximum sweetness we can bring is: {}
We'll bring:
{} A Chocolates,
{} B Chocolates,
{} C Chocolates,
{} D Chocolates
""".format(maximum_sweetness, solution_found['A'], solution_found['B'], solution_found['C'], solution_found['D']))

このコードの一部を実行すると、次のような結果が得られます。

コード偽

注意: 各チョコレートの種類に関連するすべての情報を、例えば weight_dictionary = {'A' : 100, 'B' : 45, 'C' : 10, 'D' : 25} のように辞書に格納して、関数内でハードコーディングする代わりに、その方法で値にアクセスすることが可能です。しかし、読みやすさ、コードの長さ、そしてこのチュートリアルでより重要なことに集中するために、私は制約関数自体にハードコードすることを好みます。

注：この結果が計算されるのに時間がかかることにお気づきでしょうか、これは制約プログラミングの欠点です。

例F

さて、もっと楽しいことをしよう。数独（古典的な9×9）ソルバーを作ってみるのだ。JSONファイルからパズルを読み込んで、その特定のパズルのすべての解を見つける（そのパズルに解があると仮定する）。

もし、数独を解くためのルールを忘れてしまったら。

• セルは1～9の値を持つことができる
• 同じ行のすべてのセルは、異なる値を持つ必要があります。
• 同じ列のすべてのセルは、異なる値を持っている必要があります。
• 3×3の正方形（合計9つ）のすべてのセルは異なる値でなければなりません。

このプログラムの問題点のひとつは、「値をどのように格納するか」ということです。行列を変数として問題に追加すれば、Pythonが魔法のように私たちの望むものを見つけ出してくれるわけではありません。

そこで、数値を変数名と同じように扱い（これは許されることです）、行列があるように見せかけるシステムを採用します。インデックスは通常の(0,0)ではなく、(1,1)から始まるようにします。それを使って、私たちは慣れた方法で碁盤の要素にアクセスすることにします。

次に、私たちはPythonにこれらのすべてのセルが1から9の間の値を持つことができることを伝えるという簡単なことをする必要があります。

次に、同じ行のセルは同じ最初のインデックスを持つことに注意します。例えば、最初の行は(1,x)です。すべての行を繰り返し、すべてのセルが異なる値を持つ必要があることを簡単に言うことができます。列についても同じことが言えます。あとは、コードを見ればもっと簡単に理解できます。

JSONファイルの例を見てみましょう。

The maximum sweetness we can bring is: 365.0
We'll bring:
27 A Chocolates,
2 B Chocolates,
16 C Chocolates,
2 D Chocolates

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

出力（例のJSONファイルを入力として使用した場合）。

# 1 - - - - - - - - -
# 2 - - - - - - - - -
# 3 - - - - - - - - -
# 4 - - - - - - - - -
# 5 - - - - - - - - -
# 6 - - - - - - - - -
# 7 - - - - - - - - -
# 8 - - - - - - - - -
# 9 - - - - - - - - -
#   1 2 3 4 5 6 7 8 9


import constraint
import json


problem = constraint.Problem()


# We're letting VARIABLES 11 through 99 have an interval of [1..9]
for i in range(1, 10):
    problem.addVariables(range(i * 10 + 1, i * 10 + 10), range(1, 10))


# We're adding the constraint that all values in a row must be different
# 11 through 19 must be different, 21 through 29 must be all different,...
for i in range(1, 10):
    problem.addConstraint(constraint.AllDifferentConstraint(), range(i * 10 + 1, i * 10 + 10))


# Also all values in a column must be different
# 11,21,31...91 must be different, also 12,22,32...92 must be different,...
for i in range(1, 10):
    problem.addConstraint(constraint.AllDifferentConstraint(), range(10 + i, 100 + i, 10))


# The last rule in a sudoku 9x9 puzzle is that those nine 3x3 squares must have all different values,
# we start off by noting that each square "starts" at row indices 1, 4, 7
for i in [1,4,7]:
    # Then we note that it's the same for columns, the squares start at indices 1, 4, 7 as well
    # basically one square starts at 11, the other at 14, another at 41, etc
    for j in [1,4,7]:
        square = [10*i+j,10*i+j+1,10*i+j+2,10*(i+1)+j,10*(i+1)+j+1,10*(i+1)+j+2,10*(i+2)+j,10*(i+2)+j+1,10*(i+2)+j+2]
        # As an example, for i = 1 and j = 1 (bottom left square), the cells 11,12,13,
        # 21,22,23, 31,32,33 have to be all different
        problem.addConstraint(constraint.AllDifferentConstraint(), square)


file_name = input("Enter the name of the .json file containing the sudoku puzzle: ")
try:
    f = open(file_name, "r")
    board = json.load(f)
    f.close()
except IOError:
    print ("Couldn't open file.")
    sys.exit()


# We're adding a constraint for each number on the board (0 is an "empty" cell),
# Since they're already solved, we don't need to solve them
for i in range(9):
    for j in range(9):
        if board[i][j] != 0:
            def c(variable_value, value_in_table = board[i][j]):
                if variable_value == value_in_table:
                    return True


# Basically we're making sure that our program doesn't change the values already on the board
            # By telling it that the values NEED to equal the corresponding ones at the base board
            problem.addConstraint(c, [((i+1)*10 + (j+1))])


solutions = problem.getSolutions()


for s in solutions:
    print("==================")
    for i in range(1,10):
        print("|", end='')
        for j in range(1,10):
            if j%3 == 0:
                print(str(s[i*10+j])+" | ", end='')
            else:
                print(str(s[i*10+j]), end='')
        print("")
        if i%3 == 0 and i!=9:
            print("------------------")
    print("==================")


if len(solutions) == 0:
    print("No solutions found.")

注：パズルの中にすでにある値に触れないようにするコードの部分を見落とすのは非常に簡単です。

もし、この部分を無視してコードを実行しようとすると、プログラムは、想像を絶するようなすべての数独パズルを出題しようとするでしょう。無限ループになりかねない。

結論と難点

制約プログラミングは楽しく、異なるものですが、確かに欠点もあります。制約プログラミングを使って解決されるすべての問題は、等しいか（ほとんどの場合）より良いランタイムで命令文スタイルで書くことができます。

開発者は、 python-constraint に記述するよりも、問題をより良く理解するのは当然です。非常に重要なこととして、制約プログラミングは、状況によっては、実行時間が少し悪くなるのと引き換えに、何時間も何時間も開発時間を節約することができるということがあります。

私は最近、この実例に遭遇しました。私の友人で、Pythonの存在を数ヶ月前に知ったばかりの人が、彼女が取り組んでいる物理化学の研究プロジェクトで問題を解く必要がありました。

その友人は、次のような問題を解く必要がありました。

==================
|295 | 743 | 861 |
|431 | 865 | 927 |
|876 | 192 | 345 |
------------------
|387 | 459 | 216 |
|612 | 387 | 594 |
|549 | 216 | 783 |
------------------
|768 | 524 | 139 |
|923 | 671 | 458 |
|154 | 938 | 672 |
==================
==================
|295 | 743 | 861 |
|431 | 865 | 927 |
|876 | 192 | 345 |
------------------
|387 | 459 | 216 |
|612 | 387 | 594 |
|549 | 216 | 738 |
------------------
|763 | 524 | 189 |
|928 | 671 | 453 |
|154 | 938 | 672 |
==================
==================
|295 | 743 | 861 |
|431 | 865 | 927 |
|876 | 192 | 543 |
------------------
|387 | 459 | 216 |
|612 | 387 | 495 |
|549 | 216 | 738 |
------------------
|763 | 524 | 189 |
|928 | 671 | 354 |
|154 | 938 | 672 |
==================

これを命令型プログラミングでどう解くか、考えてみてください。

私は、命令形では良い解決策のアイデアさえ思いつきませんでした。少なくとも、制約プログラミングで彼女の問題を解決するのにかかった5分間、文字通り数行のコードでは無理でした。

Generate all combinations (that have a length equal to the number of keys) of values stored in a dictionary (the order of output doesn't matter). The dictionary is {String : List_of_Strings}. In such a way that every combination has exactly one value from the List_of_Strings of a key.


You don't know the number of keys in the dictionary in advance, nor do you know how long a List_of_String is, every List_of_String can be of different length. I.e. the dictionary is dynamically generated via user input.


Example input: dictionary = {"A" : [1,2], "B" -> [4], "C" -> [5,6,7], "D" -> [8,9]}
Example output: (1,4,5,8), (1,4,5,8), (1,4,6,8), (1,4,6,9), (1,4,7,8)....

それです。制約を加えなかっただけで、プログラムが許容できるすべての組み合わせを生成してくれたのです。彼女の場合、このプログラムの最小限の実行時間の差は、いかに早く書かれたか、いかに読みやすいか、ということほどには、全く重要ではないのです。

もう一つ注意すべきことは、python-constraintは単に組み合わせがすべての制約に合うかどうかを無心でテストする以上のことができる、ということです。

バックトラック(および再帰的バックトラック)の機能が実装されており、最小競合理論に基づいた問題解決も可能である。これらは .Problem() メソッドの引数として渡すことができます。例えば .Problem(BacktrackingSolver) で、後は上記の例と同じように行います。

内蔵された制約の一覧

パラメータとして乗数のリストを取ることができる制約（ExactSumやMinSumなど）を使用する場合、例Eで行ったように、必要に応じて順序や変数を明示的に言うように注意してください。

結論

制約処理プログラミングは、読みやすさとプログラムの開発のしやすさに関しては すばらしいものですが、その代償としてランタイムが犠牲になります。特定の問題に対してどちらが重要かを決めるのは、開発者次第です。