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.

解题方法

这一题大概思路就是跟permutaion, subset差不多的backtracking的方法

• 对每一个.的地方，尝试着填入1-9其中的某个数，然后再把这个暂时的结果传入下一个recursive call来计算，
• 判断是否有正确的解，如果没有就去掉填入的信息，继续用下一个数试
• 在check是否可以填入时可以用valid sodoku的方法优化，记录下现在行，列，和小九宫格里已经用过的数，遇到就可以直接跳过

172ms

Solution

class Solution(object):
    def solveSudoku(self, board):
        """
        :type board: List[List[str]]
        :rtype: void Do not return anything, modify board in-place instead.
        """
        if not board:
            return False
        rowValid = [[False for i in range(9)] for j in range(9)]
        colValid = [[False for i in range(9)] for j in range(9)]
        subValid = [[False for i in range(9)] for j in range(9)]
        # 先保存下已经存在的数字
        for i in range(9):
            for j in range(9):
                if board[i][j] != ".":
                    subNum = (i/3)*3 + j / 3
                    rowValid[i][int(board[i][j])-1] = True
                    colValid[j][int(board[i][j])-1] = True
                    subValid[subNum][int(board[i][j])-1] = True

        self.helper(board, rowValid, colValid, subValid, 0, 0)

    def helper(self, board, rowValid, colValid, subValid, row, col):
        i = row
        j = col
        while i < 9:
            if j > 8:
                #已经到了行尾，该进入下一行了
                j = 0
                i += 1
            else:
                subNum = (i/3) * 3 + j / 3
                if board[i][j] == ".":
                    for k in range(9):
                        if not rowValid[i][k] and not colValid[j][k] and not subValid[subNum][k]:
                            board[i][j] = str(k+1)
                            rowValid[i][k] = True
                            colValid[j][k] = True
                            subValid[subNum][k] = True
                            if j < 8:
                                if self.helper(board, rowValid, colValid, subValid, i, j+1):
                                    return True
                            else:
                                if self.helper(board, rowValid, colValid, subValid, i+1, 0):
                                    return True
                            board[i][j] = "."
                            rowValid[i][k] = False
                            colValid[j][k] = False
                            subValid[subNum][k] = False
                    return False
                else:
                    j += 1

        return True

Reference

• solve sodoku