#!/usr/bin/env python """ Sudoku | Sam Auciello | March 2011 A Sudoku solving program using Knuth's dancing links algorithm. According to Wikipedia: Sudoku is a logic-based, combinatorial number-placement puzzle. The objective is to fill a 9x9 grid with digits so that each column, each row, and each of the nine 3x3 sub-grids that compose the grid (also called "boxes", "blocks", "regions", or "sub-squares") contains all of the digits from 1 to 9. The puzzle setter provides a partially completed grid, which typically has a unique solution. An example of a sudoku puzzle: 2 | 4 | 1 1 4 | 9 | 7 | 1 | 3 ----------------------- 7 3 | 4 | 6 5 | | 9 8 | 1 | 7 5 ----------------------- 1 | 2 | 2 | 6 | 8 7 8 | 3 | 6 And its solution: 2 3 6 | 5 4 7 | 8 1 9 1 4 8 | 3 6 9 | 5 7 2 7 5 9 | 8 1 2 | 3 6 4 ----------------------- 8 7 3 | 9 5 4 | 6 2 1 6 1 5 | 2 7 3 | 9 4 8 4 9 2 | 1 8 6 | 7 5 3 ----------------------- 9 6 1 | 7 2 8 | 4 3 5 3 2 4 | 6 9 5 | 1 8 7 5 8 7 | 4 3 1 | 2 9 6 The puzzle can be reduced to an exact cover problem by considdering the rules of the puzzle as 4 types of constraints. 1. Each space must have exactly one number 2. Each row must have exactly one of each number 3. Each column must have exactly one of each number 4. Each box must have exactly one of each number Then considder that from a blank grid there are 729 moves we can make. (9 possible numbers times 81 possible spaces). Each of these moves satisfies one of each of the four types of constraints listed above and eliminates the possibility of any of the moves that also satisfies the same constraint. For example, if I choose to put a 3 in the second space of the top row, I eliminate the possibility of later putting a 6 in that space since both moves satisfy the constraint of there being exactly 1 number in that space. To turn this problem into the exact cover problem, simply represent constraints with columns in a matrix and represent possible moves with rows in a matrix containing a 1 in each column for which that move satisfies that constraint and a 0 otherwise. Solving the exact cover problem on this matrix will give a subset of the rows corrosponding to the moves that can be made to solve the puzzle. Since we are already given some numbers at the start of a sudoku puzzle, it is useful to considder them as moves already made. We must start by removing all rows in the matrix that conflict with moves already made and for this reason we call the reduce sub-routine from the dancing links algorithm on each row that corresponds to a move already made. Then we call the solve routine and get our answer. Some help came from http://code.google.com/p/narorumo/wiki/SudokuDLX """ # Includes # from dancing_links import Matrix import random # Constants # DEBUG = False VERBOSE = True VISUALIZE = False # Classes # class Array() : """ A constraint matrix that can be solved by the dancing links algorithm representing a sudoku puzzle. Each row in the matrix represents a particular number that could be in particular space in the puzzle (not taking into account the numbers already filled in). There are thus 9*81 or 729 rows. The first 81 columns represent the constraint that a particular space in the puzzle must be filled exactly once. Each row contains 1 in the column corrosponding to the space it fills. The next 81 columns represent the constraint that a particular row must have exactly one of each number. Each row contains a 1 in the column corrosponding to the row its fills with the number it fills it with. The final 162 columns are the same as the previous 81 except that they corrospond to columns and boxes instead of rows. Rather than actually generate a 729x324 two dimentional list we take advantage of the fact that python is duck-typed and instead create an object that acts like a two dimentional list and pretends to have 1s in the right places. """ def __init__(self) : """ Since the intial matrix contains all possibilities there are no variables and thus nothing to initialize. The object exists to fool python into thinking its a list of lists """ pass def __getitem__(self, index) : """ Returns an object representing a row of the matrix """ number = (index % 9) + 1 space = index / 9 col = space % 9 row = space / 9 box = (row - (row % 3)) + (col / 3) return ArrayRow(number, space, col, row, box) def __len__(self) : """ Returns the number of rows """ return 81 * 9 class ArrayRow() : """ A row of the constraint matrix """ def __init__(self, number, space, col, row, box) : """ Initialize the parameters of the row """ self.number = number self.space = space self.col = col self.row = row self.box = box def __getitem__(self, index) : """ Returns a 1 or 0 depending on whether the row meets the constraint corrosponding to the specified column """ if isinstance(index, slice) : # If a slice is asked for generate the # full list and slice it return self.list()[index.start:index.stop:index.step] if 0 <= index <= 80 : # Each space must be filled once if index == self.space : return 1 return 0 if 81 <= index <= 161 : # Each row must contain each number number = ((index - 81) % 9) + 1 row = ((index - 81) / 9) if number == self.number and row == self.row : return 1 return 0 if 162 <= index <= 242 : # Each column must contain each number number = ((index - 162) % 9) + 1 col = ((index - 162) / 9) if number == self.number and col == self.col : return 1 return 0 if 243 <= index <= 323 : # Each box must contain each number number = ((index - 243) % 9) + 1 box = ((index - 243) / 9) if number == self.number and box == self.box : return 1 return 0 def __len__(self) : """ Returns the number of columns """ return 81 * 4 def list(self) : """ Returns the row as a list for use in building links """ # This almost defeats the point but I realized it was necessary too # late and it should work anyway return [self[i] for i in range(81 * 4)] class Puzzle() : """ A sudoku puzzle that can be solved using the Knuth Dancing Links algorithm """ def __init__(self, grid) : """ Initialize the puzzle """ self.grid = grid def __repr__(self) : """ A text based representation of the puzzle """ # This could stand to be DRYed out a bit but it'll do for now. out = "" for row in self.grid[0:3] : for number in row[0:3] : if number == None : out += " " else : out += " " + str(number) out+= " |" for number in row[3:6] : if number == None : out += " " else : out += " " + str(number) out+= " |" for number in row[6:9] : if number == None : out += " " else : out += " " + str(number) out += "\n" out += "-----------------------\n" for row in self.grid[3:6] : for number in row[0:3] : if number == None : out += " " else : out += " " + str(number) out+= " |" for number in row[3:6] : if number == None : out += " " else : out += " " + str(number) out+= " |" for number in row[6:9] : if number == None : out += " " else : out += " " + str(number) out += "\n" out += "-----------------------\n" for row in self.grid[6:9] : for number in row[0:3] : if number == None : out += " " else : out += " " + str(number) out+= " |" for number in row[3:6] : if number == None : out += " " else : out += " " + str(number) out+= " |" for number in row[6:9] : if number == None : out += " " else : out += " " + str(number) out += "\n" return out def solve(self, returnCount=False) : """ Generate a constraint matrix, reduce it for each known value in the grid and then solve it using the dancing links algorithm """ if VERBOSE : print "\nSUDOKU\n" + str(self) matrix = Matrix(Array()) if VERBOSE : print "Reducing the grid using given numbers..." for row in range(9) : # Iterate through spaces in the grid for col in range(9) : number = self.grid[row][col] if number != None : # Reduce using know value matrixCol = 9 * row + col matrixRow = 9 * matrixCol + number - 1 matrix[matrixRow, matrixCol].reduce() if VERBOSE : print "Running Dancing Links..." solutions = matrix.solve() # Run dancing links if VERBOSE : print "Returing solution to grid form..." if len(solutions) > 0 : solution = solutions[0] # Translate solution back onto the grid for rowIndex in solution : number = (rowIndex % 9) + 1 space = rowIndex / 9 col = space % 9 row = space / 9 self.grid[row][col] = number if VISUALIZE : print self if returnCount : return matrix.root.counter return self return "No solution" if __name__ == "__main__" : a = Puzzle([ [ 9, None, None, 1, 4, 2, None, None, 5], [None, 1, None, None, None, 8, 7, None, None], [ 2, None, None, None, 6, None, None, None, 1], [None, 7, 4, None, None, 6, None, 5, None], [None, 5, None, 7, None, 1, None, 3, None], [None, 6, None, 8, None, None, 2, 1, None], [ 7, None, None, None, 8, None, None, None, 4], [None, None, 3, 6, None, None, None, 2, None], [ 5, None, None, 4, 1, 9, None, None, 3] ]) print a.solve() a = Puzzle([ [ 2, None, None, None, 4, None, None, 1, None], [ 1, 4, None, None, None, 9, None, 7, None], [None, None, None, None, 1, None, 3, None, None], [None, 7, 3, None, None, 4, None, None, None], [ 6, None, 5, None, None, None, 9, None, 8], [None, None, None, 1, None, None, 7, 5, None], [None, None, 1, None, 2, None, None, None, None], [None, 2, None, 6, None, None, None, 8, 7], [None, 8, None, None, 3, None, None, None, 6] ]) print a.solve()