LeetCode 52.N-Queens II

52.N-Queens II（N 皇后 II）

链接：

https://leetcode-cn.com/problems/n-queens-ii/

题目

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

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

示例:

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

 　　["..Q.",  // 解法 2
 　　 "Q...",
 　　 "...Q",
 　　 ".Q.."]
　　]

思路

这题思路较清晰，先在第一行第一列放置皇后，之后第二行寻找可以放皇后的地方，一行一行放置，如果哪一行不能放置，那么就回溯到上一行，如果放置到了最后一行，那么就代表这种情况成立，计数加一，返回之前一步。

图解

从左上角开始，line1是正对角线，line2是斜对角线，col是竖列。

代码

//列
private static boolean col[];

//正对角线 x-y+n-1
private static boolean line1[];

//斜对角线 x+y
private static boolean line2[];

public static int totalNQueens(int n) {
  col = new boolean[n];
  line1 = new boolean[2 * n - 1];
  line2 = new boolean[2 * n - 1];
  return putQueen(n, 0);
}

private static int putQueen(int n, int index) {
  int flag = 0;
  if (index == n) {
    return 1;
  }

  for (int i = 0; i < n; i++) {
    if (!col[i] && !line1[i - index + n - 1] && !line2[i + index]) {

      col[i] = true;
      line1[i - index + n - 1] = true;
      line2[i + index] = true;
      flag = flag + putQueen(n, index + 1);

      col[i] = false;
      line1[i - index + n - 1] = false;
      line2[i + index] = false;
    }
  }
  return flag;
}