Python Simple DFS Solution


  • 0

    DFS only goes to positions whose value is ".".

    class Solution(object):
        def solveSudoku(self, board):
            def dfs(cells, sq, rows, cols, board):
                if not cells:
                    return True
                i, j = cells[-1]
                for num in range(0, 9):
                    if rows[i][num] == cols[j][num] == sq[3 * (i / 3) + j / 3][num] == 0:
                        rows[i][num] = cols[j][num] = sq[3 * (i / 3) + j / 3][num] = 1
                        board[i][j] = str(num + 1)
                        if dfs(cells[:-1], sq, rows, cols, board):
                            return True
                        board[i][j] = "."
                        rows[i][num] = cols[j][num] = sq[3 * (i / 3) + j / 3][num] = 0
                return False
            
            sq = [[0] * 9 for _ in range(9)]
            rows = [[0] * 9 for _ in range(9)]
            cols = [[0] * 9 for _ in range(9)]
            cells = []
            for i in range(len(board)):
                for j in range(len(board[0])):
                    if board[i][j] == ".":
                        cells.append((i, j))
                    else:
                        num = int(board[i][j]) - 1
                        rows[i][num] = cols[j][num] = sq[3 * (i / 3) + j / 3][num] = 1
            dfs(cells, sq, rows, cols, board)
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.