Sudoku Solver

题目描述

解题方法

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
        row = [[False for i in range(9)] for j in range(9)]
        col = [[False for i in range(9)] for j in range(9)]
        sub = [[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] != '.':
                    cur_val = int(board[i][j]) - 1
                    sub_num = (i / 3) * 3 + j / 3
                    row[i][cur_val] = True
                    col[j][cur_val] = True
                    sub[sub_num][cur_val] = True

        self.solve(board, row, col, sub)

    def solve(self, board, row, col, sub):
        for i in range(9):
            for j in range(9):
                if board[i][j] == ".":
                    sub_num = (i / 3) * 3 + j / 3
                    for k in range(1, 10):
                        cur_val = k - 1
                        # check if it's valid
                        if row[i][cur_val] or col[j][cur_val] or sub[sub_num][cur_val]:
                            continue
                        board[i][j] = str(k)
                        row[i][cur_val] = True
                        col[j][cur_val] = True
                        sub[sub_num][cur_val] = True
                        if self.solve(board, row, col, sub):
                            return True
                        board[i][j] = "."
                        row[i][cur_val] = False
                        col[j][cur_val] = False
                        sub[sub_num][cur_val] = False
                    return False
                else:
                    continue
        return True

Reference