برنامه نویسی محدودیت با python-محدودیت

معرفی

اولین چیزی که در هنگام پرداختن به برنامه نویسی محدودیت باید بدانیم این است که روش تفکر با طرز فکر معمول ما زمانی که برای نوشتن کد می نشینیم بسیار متفاوت است.

برنامه نویسی محدودیت نمونه ای از این است اعلامی پارادایم برنامه نویسی، بر خلاف معمول امری ضروری پارادایم که ما بیشتر اوقات از آن استفاده می کنیم.

پارادایم برنامه نویسی چیست؟

پارادایم به معنای «نمونه» یا «الگوی» چیزی است. یک پارادایم برنامه نویسی اغلب به عنوان “شیوه تفکر” یا “راه برنامه نویسی” توصیف می شود. رایج ترین نمونه ها از جمله برنامه ریزی رویه ای (به عنوان مثال C) برنامه نویسی شی گرا (مثلا جاوا) و برنامه نویسی تابعی (مثلا هسکل).

اکثر پارادایم های برنامه نویسی را می توان به عنوان عضوی از گروه پارادایم امری یا اعلانی طبقه بندی کرد.

تفاوت بین برنامه نویسی امری و اعلامی چیست؟

• امری ضروری برنامه نویسی، به زبان ساده، مبتنی است روی توسعه دهنده راه حل/الگوریتم را برای دستیابی به یک هدف (نوعی نتیجه) توصیف می کند. این با تغییر وضعیت برنامه از طریق دستورات انتساب، در حالی که دستورالعمل ها را به صورت گام به گام اجرا می کنند، اتفاق می افتد. بنابراین تفاوت زیادی در ترتیب نوشته شدن دستورالعمل ها ایجاد می کند.
• اعلامی برنامه نویسی برعکس عمل می کند – ما مراحل را نمی نویسیم روی چگونه به یک هدف برسیم، هدف را شرح می دهیمو کامپیوتر راه حلی به ما می دهد. یک مثال رایج که باید با آن آشنا باشید SQL است. به کامپیوتر میگی چگونه تا به شما نتایج مورد نیاز را بدهد؟ نه.

نصب کردن pythonماژول محدودیت

در این مقاله با ماژولی به نام کار خواهیم کرد python-constraint (توجه: یک ماژول به نام “محدودیت” برای پایتون وجود دارد، این چیزی نیست که ما می خواهیم)، که هدف آن آوردن ایده برنامه نویسی محدودیت به پایتون است.

برای نصب این ماژول، آن را باز کنید terminal و اجرا:

$ pip install python-constraint

مبانی استفاده python-محدودیت

این اسکلت تعمیم یافته برنامه هایی است که با استفاده از این ماژول نوشته شده اند (توجه: ما استفاده می کنیم import constraint و نه import python-constraint)

• import constraint
• یک متغیر را به عنوان مشکل ما تعریف کنیم
• متغیرها و فواصل مربوط به آنها را به مشکل خود اضافه کنید
• محدودیت های داخلی/سفارشی را به مشکل خود اضافه کنید
• راه حل ها را بیاورید
• راه حل ها را برای یافتن راه حل های مورد نیاز خود دنبال کنید

همانطور که قبلا ذکر شد، برنامه نویسی محدودیت شکلی از برنامه نویسی اعلانی است. ترتیب اظهارات مهم نیست، تا زمانی که همه چیز در پایان وجود دارد. معمولاً برای حل مشکلاتی مانند زیر استفاده می شود:

مثال الف

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. این کار در چند خط کد و در چند دقیقه با استفاده از برنامه نویسی محدودیت انجام می شود.

با نگاه کردن به مشکل بالا احتمالا فکر کردید “پس چی؟ من می توانم این کار را با 2 حلقه و نصف فنجان قهوه در پایتون در کمتر از 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()






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)}

بیایید قدم به قدم این برنامه را مرور کنیم. ما دو متغیر داشتیم، x و y. ما آنها را با محدوده قابل قبول مربوطه به مشکل خود اضافه کرده ایم.

این دو خط به معنای زیر است:

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)

توجه داشته باشید: در مورد ما مهم نیست که بنویسیم (x,y) یا (y,x) به عنوان پارامتر دوم ما، اما ترتیب در بیشتر موارد مهم است.

پس از آن، ما راه حل ها را با problem.getSolutions() (لیستی از تمام ترکیبات مقادیر متغیر را که همه شرایط را برآورده می کنند برمی گرداند) و ما آنها را تکرار می کنیم.

توجه داشته باشید: برای مثال اگر بخواهیم فقط ترکیبات را در کجا واکشی کنیم x /= y، قبل از واکشی راه حل ها، یک محدودیت داخلی اضافه می کنیم:

problem.addConstraint(constraint.AllDifferentConstraint())

شما می توانید لیستی از تمام محدودیت های داخلی را پیدا کنید اینجا. این تقریباً همه چیزهایی است که شما باید بدانید تا بتوانید هر کاری از این نوع را انجام دهید.

نمونه های گرم کردن

مثال B

در اینجا نوعی از برنامه نویسی محدودیت مشکل وجود دارد که استفاده از آن سرگرم کننده است روی، تماس گرفت پازل های حسابی رمزی. در شکل زیر از پازل های حسابی رمزی، هر کاراکتر یک رقم متفاوت را نشان می دهد (شخصیت های اصلی نمی توانند 0 باشند):

TWO + TWO = FOUR

به این فکر کنید که چگونه با استفاده از پایتون معمولی این مشکل را حل می کنید. در واقع، من شما را تشویق می کنم که راه حل این مشکل را که از برنامه نویسی ضروری استفاده می کند، جستجو کنید.

همچنین باید تمام دانشی را که برای حل آن نیاز دارید به شما بدهد مثال D روی مال خودت

به خاطر داشته باشید که “T” و “F” نمی توانند صفر باشند زیرا آنها شخصیت های اصلی هستند، یعنی اولین رقم یک عدد.

import constraint

problem = constraint.Problem()





problem.addVariables("TF", range(1, 10))
problem.addVariables("WOUR", range(10))


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



problem.addConstraint(sum_constraint, "TWOFUR")



problem.addConstraint(constraint.AllDifferentConstraint())

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


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

مثال ج

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) نمی دانیم که داریم یا نه a از سکه های 1 سنت، b سکه های 3 سنت و غیره

بنابراین ما باید به صراحت print متغیر و مقدار آن یکی از پیامدهای این امر این است که ما نمی توانیم از داخلی استفاده کنیم .ExactSumConstraint() به شکل دو پارامتری خود، ExactSumConstraint(50,(1,3,5,10,20)).

پارامتر دوم در اینجا “وزن” هر متغیر است (چند بار باید ضرب شود) و ما هیچ تضمینی نداریم که کدام یک از متغیرهای ما چه وزنی داشته باشد.

این یک اشتباه رایج است که فرض کنیم وزن‌ها به ترتیب اضافه شدن متغیرها به متغیرها تخصیص داده می‌شوند، در عوض از فرم سه پارامتری این محدودیت داخلی در کد زیر استفاده می‌کنیم:

import constraint

problem = constraint.Problem()




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")
)













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")))
        
        
        

solutions = problem.getSolutions()

print("Total number of ways: {}".format(len(solutions)))

با اجرای این قطعه کد به دست می آید:

Total number of ways: 535

مثال D

CRASH + ERROR + REBOOT = HACKER

مثال B و D هنگام استفاده از محدودیت ها تقریباً یکسان هستند، فقط چند متغیر بالا و پایین و محدودیت های پرمخاطب تر. این یک چیز خوب در مورد برنامه نویسی محدودیت است – مقیاس پذیری خوب، حداقل زمانی که زمان صرف شده برای کدنویسی مربوط می شود. تنها یک راه حل برای این معما وجود دارد و آن A=3 B=7 C=8 E=2 H=6 K=0 O=1 R=5 S=9 T=4 است.

هر دوی این نوع کارها (مخصوصاً crypt-arthmetic) بیشتر برای سرگرمی و برای نشان دادن آسان روش عملکرد برنامه نویسی محدودیت استفاده می شود، اما شرایط خاصی وجود دارد که در آن برنامه نویسی محدودیت دارای ارزش عملی است.

می‌توانیم حداقل تعداد ایستگاه‌های پخش را برای پوشش یک منطقه خاص محاسبه کنیم، یا روش تنظیم چراغ‌های راهنمایی را به گونه‌ای که جریان ترافیک بهینه باشد، دریابیم. به طور کلی – از محدودیت ها در جایی استفاده می شود که ترکیبات احتمالی زیادی وجود دارد.

این مثال ها برای محدوده این مقاله بسیار پیچیده هستند، اما نشان می دهند که برنامه نویسی محدودیت می تواند در دنیای واقعی کاربرد داشته باشد.

مثال های سخت تر

مثال 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	100	8 × 2.5 × 0.5	20	8
شکلات B	45	7 × 2 × 0.5	16	6.8
شکلات سی	10	3 × 2 × 0.5	9	4
شکلات دی	25	3 × 3 × 0.5	7	3

حالا بیایید آستین ها را بالا بزنیم و شروع کنیم. اگر مثال های قبلی را فهمیده باشید نباید خیلی سخت باشد.

ابتدا متوجه می‌شویم که اگر فقط آن نوع شکلات را بیاوریم، چه مقدار از هر شکلات می‌توانیم داشته باشیم، بنابراین می‌توانیم حد بالایی فواصل خود را داشته باشیم. به عنوان مثال، برای شکلات 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))


def weight_constraint(a, b, c, d):
    if (a*100 + b*45 + c*10 + d*25) <= 3000:
        return True


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


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')))

با اجرای این قطعه کد به دست می آید:

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

توجه داشته باشید: ما می توانیم تمام اطلاعات مربوط به هر نوع شکلات را در یک فرهنگ لغت ذخیره کنیم، به عنوان مثال weight_dictionary = {'A' : 100, 'B' : 45, 'C' : 10, 'D' : 25}و دسترسی به مقادیر از این طریق، به جای هاردکد کردن آنها در توابع. با این حال، برای خوانایی، طول کد و تمرکز روی چیزهایی که برای این آموزش مهم تر است، ترجیح می دهم در خود توابع محدودیت هاردکد کنم.

توجه داشته باشید: احتمالاً متوجه شده اید که مدتی طول کشید تا این نتیجه محاسبه شود، این یک است اشکال برنامه نویسی محدودیت

مثال F

اکنون برای چیزهای سرگرم کننده تر – بیایید یک حل کننده سودوکو (9×9 کلاسیک) بسازیم. ما پازل را از یک فایل JSON می خوانیم و همه راه حل های آن معمای خاص را پیدا می کنیم (با فرض اینکه پازل راه حلی دارد).

اگر قوانین حل سودوکو را فراموش کرده اید:

• سلول ها می توانند مقادیر 1 – 9 داشته باشند
• همه سلول های یک ردیف باید مقادیر متفاوتی داشته باشند
• همه سلول های یک ستون باید مقادیر متفاوتی داشته باشند
• همه سلول‌های یک مربع 3×3 (در مجموع 9 خانه) باید مقادیر متفاوتی داشته باشند

یکی از مسائل این برنامه این است که چگونه مقادیر را ذخیره کنیم؟ ما نمی توانیم فقط یک ماتریس به عنوان یک متغیر به مشکل خود اضافه کنیم و پایتون را به شکل جادویی بفهمیم که ما چه می خواهیم.

ما از سیستمی استفاده می کنیم که در آن با اعداد مانند نام متغیرها رفتار می کنیم (که مجاز است) و وانمود می کنیم که ماتریس داریم. شاخص ها از (1,1) به جای معمول (0,0) شروع می شوند. با استفاده از آن، به عناصر تخته به روشی که به آن عادت کرده ایم دسترسی خواهیم داشت.

در مرحله بعد، ما باید بخش ساده ای را انجام دهیم که به پایتون بگوییم همه آن سلول ها می توانند مقادیری بین 1 و 9 داشته باشند.

سپس توجه می کنیم که سلول های یک ردیف دارای همان شاخص اول هستند، به عنوان مثال (1,x) برای ردیف اول. ما به راحتی می‌توانیم تمام ردیف‌ها را تکرار کنیم و بگوییم که تمام سلول‌ها باید مقادیر متفاوتی داشته باشند. در مورد ستون ها هم همینطور. بقیه با نگاه کردن به کد راحت تر قابل درک است.

بیایید به نمونه فایل JSON نگاهی بیندازیم:

((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))

import constraint
import json

problem = constraint.Problem()


for i in range(1, 10):
    problem.addVariables(range(i * 10 + 1, i * 10 + 10), range(1, 10))



for i in range(1, 10):
    problem.addConstraint(constraint.AllDifferentConstraint(), range(i * 10 + 1, i * 10 + 10))



for i in range(1, 10):
    problem.addConstraint(constraint.AllDifferentConstraint(), range(10 + i, 100 + i, 10))



for i in (1,4,7):
    
    
    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)
        
        
        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()



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

            
            
            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.")

خروجی (زمانی که از فایل JSON مثال خود به عنوان ورودی استفاده می کنیم):

==================
|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 |
==================

توجه داشته باشید: بسیار آسان است که بخشی از کد را نادیده بگیریم که مطمئن می شود مقادیر موجود در پازل را لمس نمی کنیم.

اگر می‌خواستیم کد را بدون آن قسمت اجرا کنیم، برنامه سعی می‌کرد تا با ALL SUDOKU PAZZLES IMAGINABLE ارائه شود. که ممکن است یک حلقه بی پایان باشد.

نتیجه گیری و اشکالات

همانطور که برنامه نویسی با محدودیت سرگرم کننده و متفاوت است، مطمئناً اشکالاتی دارد. هر مسئله حل شده با استفاده از برنامه نویسی محدودیت می تواند به سبک دستوری با زمان اجرا برابر یا (مانند اکثر موارد) بهتر نوشته شود.

طبیعی است که توسعه دهنده مشکل را بهتر از آن چیزی که بتواند آن را توصیف کند، درک کند python-constraint. نکته بسیار مهمی که باید به آن توجه کنید این است که برنامه نویسی با محدودیت در برخی شرایط می تواند ساعت ها و ساعت ها در زمان توسعه در ازای زمان اجرا کمی بدتر صرفه جویی کند.

من اخیراً یک مثال واقعی از این داشتم. یکی از دوستان من، کسی که فقط چند ماه قبل از وجود پایتون باخبر شده بود، باید برای یک پروژه تحقیقاتی شیمی فیزیک که در حال کار بود مشکلی را حل کند. روی.

آن دوست نیاز به حل مشکل زیر داشت:

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)....

سعی کنید و فکر کنید که چگونه می توانید این را با استفاده از برنامه نویسی ضروری حل کنید.

حتی نتونستم به فکرم برسه اندیشه یک راه حل خوب ضروری است. حداقل در 5 دقیقه ای که طول کشید تا مشکل او را در برنامه نویسی محدودیت حل کنم، به معنای واقعی کلمه چند خط از کد

import constraint


generated_dictionary = {'A' : (1,2), 'B' : (4), 'C' : (5,6,7), 'D' : (8,9)}

problem = constraint.Problem()

for key, value in generated_dictionary.items():
    problem.addVariable(key, value)

solutions = problem.getSolutions()

for solution in solutions:
    print(solution)

خودشه. ما فقط هیچ محدودیتی اضافه نکردیم و برنامه تمام ترکیبات قابل قبول را برای ما ایجاد کرد. در مورد او، حداقل تفاوت در زمان اجرا این برنامه از راه دور به اندازه سرعت نوشتن و خوانایی آن اهمیت ندارد.

نکته دیگری که باید به آن توجه کرد این است python-constraint می تواند بیش از آزمایش اینکه آیا یک ترکیب بدون توجه به همه محدودیت ها تناسب دارد یا خیر.

قابلیت‌های پس‌گرد (و بازگشت بازگشتی) پیاده‌سازی شده‌اند، و همچنین بر اساس حل‌کننده‌های مشکل روی نظریه حداقل تعارض اینها را می توان به عنوان یک استدلال به آن منتقل کرد .Problem() روش، به عنوان مثال .Problem(BacktrackingSolver)، بقیه به همان روشی که در مثال های بالا انجام می شود انجام می شود.

لیست محدودیت های داخلی

نام محدودیت	شرح محدودیت
AllDifferentConstraint	اعمال می کند که مقادیر همه متغیرهای داده شده متفاوت است
AllEqualConstraint	اجبار می کند که مقادیر همه متغیرهای داده شده برابر باشند
MaxSumConstraint	اجبار می کند که مقادیر متغیرهای داده شده تا یک مقدار معین جمع شوند
ExactSumConstraint	اجباری می کند که مقادیر متغیرهای داده شده دقیقاً با مقدار معینی جمع شوند
MinSumConstraint	اعمال محدودیت که مقادیر متغیرهای داده شده حداقل به یک مقدار معین جمع می شوند
InSetConstraint	اعمال محدودیت که مقادیر متغیرهای داده شده در مجموعه داده شده وجود دارد
NotInSetConstraint	اعمال محدودیت که مقادیر متغیرهای داده شده در مجموعه داده شده وجود ندارد
SomeInSetConstraint	اعمال محدودیت که حداقل برخی از مقادیر متغیرهای داده شده باید در یک مجموعه مشخص وجود داشته باشد
SomeNotInSetConstraint	اعمال محدودیت که حداقل برخی از مقادیر متغیرهای داده شده نباید در یک مجموعه مشخص وجود داشته باشد

هنگام استفاده از محدودیت‌هایی که می‌توانند فهرستی از ضرب‌کننده‌ها را به عنوان پارامتر در نظر بگیرند (مانند ExactSum یا MinSum) مراقب باشید که در صورت لزوم ترتیب یا متغیرها را به صراحت بیان کنید، مانند آنچه در این مورد انجام دادیم مثال E

نتیجه

برنامه نویسی محدودیت تا آنجا که به خوانایی و سهولت توسعه برنامه های خاص مربوط می شود شگفت انگیز است، اما این کار را به قیمت زمان اجرا انجام می دهد. این به توسعه دهنده بستگی دارد که تصمیم بگیرد کدام یک برای یک مشکل خاص برای او مهمتر است.