leetcode-回溯算法

发表于 | 分类于 ， | 页面访问量 次
字数统计: 3.2k 字 | 阅读时长 ≈ 16 分钟

回溯法（探索与回溯法）是一种选优搜索法，又称为试探法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。

解题关键：

  • 出口 通常规律把出口语句放在递归函数的第一行。

  • 递归函数的参数 这个参数是随着每一次的递归操作而发生改变的。而回溯法很关键的一点就是：如果当前操作行不通，如何回溯到上一步操作。

  • 递归函数的处理过程 如果当前递归过程的处理参数符合要求，则执行相关赋值或其它操作，然后转入下一次递归，如果下一次递归不能找到出口，则把之前相关赋值或其它操作重置为初始状态。

37. 解数独（A+）

分析：考虑两种编程概念，约束编程和回溯法。

没填一个空单元格判断3个条件。如果，不满足回溯到上一个。

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
45
46
47
48
49
50
51
52
53
class Solution:
    def solveSudoku(self, board: List[List[str]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """
        self.board = board
        self.solve()
    
    def findUnassigned(self):
        for row in range(9):
            for col in range(9):
                if self.board[row][col] == ".":
                    return row, col
        return -1, -1
    
    def solve(self):
        row, col = self.findUnassigned()
        #no unassigned position is found, puzzle solved
        if row == -1 and col == -1:
            return True
        for num in ["1","2","3","4","5","6","7","8","9"]:
            if self.isSafe(row, col, num):
                self.board[row][col] = num
                if self.solve():
                    return True
                self.board[row][col] = "."
        return False
            
    def isSafe(self, row, col, ch):
        boxrow = row - row%3
        boxcol = col - col%3
        if self.checkrow(row,ch) and self.checkcol(col,ch) and self.checksquare(boxrow, boxcol, ch):
            return True
        return False
    
    def checkrow(self, row, ch):
        for col in range(9):
            if self.board[row][col] == ch:
                return False
        return True
    
    def checkcol(self, col, ch):
        for row in range(9):
            if self.board[row][col] == ch:
                return False
        return True
       
    def checksquare(self, row, col, ch):
        for r in range(row, row+3):
            for c in range(col, col+3):
                if self.board[r][c] == ch:
                    return False
        return True
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
45
class Solution:
    def solveSudoku(self, board: List[List[str]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """
        # 把所有没填数字的位置找到
        all_points = []
        for i in range(9):
            for j in range(9):
                if board[i][j] == ".":
                    all_points.append([i, j])
        # check函数是为了检查是否在point位置k是合适的
        def check(point, k):
            row_i = point[0]
            col_j = point[1]
            for i in  range(9):
                # 检查 行
                if i != row_i and board[i][col_j] == k:
                    return False
                # 检查 列
                if i != col_j and board[row_i][i] == k:
                    return False
            # 检查块
            for i in range(row_i//3*3 , row_i//3*3+3):
                for j in range(col_j//3*3, col_j//3*3+3):
                    if i != row_i and j != col_j and board[i][j] == k:
                        return False

            return True

        def backtrack(i):
            # 回溯终止条件
            if i == len(all_points):
                return True
            for j in range(1, 10):
                # 检查是否合适
                if check(all_points[i],str(j)):
                    # 合适就把位置改过来
                    board[all_points[i][0]][all_points[i][1]] = str(j)
                    if backtrack(i+1): # 回溯下一个点
                        return True
                    board[all_points[i][0]][all_points[i][1]] = "."# 不成功把原来改回来
            return False

        backtrack(0)

python2版本，最快代码。应该是用了哈希

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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
class Solution(object):
    def solveSudoku(self, board):
        """
        :type board: List[List[str]]
        :rtype: None Do not return anything, modify board in-place instead.
        """
        
        self.board = board
        self.val = self.PossibleVals()
        self.Solver()

    def PossibleVals(self):
        a = "123456789"
        d, val = {}, {}
        for i in xrange(9):
            for j in xrange(9):
                ele = self.board[i][j]
                if ele != ".":
                    d[("r", i)] = d.get(("r", i), []) + [ele]
                    d[("c", j)] = d.get(("c", j), []) + [ele]
                    d[(i//3, j//3)] = d.get((i//3, j//3), []) + [ele]
                else:
                    val[(i,j)] = []
        for (i,j) in val.keys():
            inval = d.get(("r",i),[])+d.get(("c",j),[])+d.get((i/3,j/3),[])
            val[(i,j)] = [n for n in a if n not in inval ]
        return val

    def Solver(self):
        if len(self.val)==0:
            return True
        kee = min(self.val.keys(), key=lambda x: len(self.val[x]))
        nums = self.val[kee]
        for n in nums:
            update = {kee:self.val[kee]}
            if self.ValidOne(n, kee, update): # valid choice
                if self.Solver(): # keep solving
                    return True
            self.undo(kee, update) # invalid choice or didn't solve it => undo
        return False

    def ValidOne(self, n, kee, update):
        self.board[kee[0]][kee[1]] = n
        del self.val[kee]
        i, j = kee
        for ind in self.val.keys():
            if n in self.val[ind]:
                if ind[0]==i or ind[1]==j or (ind[0]/3,ind[1]/3)==(i/3,j/3):
                    update[ind] = n
                    self.val[ind].remove(n)
                    if len(self.val[ind])==0:
                        return False
        return True

    def undo(self, kee, update):
        self.board[kee[0]][kee[1]]="."
        for k in update:            
            if k not in self.val:
                self.val[k]= update[k]
            else:
                self.val[k].append(update[k])
        return None

46. 全排列（C）

分析：整体就是简单的递归思想。

1
2
3
4
5
6
7
8
class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        if len(nums) <= 1: return [nums]
        res = []
        for i, num in enumerate(nums):
            for r in self.permute(nums[:i] + nums[i + 1:]):
                res.append([num] + r)
        return res

47. 全排列 II（C-）

分析：根据上题稍微变动一下，加一个条件去重即可

1
2
3
4
5
6
7
8
9
10
class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        if len(nums) <= 1: return [nums]
       
        res = []
        for i, num in enumerate(nums):
            for r in self.permuteUnique(nums[:i] + nums[i + 1:]):
                if [num]+r not in res:
                    res.append([num] + r)
        return res

回溯法常规写法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def dfs(self, nums, path, res):
        if not nums:
            res.append(path)
        for i in range(len(nums)):
            if i > 0 and nums[i] == nums[i-1]:
                continue
            self.dfs(nums[:i] + nums[i+1:], path + [nums[i]], res)
    
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        res = []
        self.dfs(nums, [], res)
        return res

51. N皇后（A）

分析：回溯法经典问题。思路需要梳理清楚。主要学习了两种方式。一种递归方式，另一种非递归方式。最优的方法应该是位排序。利用二进制的特性进行排序。在后一题有详解。

回溯算法也叫试探法，它是一种系统地搜索问题的解的方法。回溯算法的基本思想是：从一条路往前走，能进则进，不能进则退回来，换一条路再试。

在现实中，有很多问题往往需要我们把其所有可能穷举出来，然后从中找出满足某种要求的可能或最优的情况，从而得到整个问题的解。回溯算法就是解决这种问题的“通用算法”，有“万能算法”之称。N皇后问题在N增大时就是这样一个解空间很大的问题，所以比较适合用这种方法求解。这也是N皇后问题的传统解法，很经典。

把棋盘存储为一个N维数组a[N]，数组中第i个元素的值代表第i行的皇后位置，这样便可以把问题的空间规模压缩为一维O(N)，在判断是否冲突时也很简单，首先每行只有一个皇后，且在数组中只占据一个元素的位置，行冲突就不存在了，其次是列冲突，判断一下是否有a[i]与当前要放置皇后的列j相等即可。至于斜线冲突，通过观察可以发现所有在斜线上冲突的皇后的位置都有规律即它们所在的行列互减的绝对值相等，即| row – i | = | col – a[i] |

第一种递归方式。python

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
class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        res = list()
        board = [["." for col in range(n)] for row in range(n)]
        self._dfs(0, n, board, res)
        return res

    def _can_place(self, n, board, row, col):
        for r in range(row):
            if board[r][col] == 'Q':
                return False
            if col + row - r < n and board[r][col + row - r] == 'Q':
                return False
            
            if col - row + r >= 0 and board[r][col - row + r] == 'Q':
                return False
        return True

    def _dfs(self, row, n, board, res):
        if row == n:
            res.append(list(map(lambda r: "".join(r), board)))
            return

        for col in range(n):
            if not self._can_place(n, board, row, col):
                continue
            board[row][col] = 'Q'
            self._dfs(row + 1, n, board, res)
            board[row][col] = '.'

cpp

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
class Solution {
public:
    vector<vector<string>> solveNQueens(int n) {
        vector<vector<string>> res;
        vector<string> board(n, string(n, '.'));
        dfs(0, n, board, res);
        return res;
    }
private:
    void dfs(int row, int n, vector<string>& board, vector<vector<string>>& res){
        if (row == n){
            res.push_back(board);
            return;
            
        }
        for (int col = 0; col < n; ++col){
            if (can_place(board, n, row, col)) {
                board[row][col] = 'Q';
                dfs(row + 1, n, board, res);
                board[row][col] = '.';
            }            
        }
    }
    bool can_place(vector<string>& board, int n, int row, int col){
        for (int r = 0; r < row; ++r){
            if (board[r][col] == 'Q') return false;
            if (col + row - r < n && board[r][col + row - r] == 'Q') return false;
            if (col - row + r >= 0 && board[r][col - row + r] == 'Q') return false;
                           
        }
        return true;
    }
};

python另一种写法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
from itertools import permutations

class Solution:
    
    def __init__(self):
        self.res = []
        self.n = 0
        
    def solveNQueens(self, n: int) -> List[List[str]]:
        self.n = n
        for vec in permutations(range(n)):
            #这步比较关键,排除各种可能的对角线,好好思考一下就懂了
            if (n == len(set(vec[i] + i for i in range(n))) == len(set(vec[i]-i for i in range(n)))):
                self.generate_q(vec)
        return self.res
    
    #拼接需要的输出结果,添加进self.res
    def generate_q(self,vec):
        s = '.'*self.n
        a = []
        for i in vec:
            q = i*"."+'Q'+(self.n-i-1)*'.'
            a.append(q)
        self.res.append(a)

python一种优化方式。记录冲突的位置。。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        res = []
        def dfs(queens, ddiff, ssum):
            p = len(queens)
            if p == n:
                queens = ['.' * i + 'Q' + '.' * (n - 1 - i) for i in queens]
                res.append(queens)
                return
            for q in range(n):
                if q in queens or p - q in ddiff or p + q in ssum: continue
                dfs(queens + [q], ddiff + [p - q], ssum + [p + q])
        dfs([], [], [])
        return res

第二种非递归法

cpp

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
class Solution {
public:
    vector<vector<string>> solveNQueens(int n) {
        vector<vector<string>> res;
        vector<int> pos(n, -1);
        
        int row = 0;
        while (row >= 0) {
            while(++pos[row] < n && !can_place(pos, row));
            
            if (pos[row] < n) {
                if (row == n - 1) {
                    add_solution(res, pos);
                    --row;                    
                } else {
                    pos[++row] = -1;                    
                }
            } else{
                --row;
            }
        }
        return res;
    }
    
private:
    bool can_place(vector<int>& pos, int row) {
        for (int r = 0; r < row; ++r) {
            if (pos[r] == pos[row] || abs(pos[r] - pos[row]) == row - r) {
                return false;
            }
        }
        return true;                                                     
    }

void add_solution(vector<vector<string>>& res, vector<int>& pos) {
    vector<string> board(pos.size(), string(pos.size(), '.'));
    for (int row = 0; row < pos.size(); ++row) {
        board[row][pos[row]] = 'Q';        
    }
    res.push_back(board);
}
};

一行邪教

1
2
3
4
5
class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        return [['.' * v + 'Q' + '.' * (n - v - 1) for v in c] for c in itertools.permutations(range(n))
                if (len(set(i + v for i, v in enumerate(c))) == n) and
                (len(set(i - v for i, v in enumerate(c))) == n)]

52. N皇后 II（A）

分析:有了上一题的基础，做起来还是挺简单的。符合条件的放入列表。

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
class Solution:
    def totalNQueens(self, n):
        board, ret = [['.'] * n for _ in range(n)], []
        self.dfs(board, n, 0, ret)
        return len(ret)
    
    def dfs(self, board, n, row, ret):
        if row == n:
            ret.append(["".join(i) for i in board])
            return
        for i in range(n):
            if not self.canPlace(row, i, n, board):
                continue
            board[row][i] = 'Q'
            self.dfs(board, n, row + 1, ret)
            board[row][i] = '.'
    
    def canPlace(self, row, col, n, board):
        for i in range(1, row + 1):
            if board[row - i][col] == 'Q':
                return False
            if col - i >= 0 and board[row - i][col - i] == 'Q':
                return False
            if col + i < n and board[row - i][col + i] == 'Q':
                return False
        return True

方法二：记录不能放置的位置。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# @author:leacoder 
# @des:  DFS 深度优先  N皇后II

class Solution:
    def totalNQueens(self, n: int) -> int:
        if n < 1 : return []  #
        self.count = 0
        shu = [] # 竖方向是否被攻击
        pie = [] # 撇方向是否被攻击  x y 坐标之和固定 x + y
        na = []  # 捺方向是否被攻击  x y 坐标之差固定 x - y
        
        self.DFS(n,shu,pie,na)
        
        return self.count
    
    def DFS(self,n,shu,pie,na): #深度优先搜索 
        p = len(shu) #  从 1 -> n
        if p == n :
            self.count += 1 #每层有且只能放一个
            return 
        for q in range(n): # 看成 x  每层枚举可能的 x
            if q not in shu and p - q not in na and p + q not in pie: #这一层存在可能位置，向下层搜索
                self.DFS(n,shu+[q],pie+[p+q],na+[p-q])  #深度优先搜索  将被攻击的 坐标记录下来

方法三：位运算的表示，应该是最优方法之一。

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
# @author:leacoder 
# @des:  位运算 + DFS 深度优先  N皇后
class Solution:
    def totalNQueens(self, n: int) -> int:
        if n < 1: return []
        self.count = 0
        self.DFS(n,0,0,0,0) #从第一行开始   由于棋盘第一行没有放任何皇后那么 row 行 cols 列 pie 撇 na 捺 位没有不可放置的
        return self.count
    
    def DFS(self, n, row, cols, pie, na):
        if row >= n: #递归终止条件  深度搜索 n 个皇后均已放在棋盘上
            self.count += 1
            return
        
        
        # col | pie | na  (1 表示被攻击, 或了以后 等到本行 所有被攻击位置 )
        # ~( col | pie | na )  0 表示被攻击位  1 表示可放置位
        # (( 1<<n ) - 1)   形成 n位全1的二进制 筛子  用于 筛选出 n 位内的有效数据
        bits = ( ~( cols | pie | na )) & (( 1<<n ) - 1)
        
        while bits:
            p = bits & (-bits)  # 取出最低位的1 也就是最低位可以放置 皇后Q的位置
            # row + 1 下移一层   cols | p : p 上放置 Q 后  cols 列方向被攻击位刷新
            # (pie | p) << 1 下一层 pie撇方向被攻击位置刷新
            # (na | p) >> 1 下一层 na 捺方向被攻击位置刷新
            self.DFS(n , row + 1, cols | p, (pie | p) << 1, (na | p) >> 1)  # 递归处理下一层
            bits = bits & (bits - 1) #去掉最低位的 1 （表示这种可能已被探寻）

参看 LeetCode 52. N皇后 II(N-Queens II)

0%
undefined