Question: http://oj.leetcode.com/problems/sudoku-solver/
Question Name: Sudoku Solver
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 | class Solution: class _State(object): __slot__ = ("board", "row", "col", "usedRow", "usedCol", "usedBlock") def __init__(self, board, row, col, usedRow, usedCol, usedBlock): self.board = [line*1 for line in board] # The whole board self.row = row # Next process position self.col = col # Next process position self.usedRow = usedRow # Appeared integers in rows self.usedCol = usedCol # Appeared integers in columns self.usedBlock = usedBlock # Appeared integers in blocks # @param board, a 9x9 2D array # Solve the Sudoku by modifying the input board in-place. # Do not return any value. def solveSudoku(self, board): # Convert the input (array of strings) to 2D array of integer char2int = {"1":1, "2":2, "3":4, "4":8, "5":16, "6":32, "7":64, "8":128, "9":256} boardMatrix = [[char2int.get(item, 0) for item in line] for line in board] stack = [] usedRow, usedCol, usedBlock = [0] * 9, [0] * 9, [] # Get the initially appeared integers in each row and column for i in xrange(9): usedRow[i] = sum(boardMatrix[i]) usedCol[i] = sum([line[i] for line in boardMatrix]) # Get the initially appeared integers in each block for iBlock in xrange(3): for jBlock in xrange(3): usedBlock.append(0) for i in xrange(3): for j in xrange(3): usedBlock[-1] = usedBlock[-1] | boardMatrix[iBlock*3+i][jBlock*3+j] stack.append(self._State(boardMatrix, 0, 0, usedRow, usedCol, usedBlock)) current = None # Do a DFS while len(stack) != 0: current = stack.pop() # Find the next empty cell to fill while current.row != 9 and current.board[current.row][current.col] != 0: current.col += 1 if current.col == 9: current.row += 1 current.col = 0 # Every cell is filled. It is a solution for the Sudoku if current.row == 9: break # Try to fill this cell with each integer for toAdd in char2int.values(): # Check whether this integer appears in the row/column/block or not if toAdd & current.usedRow[current.row] != 0: continue if toAdd & current.usedCol[current.col] != 0: continue if toAdd & current.usedBlock[(current.row//3)*3+current.col//3] != 0: continue # Create a new State for this filling and push it to the stqck current.board[current.row][current.col] = toAdd newUsedRow = current.usedRow * 1 newUsedRow[current.row] |= toAdd newUsedCol = current.usedCol * 1 newUsedCol[current.col] |= toAdd newUsedBlock = current.usedBlock * 1 newUsedBlock[(current.row//3)*3+current.col//3] |= toAdd stack.append(self._State(current.board, current.row, current.col, newUsedRow, newUsedCol, newUsedBlock)) # Find the solution for this Sudoku # Empty the input board del board[:] # Fill the board with the right solution int2char = {0:".", 1:"1", 2:"2", 4:"3", 8:"4", 16:"5", 32:"6", 64:"7", 128:"8", 256:"9"} result = ["".join([int2char[i] for i in line]) for line in current.board] for line in result: board.append(line) return |