LeetCode 解题报告 (37)-- 回溯法解决数独问题

发表于 标签 ，

原题如下： >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.

A sudoku puzzle...

题目要求解决一个给定的数独，且每个数独的答案唯一。

解题思路如下：采用回溯法，每插入一个数之前检查插入这个数之后是否有效。假如有效就插入并且保留当前插入了这个数的状态。以保证后面插入的数无效的时候能够回溯到当前这个状态，修改当前状态插入的数。实现这种状态的保存与回溯可以通过递归实现。

实现代码如下：

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
class Solution(object):
    def solveSudoku(self, board):
        """
        :type board: List[List[str]]
        :rtype: void Do not return anything, modify board in-place instead.
        """
        self.helper(board)

    def helper(self, board):
        num = len(board)
        for i in range(num):
            for j in range(num):
                if board[i][j] == '.':
                    for t in range(1,10):
                        c = str(t)
                        if self.is_valid(board, c, i, j):
                            board[i][j] = c
                            if self.helper(board):
                                return True
                            else:
                                board[i][j] = '.' 
                    return False  # 当前插入1~9均无效，回溯到前一状态
        return True  # 插入最后一个数成功时需要返回True,从而将前面的状态确定下来

    def is_valid(self, board, c, row , col):
        num = len(board)
        # check row 
        for m in range(num):
            if board[row][m] == c:
                return False

        # check column 
        for n in range(num):
            if board[n][col] == c:
                return False

        # check block 
        row_start = (row/3)*3
        column_start = (col/3)*3
        for i in range(row_start,row_start+3):
            for j in range(column_start,column_start+3):
                if board[i][j] == c:
                    return False
        return True