Advertisement
Guest User

Python python-constraint sudoku solver

a guest
Nov 2nd, 2012
664
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #Getting python constraint, the ./python-constraint-1.1 contains constraint.py file
  2. import sys, math
  3. sys.path.append("./python-constraint-1.1")
  4.  
  5. #Importing constraint
  6. from constraint import *
  7.  
  8. def solveSudoku(size = 9, originalGame = None):
  9.     """ Solving Sudoku of any size """
  10.     sudoku = Problem()
  11.  
  12.     #Defining size of row/col
  13.     rows = range(size)
  14.     cols = range(size)
  15.  
  16.     #Creating board
  17.     board = [(row, col) for row in rows for col in cols]
  18.     #Defining game variable, a single range will be enough
  19.     sudoku.addVariables(board, range(1, size * size + 1))
  20.  
  21.     #Row set
  22.     rowSet = [zip([el] * len(cols), cols) for el in rows]
  23.     colSet = [zip(rows, [el] * len(rows)) for el in cols]
  24.  
  25.     sudoku.addConstraint( InSetConstraint( range(1, size+1) ) )
  26.  
  27.     #The original board is not empty, we add that constraint to the list of constraint
  28.     if originalGame is not None:
  29.         for i in range(0, size):
  30.             for j in range(0, size):
  31.                 #Getting the value of the current game
  32.                 o = originalGame[i][j]
  33.                 #We apply constraint when the number is set only
  34.                 if o > 0:
  35.                     #We get the associated tuple
  36.                     t = (rows[i],cols[j])
  37.                     #We set a basic equal constraint rule to force the system to keep that variable at that place
  38.                     sudoku.addConstraint(lambda var, val=o: var == val, (t,))
  39.  
  40.     #The constraint are like that : and each row, and each columns, got same final compute value
  41.  
  42.     for row in rowSet:
  43.         sudoku.addConstraint(AllDifferentConstraint(), row)
  44.     for col in colSet:
  45.         sudoku.addConstraint(AllDifferentConstraint(), col)
  46.  
  47.     #Every sqrt(size) (3x3 box constraint) got same sum
  48.     sqSize = int(math.floor(math.sqrt(size)))
  49.  
  50.     #xrange allow to define a step, here sq (wich is sq = 3 in 9x9 sudoku)
  51.     for i in xrange(0,size,sqSize):
  52.         for j in xrange(0,size,sqSize):
  53.             #Computing the list of tuple linked to that box
  54.             box = []
  55.             for k in range(0, sqSize):
  56.                 for l in range(0, sqSize):
  57.                     #The tuple i+k, j+l is inside that box
  58.                     box.append( (i+k, j+l) )
  59.             #Compute is done, now we can add the constraint for that box
  60.             sudoku.addConstraint(AllDifferentConstraint(), box)
  61.  
  62.     #Computing and returning final result
  63.     # return sudoku.getSolutions()
  64.     return sudoku.getSolution()
  65.  
  66.  
  67. if __name__ == '__main__':
  68.     rg = 9
  69.     #World hardest sudoku
  70.     initValue = [[0, 0, 5, 3, 0, 0, 0, 0, 0],
  71.                 [8, 0, 0, 0, 0, 0, 0, 2, 0],
  72.                 [0, 7, 0, 0, 1, 0, 5, 0, 0],
  73.                 [4, 0, 0, 0, 0, 5, 3, 0, 0],
  74.                 [0, 1, 0, 0, 7, 0, 0, 0, 6],
  75.                 [0, 0, 3, 2, 0, 0, 0, 8, 0],
  76.                 [0, 6, 0, 5, 0, 0, 0, 0, 9],
  77.                 [0, 0, 4, 0, 0, 0, 0, 3, 0],
  78.                 [0, 0, 0, 0, 0, 9, 7, 0, 0]]
  79.     # initValue = [[0, 9, 0, 7, 0, 0, 8, 6, 0],
  80.                 # [0, 3, 1, 0, 0, 5, 0, 2, 0],
  81.                 # [8, 0, 6, 0, 0, 0, 0, 0, 0],
  82.                 # [0, 0, 7, 0, 5, 0, 0, 0, 6],
  83.                 # [0, 0, 0, 3, 0, 7, 0, 0, 0],
  84.                 # [5, 0, 0, 0, 1, 0, 7, 0, 0],
  85.                 # [0, 0, 0, 0, 0, 0, 1, 0, 9],
  86.                 # [0, 2, 0, 6, 0, 0, 0, 5, 0],
  87.                 # [0, 5, 4, 0, 0, 8, 0, 7, 0]]
  88.  
  89.     res = solveSudoku(rg, initValue)
  90.     print
  91.     if res is not None:
  92.         # for r in res:
  93.             # for i in range(0, rg):
  94.                 # for j in range(0, rg):
  95.                     # print r[i, j],
  96.                 # print
  97.             # print
  98.         for i in range(0, rg):
  99.             for j in range(0, rg):
  100.                 print res[i, j],
  101.             print
  102.         print
  103.     else:
  104.         print "No result to show"
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement