51.N 皇后

题目描述

原题

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

上图为 8 皇后问题的一种解法。

给定一个整数 n，返回所有不同的 n 皇后问题的解决方案。

每一种解法包含一个明确的 n 皇后问题的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。

示例：

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

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

提示：

• 皇后彼此不能相互攻击，也就是说：任何两个皇后都不能处于同一条横行、纵行或斜线上。

题解

class Solution {
    /**
     * 数组索引是行号，数组元素是列号
     */
    int[] cols;
    List<List<String>> lists = new ArrayList<>();
    public List<List<String>> solveNQueens(int n) {
        if (n < 1) return null;
        cols = new int[n];
        place(0);
        return lists;
    }
    /**
     * 从第row行开始摆放皇后
     * @param row
     */
    void place(int row) {
        if(row == cols.length){
            lists.add(show());
            return;
        }
        for (int col = 0; col < cols.length; col++) {
            if (isValid(row, col)) {
                // 在第row行第col列摆放皇后
                cols[row] = col;
                place(row + 1);
            }
        }
    }
    /**
     * 判断第row行第col列是否可以摆放皇后
     */
    boolean isValid(int row, int col) {
    //遍历每一行
        for (int i = 0; i < row; i++) {
            // 第col列已经有皇后
            if (cols[i] == col) {
                return false;
            }
            // 第i行的皇后跟第row行第col列格子处在同一斜线上
            if (row - i == Math.abs(col - cols[i])) {
                return false;
            }
        }
        // System.out.println("[" + row + "][" + col + "]=true");
        return true;
    }
    List<String> show() {
        List<String> list = new ArrayList<>();
      for (int row = 0; row < cols.length; row++) {
        StringBuilder sb = new StringBuilder();
        for (int col = 0; col < cols.length; col++) {
          if (cols[row] == col) {
            sb.append("Q");
          } else {
            sb.append(".");
          }
        }
        list.add(sb.toString());
      }
         return list;
    }
}