We love designing and developing websites, but what really drives us is solving problems and cultivating strong relationships with our clients
Constraint programming in Python
By : shabda
Imagine this, you want to solve a problem, the algorithm for which you do not know. You just know the problem.
From wikipedia,
Constraints differ from the common primitives of imperative programming languages in that they do not specify a step or sequence of steps to execute, but rather the properties of a solution to be found.
Assume that there exists an alternate world where you only need to specify the problem, the computer will find out an algorithm to find it, even better if could you write it in Python.
Stop assuming it hapens every day, and this is the magic of constraint programming.
Example to solve a + b = 5, a*b=6, don't explain algebra, just tell the relations between variables. Here is the complete program.
from constraint import *
problem = Problem()
problem.addVariable('a', range(5))
problem.addVariable('b', range(5))
problem.addConstraint(lambda a, b: a + b == 5)
problem.addConstraint(lambda a, b: a * b == 6)
problem.getSolutions()
Don't worry if this doesn't make sense yet, we will explain it in a lot of detail. Also we cheated a little, by assuming that the solutions are positive integers.
Files required
You need a constraint library, which allows ypu to do constraint programming. python-constraints from Gustavo Niemeyer is an excellent library to do constraint programming, which we will use here. Download and install python-constraint from here.
After you setup, you should be able to do import constraint on a python shell
On to our program
Ok lets see the same program with cpomments.
from constraint import * #imports
problem = Problem() #Create a blank problem where we can add solutions.
problem.addVariable('a', range(5+1)) #Add a variable named a, and specify its domain. Since a+b=5, a is a positive integer less than 5
problem.addVariable('b', range(5+1)) #Same thing with b
problem.addConstraint(lambda a, b: a + b == 5) # Tell the computer that a+b=5
problem.addConstraint(lambda a, b: a * b == 6) #tell the computer that a*b=6
print problem.getSolutions() #We are done, get the solutions.
Not much to explain after you see it with comments. We created two variables, and relation between them and got the answer.
Ok something better
Ok so the last example was cute, but can constraint programming can solve any harder problems? Lets try something harder, like umm, magic square. (How, original!)
So lets think, how can we represent our problem.
- We have a n*n board. Start with 3, So our board is [(0,0), (0,1) ...., (2,1), (2,2)
- Rows have a sum of sum(1 .... n*n+1)/size
- Cols have a sum of sum(1 .... n*n+1)/size
- Diagonals have a sum of sum(1 .... n*n+1)/size
- Thats all,
So without further ado, lets see the code.
from constraint import *
def solve_magic_square(size = 3):
"Get the magic square solution for any numbered square."
magic = Problem()#create a blank problem
rows = range(size)#Rows indices eg[0, 1, 2]
cols = range(size)#cols indices eg [0, 1, 2]
board_line_sum = sum(range(1, size*size+1))/size # What does each row, col and diag sum up to? Eg 15, for size 3
board = [(row, col) for row in rows for col in cols] # Cartesan of rows and col, eg [(0, 0), (0, 1), (1, 0), (1, 1)] for size = 2
row_set = [zip([el]*len(cols), cols) for el in rows]#A list of all the rows, eg [[(0, 0), (0, 1)], [(1, 0), (1, 1)]]
col_set = [zip(rows, [el]*len(rows)) for el in cols]#A list of all the columns, eg [[(0, 0), (1, 0)], [(0, 1), (1, 1)]]
diag1 = zip(rows, cols)#One of the diagonals, eg [(0,0), (0,1)]
diag2 = zip(rows, cols[::-1])#Other diagonal, eg [(0,1), (1,0)]
magic.addVariables(board, range(1, size*size+1))#add Each block of square as a variable. There range is between [1..n*n+1]
magic.addConstraint(ExactSumConstraint(board_line_sum), diag1)#Add diagonals as a constraint, they must sum to board_line_sum
magic.addConstraint(ExactSumConstraint(board_line_sum), diag2)#Add other diagonal as constraint.
for row in row_set:
magic.addConstraint(ExactSumConstraint(board_line_sum), row)#Add each row as constraint, they must sum to board_line_sum
for col in col_set:
magic.addConstraint(ExactSumConstraint(board_line_sum), col)#Similarly add each column as constraint.
magic.addConstraint(AllDifferentConstraint(), board)#Every block has a different number.
return magic.getSolution()Retutn the solution.
if __name__ == '__main__':
print solve_magic_square()
Not much to explain again after you see the commented code. We created a board, added constraints and got solution.
Labix has a different implementation if how to solve the magic square.
What more can I do?
Constraint programming has a wide application, wherever you can specify the problem as relation between variables you can use constraint programming. Next step for you is to write a function, which takes a Sudoku board as input and returns a solved Sudoku board. SO get cracking.
Want to build an Amazing Web application? We can help? Contact us today!
Comments
There's a section of SICP about the properties and implementation of constraint-based systems, if you're interested in more on this topic.
I know about constraint programming. It's just a way to get some interresting output by feeding the beast the proper variables et cetera... but hell I don't see any problem that could be usefull to be solved that way and that I would get an application with it online... the sudoko is the *only* (among other math games) to be an entertaning example.
Could I use, this to get a 3D projections of my articles on 3 axes that sould be some sort of the three best combinaisons of tags which forms the best space to get the best "filling" on my data ? (I'm wondering is there a simple solution for that using CP)
Let's assume now that I want to find an article in the same database of tagged articles but with a 2D navigation, it should not take me more than five screen to get to my article. On each screen, I have to select a group au tags and in the 6th (or sooner) I should be able to select my article among 10.
I don't know if I made my point. Getting new way to navigate data is completly useless, guetting the result of sudoko could comes to be handy rainy days...
This is a completly honest question, "Constraint programming" where does it fit well in webdev ?
PS: I hate sudoko
This is very interesting and nicely written Python examples of this. python-constraints is fun!
seo（æœç´¢å¼•æ“Žå„ªåŒ–）是我們主è¦æ¥å‹™ï¼Œç‚ºå¤§åž‹ä¼æ¥ç¶²çµ¡æä¾›SEOæœå°‹å¼•æ“Žæœ€ä½³åŒ–解決方案；數åƒå®¶ä¸å¤§åž‹ä¼æ¥ç¶²ç«™ç‡ŸéŠ·ç–劃經驗，æä¾›ä¼æ¥SEO培訓，整站優化方案制定，整站優化實施，百度網站收錄æ¢å¾©ï¼Œç¶²ç«™é‡æ§‹å£¹æ¢é¾æœå‹™
Reactions
More info:The article is an introduction to Constraint Satisfaction Problems (CSP’s). http://en.wikipedia.org/wiki/Constraint_satisfaction_problem
A very rudimentary demonstration of this:http://aispace.org/constraint/sample2.html
Norvig implemented a quick and dirty version of this for his sudoku solver: http://norvig.com/sudoku.html.
Note, while you eventually end up just telling a CSP what you want, there’s a plethora of algorithms to solve these constraints.
This comment was originally posted on Hacker News
I think the example cheats a lot by assuming the solutions have to be positive integers. Is there a mechanism to tell the system "a and b are integers", and if so, could the system still solve the simultaneous equation?
This comment was originally posted on Hacker News
About solving systems of simultaneous equations, I don’t know if this particular solver can do it but many solvers can by using Gaussian Elimination from linear algebra.http://en.wikipedia.org/wiki/Gaussian_elimination
This comment was originally posted on Hacker News
This is basically logic programming. If you really want to do something like this, you are far better off just using a logic language like prolog and saving yourself the trouble.
This comment was originally posted on Hacker News
- How to use pep8.py to write better Django code
- Screencast: Django Tutorial Part 1
- How and why to use pyflakes to write better Python
- Getting started with South for Django DB migrations
- A brief overview of Vagrant
- Writing jQuery plugins using Coffeescript
- Behind the Scenes: Request to Response
- Using SQLite Database with Android
- Haml for Django developers
- Coffeescript for Python programmers
- rails
- django
- linkroundup
- django opinion
- opinion
- business
- API
- appengine
- python
- satire
- startup
- Uncategorized
- marketing
- personal
- rambling
- search
- interviews
- seo-interviews
- 5startupideas
- ideas
- seo
- tips
- forms
- paypal
- utilities
- datetime
- web2.0
- Amazon
- algorithms
- presentations
- products
- pinax
- satchmo
- ecommerce
- microsoft
- yahoo
- book
- tutorial
- models
- aggreagtion
- meta
- India
- apps
- about
- CSS
- Design
- wordpress
- test slug
- vim
- urls
- reviews
- javascript
- xmpp
- emacs
- Typography
- Grid Theory
- Color Theory
- iphone
- android
- titanium
- mobile applications
- CSS3
- Browser Compatibility
- mobile
- jobs
- lamson
- django setup
- files
- upload
- jsTree
- hierarchical view
- web page
- Treeview
- coffeescript
- request
- response
- South
- django south
- django migration
- --fake
- screencasts
- February 2012
- January 2012
- December 2011
- October 2011
- September 2011
- July 2011
- June 2011
- April 2011
- February 2011
- January 2011
- December 2010
- November 2010
- October 2010
- September 2010
- June 2010
- April 2010
- March 2010
- January 2010
- December 2009
- November 2009
- October 2009
- September 2009
- August 2009
- July 2009
- June 2009
- April 2009
- March 2009
- February 2009
- November 2008
- October 2008
- June 2008
- May 2008
- April 2008
This might be a dumb question, but if we specify constraints, can we submit algorithms (in Python) to it and check whether it satisfies all the specified requirements of a solution?