Python-constraint and sudoku

For people who don’t know what is constraint programming, please read this first.

The programming constraint is a fast and good way for solving complex problems, but it comes with some difficulties. I personnaly start with Prolog at school, but Prolog got a syntax I definitely dislike, so I decide to continue with python-constraint, a good Python tool for solving constraint problems.

Let’s start to make a sudoku solver (even if it’s already exist in python-constraint’s examples, I provide here a more « readable » solver) :
The sudoku got thoose rules :

  • Every 3×3 got a total sum of total = sum(range(1, 10)) => sum 1 to 9.
  • Every line and every column got that same sum.
  • Every number on a line or column is unique for this row/column.

If you already know constraint programming, you know we are already near to the end, when you are able to express constraint list from variable, you are already near the end !
Let’s apply this in python-constraint, I use this base to create the soduko version, so you will find same way of programming, and this article provide some usefull help if you need.

#Getting python constraint, the ./python-constraint-1.1 contains constraint.py file
import sys, math
sys.path.append("./python-constraint-1.1")

#Importing constraint
from constraint import *

def solveSudoku(size = 9, originalGame = None):
	""" Solving Sudoku of any size """
	sudoku = Problem()

	#Defining size of row/col
	rows = range(size)
	cols = range(size)

	#every line got same sum
	lineSum = sum(range(1, size+1))

	#Creating board
	board = [(row, col) for row in rows for col in cols]
	#Defining game variable, a single range will be enough
	sudoku.addVariables(board, range(1, size * size + 1))

	#Row set
	rowSet = [zip([el] * len(cols), cols) for el in rows]
	colSet = [zip(rows, [el] * len(rows)) for el in cols]

	#The original board is not empty, we add that constraint to the list of constraint
	if originalGame is not None:
		for i in range(0, size):
			for j in range(0, size):
				#Getting the value of the current game
				o = originalGame[i][j]
				#We apply constraint when the number is set only
				if o > 0:
					#We get the associated tuple
					t = (rows[i],cols[j])
					#We set a basic equal constraint rule to force the system to keep that variable at that place
					sudoku.addConstraint(lambda var, val=o: var == val, (t,))

	#The constraint are like that : and each row, and each columns, got same final compute value, and are all unique
	for row in rowSet:
		sudoku.addConstraint(ExactSumConstraint(lineSum), row)
		sudoku.addConstraint(AllDifferentConstraint(), row)
	for col in colSet:
		sudoku.addConstraint(ExactSumConstraint(lineSum), col)
		sudoku.addConstraint(AllDifferentConstraint(), col)

	#Every sqrt(size) (3x3 box constraint) got same sum
	sqSize = int(math.floor(math.sqrt(size)))

	#xrange allow to define a step, here sq (wich is sq = 3 in 9x9 sudoku)
	for i in xrange(0,size,sqSize):
		for j in xrange(0,size,sqSize):
			#Computing the list of tuple linked to that box
			box = []
			for k in range(0, sqSize):
				for l in range(0, sqSize):
					#The tuple i+k, j+l is inside that box
					box.append( (i+k, j+l) )
			#Compute is done, now we can add the constraint for that box
			sudoku.addConstraint(ExactSumConstraint(lineSum), box)
			sudoku.addConstraint(AllDifferentConstraint(), box)

	#Computing and returning final result
	return sudoku.getSolution()


if __name__ == '__main__':
	rg = 9
	initValue = [[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]]

	res = solveSudoku(rg, initValue)
	print
	if res is not None:
		for i in range(0, rg):
			for j in range(0, rg):
				print res[i, j],
			print
		print
	else:
		print "No result to show"

Let’s explain it a little :

  • We create two list : rows and cols. We create a board, a list of tuples from rows/cols (we got inside (0, 0), (0, 1), (0, 2)…)
  • Then from board, we get the list of tuples for each row, and each column
  • After that, if the original map got some value, we create constraint to limit to that values already setted
  • Finally we create constraint for each row/col, and for each 3×3 boxes. And resole this !

Now if you compare this version with the example given in official python-constraint, you will see that to solve the most complex sudoku our algorithm takes approx 40sec while the example one is around 0sec to solve it ! Why this difference ?

The answser is simple : domain and compute. On this version we do not lock the domain to specific value, we let the system find the domain by itself, which can lead to some performance hit (here some system may take 0 to 45 (sum 1 to 9) instead of 1 to 9 possibilities for each cases). And, in a more unhealthy way, everytime the system try to check a constraint, it has to compute many sum. To correct that, the easy way is just to change little bit our constraints system :

  • Every line/row and 3×3 box got a set of unique number from 1 to size exactly
  • Every number can go from 1 to size included, not more

We first remove all computed checksum, and also, we makes a tinyer domain by forcing the system to choose from 1 to size, and not from 1 to sum (sum > size, so it will makes less compute). After that modification, this version run as fast as the one given in python-constraint example (less than a second) :

#Getting python constraint, the ./python-constraint-1.1 contains constraint.py file
import sys, math
sys.path.append("./python-constraint-1.1")

#Importing constraint
from constraint import *

def solveSudoku(size = 9, originalGame = None):
	""" Solving Sudoku of any size """
	sudoku = Problem()

	#Defining size of row/col
	rows = range(size)
	cols = range(size)

	#Creating board
	board = [(row, col) for row in rows for col in cols]
	#Defining game variable, a single range will be enough
	sudoku.addVariables(board, range(1, size * size + 1))

	#Row set
	rowSet = [zip([el] * len(cols), cols) for el in rows]
	colSet = [zip(rows, [el] * len(rows)) for el in cols]

	#Limit the entry set to 1 to size included only
	sudoku.addConstraint( InSetConstraint( range(1, size+1) ) )

	#The original board is not empty, we add that constraint to the list of constraint
	if originalGame is not None:
		for i in range(0, size):
			for j in range(0, size):
				#Getting the value of the current game
				o = originalGame[i][j]
				#We apply constraint when the number is set only
				if o > 0:
					#We get the associated tuple
					t = (rows[i],cols[j])
					#We set a basic equal constraint rule to force the system to keep that variable at that place
					sudoku.addConstraint(lambda var, val=o: var == val, (t,))

	#The constraint are like that : and each row, and each columns, got same final compute value

	for row in rowSet:
		sudoku.addConstraint(AllDifferentConstraint(), row)
	for col in colSet:
		sudoku.addConstraint(AllDifferentConstraint(), col)

	#Every sqrt(size) (3x3 box constraint) got same sum
	sqSize = int(math.floor(math.sqrt(size)))

	#xrange allow to define a step, here sq (wich is sq = 3 in 9x9 sudoku)
	for i in xrange(0,size,sqSize):
		for j in xrange(0,size,sqSize):
			#Computing the list of tuple linked to that box
			box = []
			for k in range(0, sqSize):
				for l in range(0, sqSize):
					#The tuple i+k, j+l is inside that box
					box.append( (i+k, j+l) )
			#Compute is done, now we can add the constraint for that box
			sudoku.addConstraint(AllDifferentConstraint(), box)

	#Computing and returning final result
	return sudoku.getSolution()


if __name__ == '__main__':
	rg = 9
	#World hardest sudoku
	initValue = [[0, 0, 5, 3, 0, 0, 0, 0, 0],
				[8, 0, 0, 0, 0, 0, 0, 2, 0],
				[0, 7, 0, 0, 1, 0, 5, 0, 0],
				[4, 0, 0, 0, 0, 5, 3, 0, 0],
				[0, 1, 0, 0, 7, 0, 0, 0, 6],
				[0, 0, 3, 2, 0, 0, 0, 8, 0],
				[0, 6, 0, 5, 0, 0, 0, 0, 9],
				[0, 0, 4, 0, 0, 0, 0, 3, 0],
				[0, 0, 0, 0, 0, 9, 7, 0, 0]]

	res = solveSudoku(rg, initValue)
	print
	if res is not None:
		for i in range(0, rg):
			for j in range(0, rg):
				print res[i, j],
			print
		print
	else:
		print "No result to show"

In that code, we remove all « ExactSumConstraint » constraint, and add the InSetConstraint to limit domain on all variable (here all variable = all sudoku cases). This help the constraint algorithm to not try un-reachable possibilities. Doing so, it runs pretty fast ! You can found the pastebin of that final code here

Publicités

Laisser un commentaire

Entrez vos coordonnées ci-dessous ou cliquez sur une icône pour vous connecter:

Logo WordPress.com

Vous commentez à l'aide de votre compte WordPress.com. Déconnexion / Changer )

Image Twitter

Vous commentez à l'aide de votre compte Twitter. Déconnexion / Changer )

Photo Facebook

Vous commentez à l'aide de votre compte Facebook. Déconnexion / Changer )

Photo Google+

Vous commentez à l'aide de votre compte Google+. Déconnexion / Changer )

Connexion à %s

%d blogueurs aiment cette page :