N皇后问题如何写出简洁的最优解 - 回溯法及LeetCode应用详解

Steve Wang

发布于 2021-01-14 15:05:07

5030

发布于 2021-01-14 15:05:07

backtracking(回溯)，是LeetCode上比较常见的一类典型题。本博文所有的代码均可在 https://github.com/Hongze-Wang/LeetCode_Java https://github.com/Hongze-Wang/LeetCode_Python 中找到，欢迎star。

回溯法之所以称之为回溯法，是因为它其实是DFS/BFS+回溯操作进行的穷举。回溯和DFS/BFS的区别在于回溯操作。也有人把回溯法称为BFS/DFS，这没有错，但是不太准确的，回溯法是特殊的DFS或者BFS，因为DFS或者BFS在某些情况下无法递归处理所有的情况(即不完全穷举)，需要执行一定的后悔操作，才能穷举所有情况。

我们以LeetCode实例进行说明：

首先我们从DFS扩展到backtracking：

112. Path Sum (Easy)

Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.

Note: A leaf is a node with no children.

Example: Given the below binary tree and sum = 22,

      5
     / \
    4   8
   /   / \
  11  13  4
 /  \      \
7    2      1

return true, as there exist a root-to-leaf path 5->4->11->2which sum is 22.

因为是树形结构，很容易联想到使用DFS递归来解：

// 112. Path Sum
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class PathSum {
    public boolean hasPathSum(TreeNode root, int sum) {
        if(root == null) return false;
        // Path value condition need that the last node must be a leaf node
        if((sum -= root.val) == 0 && root.left == null && root.right == null) {
            return true;
        }
        return hasPathSum(root.left, sum) || hasPathSum(root.right, sum);
    }
}

113. Path Sum II (Medium)

Given a binary tree and a sum, find all root-to-leaf paths where each path’s sum equals the given sum.

Note: A leaf is a node with no children.

Example: Given the below binary tree and sum = 22,

      5
     / \
    4   8
   /   / \
  11  13  4
 /  \    / \
7    2  5   1

Return:

[
   [5,4,11,2],
   [5,8,4,5]
]

这道题是上面简单题的扩展版，从求有没有解到把所有的解都求出来，这个时候就需要回溯法了。因为DFS找到解之后就直接返回了，它无法穷举所有的情况。

// 113. Path Sum II

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */

public class Solution {
    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        List<List<Integer>> res = new ArrayList<>();
        dfs(root, sum, res, new ArrayList());
        return res;
    }

    public void dfs(TreeNode root, int sum, List<List<Integer>> res, List<Integer> list) {
        if(root == null) return; // 递归终止条件
        
        sum -= root.val;    // 需要回溯的操作1
        list.add(root.val); // 需要回溯的操作2
        
        if(root.left == null && root.right == null) {
            if(sum == 0) {
                res.add(new ArrayList(list));
            }
            list.remove(list.size()-1); // 回溯 取消操作2 把操作2加进去的元素删掉
            // sum += root.val;         // 回溯 取消操作1 不再向下递归 这一句做不做都一样
            return;
        }
        dfs(root.left, sum, res, list);
        dfs(root.right, sum, res, list);
        list.remove(list.size()-1);    // 回溯 取消操作2 把操作2加进去的元素删掉
        // sum += root.val;            // 回溯 取消操作1 因为不再向下递归 这一句做不做都一样
    }
}

回溯法比较难搞懂的是它的执行路径，因为它建立在递归之上，而且还有后悔操作。以这个例子为例，list.remove(list.size()-1)移除的到底是哪一个元素呢？没错，是本次递归所加进去的元素。递归调用会保存堆栈，两行dfs返回之后list的状态是没有执行两行dfs的状态，而不是执行了两行dfs之后的状态，这点是反直觉的。你可以把代码辅助到Idea中，打个断点，然后一步一步观察相关变量是如何变化的，以加深自己的理解。

下面我们在看看和的组合以及序列这两个LeetCode的回溯典型题：

39. Combination Sum (Medium)

Given an array of distinct integers candidates and a target integer target, return a list of all unique combinations of candidates where the chosen numbers sum to target. You may return the combinations in any order.

The same number may be chosen from candidates an unlimited number of times. Two combinations are unique if the frequency of at least one of the chosen numbers is different.

It is guaranteed that the number of unique combinations that sum up to target is less than 150 combinations for the given input.

Example 1: Input: candidates = [2,3,6,7], target = 7 Output: [[2,2,3],[7]] Explanation: 2 and 3 are candidates, and 2 + 2 + 3 = 7. Note that 2 can be used multiple times. 7 is a candidate, and 7 = 7. These are the only two combinations.

Example 2: Input: candidates = [2,3,5], target = 8 Output: [[2,2,2,2],[2,3,3],[3,5]]

Example 3: Input: candidates = [2], target = 1 Output: []

Example 4: Input: candidates = [1], target = 1 Output: [[1]]

Example 5: Input: candidates = [1], target = 2 Output: [[1,1]]

Constraints: 1 <= candidates.length <= 30 1 <= candidates[i] <= 200 All elements of candidates are distinct. 1 <= target <= 500

class Solution {
    public void backtrack(int[] candidates, int index,int target, List<Integer> list, List<List<Integer>> res) {
        if(target == 0) { // 递归终止条件
            res.add(new ArrayList(list));
            return;
        }
        
        for(int i=index; i<candidates.length; i++) { // 因为这道题 数组元素是可以重复利用的所以i从index开始 递归调用也会传入index 这点请注意
            if(target - candidates[i] < 0) {
                break;
            }
            target -= candidates[i]; // 需要回溯的操作1
            list.add(candidates[i]); // 需要回溯的操作2
            backtrack(candidates, i, target, list, res);
            target += candidates[i]; // 回溯操作1
            list.remove(list.size()-1); // 回溯操作2
        }
        
        
    }
    
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> res = new ArrayList<>();
        Arrays.sort(candidates); // 需要对数组排序
        backtrack(candidates, 0, target, new ArrayList(), res);
        return res;
    }
}

这道题我们可以看出，解回溯题是，需要回溯的操作位于递归调用之前，递归调用之后应该立即取消这些操作。

40. Combination Sum II (Medium)

Given a collection of candidate numbers (candidates) and a target number (target), find all unique combinations in candidates where the candidate numbers sum to target.

Each number in candidates may only be used once in the combination. (注意这点，这是和第39题的区别)

Note: The solution set must not contain duplicate combinations. (注意这点，这是和第39题的区别)

Example 1: Input: candidates = [10,1,2,7,6,1,5], target = 8 Output:

[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]

Example 2: Input: candidates = [2,5,2,1,2], target = 5 Output:

[
[1,2,2],
[5]
]

Constraints:

1 <= candidates.length <= 100 1 <= candidates[i] <= 50 1 <= target <= 30

class Solution {
    public void backtrack(int[] candidates, int index,int target, List<Integer> list, List<List<Integer>> res) {
        if(target == 0) { // 递归终止条件1
            res.add(new ArrayList(list));
            return;
        }
        
        for(int i=index; i<candidates.length; i++) {
            if(target - candidates[i] < 0) { // 递归终止条件2
                break;
            }
            if(i > index && candidates[i] == candidates[i-1]) { // 防止回溯时再次把之前记忆过的答案再加进去
                continue;
            }
            target -= candidates[i];  // 需要回溯的操作1
            list.add(candidates[i]);  // 需要回溯的操作2
            backtrack(candidates, i+1, target, list, res);  // 注意 和39不同，这里因为每个元素只能用一次 所以传的参数是i+1
            target += candidates[i];    // 回溯操作1
            list.remove(list.size()-1); // 回溯操作2
        }
        
        
    }
    
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        List<List<Integer>> res = new ArrayList<>();
        Arrays.sort(candidates); // 注意需要对数组排序
        backtrack(candidates, 0, target, new ArrayList(), res);
        return res;
    }
}

46. Permutations (Medium)

Given an array nums of distinct integers, return all the possible permutations. You can return the answer in any order.

Example 1: Input: nums = [1,2,3] Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

Example 2: Input: nums = [0,1] Output: [[0,1],[1,0]]

Example 3: Input: nums = [1] Output: [[1]]

Constraints:

1 <= nums.length <= 6 -10 <= nums[i] <= 10 All the integers of nums are unique.

// 46. Permutations
// c++ offer next_permutation to generate next permutationI

class Solution {
    List<Integer> temp;
    
    public List<List<Integer>> arr = new ArrayList();

    public List<List<Integer>> permute(int[] nums) {
        permute(nums, 0, nums.length-1);
        return arr;
    }

    private void permute(int nums[], int left, int right) {
        if(left == right) {
            temp = new ArrayList<Integer>();
            for(int k: nums) {
                temp.add(k);
            }
            arr.add(temp);
        } else {
            for(int i=left; i<=right; i++) {
                swap(nums, i, left); // 需要回溯的操作
                permute(nums, left+1, right);
                swap(nums, i, left);  // 回溯操作
            }
        }
    }

    private void swap(int[] nums, int i, int left) {
        int temp = nums[i];
        nums[i] = nums[left];
        nums[left] = temp;
    }

这道题体现了回溯法的穷举特性，以Example1为例，加到结果集arr顺序是[1,2,3] ->[1,3,2]->[2,1,3]->[2,3,1]->[3,2,1]->[3,1,2]。思考一下递归执行的整个过程是怎样的？

47. Permutations II (Medium)

Given a collection of numbers, nums, that might contain duplicates, return all possible unique permutations in any order.

Example 1: Input: nums = [1,1,2] Output: [[1,1,2], [1,2,1], [2,1,1]]

Example 2: Input: nums = [1,2,3] Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

Constraints: 1 <= nums.length <= 8 -10 <= nums[i] <= 10

// 47. Permutations II

class Solution {
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        vector<vector<int>> res = {nums};
        // if(nums.size() == 0) return res;
        while(next_permutation(nums.begin(),nums.end())) {
            res.push_back(nums);
        }
        return res;
    }
};

开个玩笑！不过这道题我只写了Python版本的。使用Python内置的计数器对数组元素计数，然后用一个就减掉一个，减到0直接删除，计数器为空的时候即为所有的元素都使用完毕，加入到结果集中。Python的回溯法可以写一个内置函数，是一种闭包的形式，可以减少很多参数的传递，改变变量作用域是闭包的重要作用之一。

# 47. Permutations II

class Solution:
    def permuteUnique(self, nums: List[int]) -> List[int]:
        counter = collections.Counter(nums)

        def dfs(cur):
            res = []
            if not counter: # 递归终止条件
                return [cur]
            for num in list(counter.keys()):
                counter[num] -= 1 # 需要回溯的操作
                if counter[num] == 0:
                    del counter[num]
                res += dfs(cur + [num]) # 等价于 res.append(dfs(cur + [num]))
                counter[num] = counter.get(num, 0) + 1 # 回溯操作
            return res
        
        return dfs([])

最后，就是我们的主人公了，经典的N皇后问题。

51. N-Queens (Hard)

The n-queens puzzle is the problem of placing n queens on an n x n chessboard such that no two queens attack each other.

Given an integer n, return all distinct solutions to the n-queens puzzle.

Each solution contains a distinct board configuration of the n-queens’ placement, where ‘Q’ and ‘.’ both indicate a queen and an empty space, respectively.

Example 1:

Input: n = 4 Output: [[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]] Explanation: There exist two distinct solutions to the 4-queens puzzle as shown above Example 2:

Input: n = 1 Output: [["Q"]]

Constraints: 1 <= n <= 9

如果你不太看得懂对角线规律是这么来的话，参见这里。

// 51. N-Queens

// 回溯法模板题 + 找规律
// 回溯法适用于枚举问题，比如全排列、组合之类的
// 这些问题往往需要在枚举的所有情况中选择满足条件的情况生成解或者是求最优解 因此需要注意if判断条件删除一些不需要考虑的情况
// 回溯法和DFS、BFS的区别在于为了枚举 有回溯过程 即为了生成所有情况而还原某些操作 比如下面的操作1和操作2 都是需要回溯的操作
// 千万不能忘掉回溯 否则无法生成所有解 或者漏掉最优解的过程

// i表示第i行 j表示第j列
// 规律 对角线坐标
// 斜对角线坐标 行列坐标差值永远相等 为了避免出现负值 使用i-j+n 为此 diag1的容量应为2n
// 反斜对角线左边 行列坐标的和永远相等 为了避免出现溢出 diag1的容量为2n

class Solution {
    
    public List<List<String>> res = new ArrayList<>();
    
    public List<List<String>> solveNQueens(int n) {
        char[][] board = new char[n][n];
        boolean[] col = new boolean[n];
        boolean[] diag1 = new boolean[n+n];
        boolean[] diag2 = new boolean[n+n];
        // 初始化棋盘
        for(int i=0; i<n; i++) {
            for(int j=0; j<n; j++) {
                board[i][j] = '.';
            }
        }
        
        solveNQueens(0, n, board, col, diag1, diag2);
        
        return res;
    }
    
    
    public void solveNQueens(int i, int n, char[][] board, boolean[] col, boolean[] diag1, boolean[] diag2) {
        if(i == n) { // 递归终止条件
            List<String> list = new ArrayList<>();
            for(int r=0; r<n; r++) {
                list.add(new String(board[r])); // 因为是传引用 所以要new出新的String加入list
            }
            res.add(list);
            return;
        }
        
        for(int j=0; j<n; j++) {
            if(!col[j] && !diag1[n-i+j] && !diag2[i+j]) {
                board[i][j] = 'Q'; // 需要回溯的操作1
                col[j] = diag1[n-i+j] = diag2[i+j] = true; // 需要回溯的操作2
                solveNQueens(i+1, n, board, col, diag1, diag2);
                col[j] = diag1[n-i+j] = diag2[i+j] = false; // 回溯操作2
                board[i][j] = '.'; // 回溯操作1
            }
        }
    }
}

52. N-Queens II (Hard)

The n-queens puzzle is the problem of placing n queens on an n x n chessboard such that no two queens attack each other.

Given an integer n, return the number of distinct solutions to the n-queens puzzle.

Example 1:

Input: n = 4 Output: 2 Explanation: There are two distinct solutions to the 4-queens puzzle as shown.

Example 2: Input: n = 1 Output: 1

Constraints:

1 <= n <= 9

回溯解法一(非最优解)

解法同51，只不过到达递归终止条件时，我们就计数。这不是最优解，仅仅求出解的数量可以通过取巧来节省穷举整个求解过程的某些计算过程，见下面的解法。

class Solution {
    
    public int res = 0;
    
    public void solveNQueens(int n) {
        char[][] board = new char[n][n];
        boolean[] col = new boolean[n];
        boolean[] diag1 = new boolean[n+n];
        boolean[] diag2 = new boolean[n+n];
        
        for(int i=0; i<n; i++) {
            for(int j=0; j<n; j++) {
                board[i][j] = '.';
            }
        }
        
        solveNQueens(0, n, board, col, diag1, diag2);
        
    }
    
    
    public void solveNQueens(int i, int n, char[][] board, boolean[] col, boolean[] diag1, boolean[] diag2) {
        if(i == n) {
            res++;
        }
        
        for(int j=0; j<n; j++) {
            if(!col[j] && !diag1[n-i+j] && !diag2[i+j]) {
                board[i][j] = 'Q';
                col[j] = diag1[n-i+j] = diag2[i+j] = true;
                solveNQueens(i+1, n, board, col, diag1, diag2);
                col[j] = diag1[n-i+j] = diag2[i+j] = false;
                board[i][j] = '.';
            }
        }
    }
    
    public int totalNQueens(int n) {
        solveNQueens(n);
        return res;
    }
}

回溯解法二(最优解)：

使用整型的二进制表示做标志位
用n个十进制数 即可表示棋盘 0表示可以放Q 1表示不能放Q

一旦某一行被放置了Q 则该位置变为1 整行整列都不能放Q了 因而整行整列都变成1 对应for循环操作a
反对角线 不能放Q 对应循环操作b
对角线   不能放Q 对应循环操作c

// 使用整型的二进制表示做标志位
// 用n个十进制数 即可表示棋盘 0 表示可以放Q 1表示不能放Q

// 一旦某一行被放置了Q 则该位置变为1 整行整列都不能放Q了 因而整行整列都变成1 对应for循环操作a
// 反对角线 不能放Q 对应循环操作b
// 对角线   不能放Q 对应循环操作c

// 以n = 3为例
// 000b = 0
// 000b = 0
// 000b = 0
 
// 我们在第一行第一列放置Q Q存的是1 我这里为了区别因为本列本行或者对角线放了Q而不能放的位置 写成了Q
// Q00b = 4
// 000  = 0
// 000  = 0

// for循环a操作 使得
// Q11  = 7
// 100  = 4
// 100  = 4

// for循环b操作 使得
// Q11  = 7
// 110  = 6
// 100  = 4

// for循环c操作 使得
// Q11  = 7
// 110  = 6
// 101  = 5

// 最终得到
// Q11  = 7
// 11Q  = 7
// 1Q1  = 7
// 只有这一种解

class Solution {
    
    public int total = 0;

    public int totalNQueens(int[] queens, int len) {
        int total = 0;
        for(int i=0; i<queens.length; i++) {
            if((queens[len-1] & (1 << i)) == 0) {
                if(len == queens.length) {
                    total += 1;
                } else {
                    int[] rem = new int[queens.length-len];
                    for(int j=len; j<queens.length; j++) {
                        rem[j-len] = queens[j];            // 储存操作前状态 为了回溯
                        queens[j] |= 1 << i;               // 操作a
                        queens[j] |= 1 << (i+j - len + 1); // 操作b 对角线规律 行列坐标和相等 -len+1 防止溢出n
                        queens[j] |= 1 << (i-j + len - 1); // 操作c 对角线规律 行列坐标差相等 +len-1 防止小于0
                    }
                    total += totalNQueens(queens, len+1);
                    for(int j=len; j<queens.length; j++) {
                        queens[j] = rem[j-len];            // 回溯操作 同时撤销了操作a、b、c
                    }
                }
            }
        }
        return total;
    }

    public int totalNQueens(int n) {
        int[] queens = new int[n];
        return totalNQueens(queens, 1);
    }
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2021/01/11 ，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

编程算法

登录后参与评论

0 条评论

热度