LeetCode-N皇后(每日一题)

题目描述

n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。

示例：

输入：4
输出：[
 [".Q..",  // 解法 1
  "...Q",
  "Q...",
  "..Q."],

 ["..Q.",  // 解法 2
  "Q...",
  "...Q",
  ".Q.."]
]
解释: 4 皇后问题存在两个不同的解法。

解法

1. 回溯法

思路：回溯算法是一种遍历算法，以深度优先搜索的方式尝试所有可能性。回溯算法是有方向性地搜索，区别于多层循环实现的暴力法。

回溯算法的思想是：不断尝试，直到不能尝试为止，回退到上一步，继续尝试。

例如：4皇后的递归树如下

这里搜索的过程中包含了剪枝的思想，依据是N皇后的摆放规则：

不在同一行
不在同一列
不在同一主对角线
不在同一副对角线

我们可以使用数组来记住对应的占用。我们一行一行的摆放皇后的位置，所以可以使用三个数组分别保存列占用，主对角线占用以及副对角线占用。

主对角线

主对角线上的列数和行数之差为一常数。为了将负值放在数组中，需要将对应的数字都向右平移(n - 1)，这里n=3

副对角线

副对角线上的列数与行数之和为一常数。

import java.util.List;
import java.util.ArrayList;
import java.util.Stack;

class Solution {
    // 设置为成员变量，减少参数传递
    // 设置数组保存皇后的占位
    private boolean[] column;
    private boolean[] dialog1;
    private boolean[] dialog2;
    // 结果
    private List<List<String>> ans;

    public List<List<String>> solveNQueens(int n) {
        ans = new ArrayList<>();
        if (n <= 0) return ans;
        column = new boolean[n];
        dialog1 = new boolean[2 * n - 1];
        dialog2 = new boolean[2 * n - 1];
        // path存放一个满足条件的结果
        Stack<Integer> path = new Stack<>();
        // 深度优先搜索
        dfs(path, 0, n);
        return ans;
    }

    private void dfs(Stack<Integer> path, int row, int n) {
        // 如果row == n，说明前n-1行都填完了，此时path中的是一个满足条件的结果
        // 保存结果
        if (row == n) {
            List<String> result = convert2Res(path, n);
            ans.add(result);
        }
        // 否则在当前行中一个位置一个位置摆放
        for (int col = 0; col < n; col++) {
            // 如果对应要求的位置没有被占用，放入皇后
            if (!column[col] && !dialog1[col - row + n - 1] && !dialog2[col + row]) {
                path.push(col);
                column[col] = true;
                dialog1[col - row + n - 1] = true;
                dialog2[col + row] = true;

                // 去下一行摆放
                dfs(path, row + 1, n);

                // 摆放失败需要将当前步退后
                path.pop();
                column[col] = false;
                dialog1[col - row + n - 1] = false;
                dialog2[col + row] = false;
            }
        }
    }

    private List<String> convert2Res(Stack<Integer> path, int n) {
        List<String> board = new ArrayList<>();
        for (Integer num: path) {
            StringBuilder sb = new StringBuilder();
            sb.append(".".repeat(n));
            sb.replace(num, num + 1, "Q");
            board.add(sb.toString());
        }
        return board;
    }
}