Created
October 18, 2011 20:17
-
-
Save sahilgupta/1296588 to your computer and use it in GitHub Desktop.
Sudoku Puzzle solved using Constraint Satisfaction Programming(CSP) library 'constraint'
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #We only need to ensure unique values in every row, column and 3*3 blocks | |
| #The rest is done by the library. | |
| import constraint | |
| #Create the list of entire 81 variables, initialised to an empty set | |
| boxes = [] | |
| for i in 'A B C D E F G H I'.split(): | |
| k = [] | |
| for j in range(1,10): | |
| k.append(i+str(j)) | |
| boxes.append(k) | |
| #Create a new constraint Problem | |
| problem = constraint.Problem() | |
| #Adding the 'AllDifferent' constraint to the given set of variables | |
| def enforceUniqueValues(list_variables): | |
| problem.addConstraint(constraint.AllDifferentConstraint(), list_variables) | |
| #Adding all the variables and their possible valid range to the problem | |
| for row in boxes: | |
| problem.addVariables(row, range(1,10)) | |
| # enforce unique values in every row | |
| for row in boxes: | |
| enforceUniqueValues(row) | |
| # enforce unique values in every column | |
| for column in zip(*boxes): | |
| enforceUniqueValues(column) | |
| # enforce unique value in each small square | |
| for n in xrange(1,10): | |
| small_square = [] | |
| for j in range(3): | |
| small_square.extend(boxes[((n-1)/3)*3+j][((n-1)%3)*3:((n-1)%3)*3+3]) | |
| enforceUniqueValues(small_square) | |
| def solve(matrix): | |
| #Need to assign the existing values to the variables and hence the enumeration! | |
| for (index, val) in enumerate(sum(matrix, [])): | |
| if val is not None: | |
| problem.addConstraint(lambda var, val=val: var==int(val), variables= [boxes[index/9][index%9]]) | |
| #Find the solution | |
| soln = problem.getSolution() | |
| if soln is None: | |
| print "The given Sudoku is not solvable!" | |
| # soln is a dictionary of indices to values | |
| values = (v for (k, v) in sorted(soln.iteritems(), key=lambda (k, v): k)) | |
| cols = len(matrix) | |
| lis = [] | |
| #Print the solved Sudoku | |
| for value in values: | |
| lis.append(value) | |
| for i in range(9): | |
| print lis[i*9:i*9+9] | |
| sudoku = ''' | |
| X 4 X X X X X X X | |
| X X X X X 6 5 X 4 | |
| 3 6 X X 5 8 9 X X | |
| 9 8 X X X X X X X | |
| X X X 5 7 2 X X X | |
| X X X X X X X 4 1 | |
| X X 3 7 2 X X 5 9 | |
| 2 X 5 8 X X X X X | |
| X X X X X X X 3 X | |
| ''' | |
| sudoku2 = ''' | |
| X X X 9 X 1 X X 7 | |
| X X X X X X X X X | |
| X 8 6 X X X 4 X X | |
| 9 X X 2 X X X X X | |
| X X X X 4 X 8 X X | |
| 1 X X X X X X X X | |
| X 4 X X X X X X X | |
| X X X 5 X X X X 9 | |
| X 2 X X 8 X 6 X X | |
| ''' | |
| def sudoku_to_matrix(s): | |
| m = [] | |
| for line in s.split('\n'): | |
| if len(line) == 0: | |
| continue | |
| line = line.split() | |
| for (i, token) in enumerate(line): | |
| if token == 'X': | |
| line[i] = None | |
| m.append(line) | |
| return m | |
| solve(sudoku_to_matrix(sudoku2)) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment