LeetCode: Sudoku Solver Posted on January 18, 2018July 26, 2020 by braindenny Sudoku Solver Write a program to solve a Sudoku puzzle by filling the empty cells. Empty cells are indicated by the character ‘.’. You may assume that there will be only one unique solution. Github: code.dennyzhang.com Credits To: leetcode.com Leave me comments, if you have better ways to solve. ## https://code.dennyzhang.com/sudoku-solver ## Basic Ideas: backtracking ## For each '.', try with 0-9. ## If test has passed, keep moving forward ## Otherwise stop current thread ## ## Complexity: Time O(k), k is the count of '.', Space ? class Solution(object): def solveSudoku(self, board): """ :type board: List[List[str]] :rtype: void Do not return anything, modify board in-place instead. """ if len(board) != 9 or len(board[0]) != 9: return 0 _can_solve = self.mySolveSudoku(board, 0, 0) # print("can_solve: %d" % (can_solve)) def mySolveSudoku(self, board, irow, icol): # if irow > 6: # print("irow: %d, icol: %d" % (irow, icol)) # print board if irow == 9: return True irow2, icol2 = None, None if icol == 8: irow2, icol2 = irow+1, 0 else: irow2, icol2 = irow, icol + 1 if board[irow][icol] != '.': return self.mySolveSudoku(board, irow2, icol2) # try with all possibilities for i in xrange(9): value = chr(ord('1')+i) # Change contenxt: go further board[irow][icol] = value if self.isSudoku(board, irow, icol, value): if self.mySolveSudoku(board, irow2, icol2): return True # Restore context: only the outer-layer board[irow][icol] = '.' return False def isSudoku(self, board, irow, icol, value): # If we set board[irow][icol] to value, is it still a valid sudoku. for index in xrange(9): # check row if index == icol: continue if board[irow][index] == value: return False for index in xrange(9): # check col if index == irow: continue if board[index][icol] == value: return False # check section istart, jstart = (irow/3)*3, (icol/3)*3 for i in range(0, 3): for j in range(0, 3): if istart+i == irow and jstart+j == icol: continue if board[istart+i][jstart+j] == value: return False return True Post Views: 6