package com.jiucaiyuan.net.question;
/**
* 【问题】N皇后问题,指的是n*n的棋盘，可以放n个皇后，要求任何两个皇后不同行、不同列，也不在同一条斜线上
* 给出一个整数n，返回n皇后的摆法有多少种
* 给n=1，返回1
* n=2或者3，2皇后和3皇后，无论怎么摆放都不行，返回0
* n=8，返回92
* 【思路】按照行往下摆放，然后一列一列尝试（加速版本会使用按照位操作来加速器处理，但是整体上也是所有都尝试一遍）
* 时间复杂度O(N^N)
*
* @Author jiucaiyuan 2022/4/19 23:26
* @mail services@jiucaiyuan.net
*/
public class NQueens {
/**
* @param n 皇后数
* @return 摆放种数
*/
public static int nQueens(int n) {
System.out.println("--------------" + n + "----------------------");
if (n < 1) {
return 0;
}
int[] record = new int[n]; //record[i] i行的皇后放到第几列上
return process1(0, record, n);
}
/**
* @param i 当前处理第i行元素
* @param record record[0~i-1]表示之前的行，放了皇后的位置，不共行、不共列、不共斜线
* @param n 总共有多少行（皇后个数）
* @return i行的摆法
*/
public static int process1(int i, int[] record, int n) {
if (i == n) {
print(record);
return 1;
}
int res = 0;
for (int j = 0; j < n; j++) {
//当前i行的皇后放到j列，会不会和之前i-1个皇后共列、共斜线
//如果是，无效，如果不是，有效
if (isValid(record, i, j)) {
record[i] = j;
res += process1(i + 1, record, n);
}
}
return res;
}
/**
* 检查是否存在共列、共斜线情况（不可能有共行情况，因为是一行一行处理的）
*
* @param record record[k] 表示k行摆放在record[k]列 0<=k<=i-1
* @param i 当前放到i行
* @param j i行放到j列
* @return 是否和之前的有共列、共斜线情况
*/
public static boolean isValid(int[] record, int i, int j) {
for (int k = 0; k < i; k++) {
if (record[k] == j //共列
|| Math.abs(k - i) == Math.abs(record[k] - j) //共斜线
) {
return false;
}
}
return true;
}
private static void print(int[] record) {
System.out.print(record[0]);
for (int i = 1; i < record.length; i++) {
System.out.print("," + record[i]);
}
System.out.println();
}
/**
* <pre>
* n皇后问题（加速版本）
* 【适用范围】由于限制用的是int类型值来表示，所以支持n<=32
* 【加速思路】：未加速版本是通过一个数组记录已经放置皇后，再放置时检查是否和已经放置的
* 共行、共列、共斜线，加速版本思路也是要检查是否共行、共列、共斜线，不过是每次处理
* 时往下传入列限制、左斜线限制、右斜线限制，其中这些限制是通过二进制运算得到，达到
* 加速的效果
* 【限制规则】：1的位置不能放皇后，0的位置可以
* 列限制 | 左斜线限制 | 右斜线限制 = 总限制
* colLim | leftDiaLim | rightDiaLim
* </pre>
*
* @param n 皇后个数
* @return 返回摆法的种数
*/
public static int nQueens2(int n) {
if (n < 1 || n > 32) {
System.out.println("加速方法的处理不支持超过32个皇后");
return 0;
}
//因为是32位，所以用upperLim来标识当前指定的是皇后个数，即22皇后时，upperLim值是 00000000001111111111111111111111
//右侧1的个数就是当前皇后个数
//(1<<n)-1 得到的是后面n个1，前面全是0
int upperLim = n == 32 ? -1 : (1 << n) - 1;
return process2(upperLim, 0, 0, 0);
}
/**
* <pre>
* 【加速思路】：未加速版本是通过一个数组记录已经放置皇后，再放置时检查是否和已经放置的
* 共行、共列、共斜线，加速版本思路也是要检查是否共行、共列、共斜线，不过是每次处理
* 时往下传入列限制、左斜线限制、右斜线限制，其中这些限制是通过二进制运算得到，达到
* 加速的效果
* 【限制规则】：1的位置不能放皇后，0的位置可以
* 列限制 | 左斜线限制 | 右斜线限制 = 总限制
* colLim | leftDiaLim | rightDiaLim
* </pre>
*
* @param upperLim
* @param colLim 列的限制
* @param leftDiaLim 左斜线的限制
* @param rightDiaLim 右斜线的限制
* @return
*/
public static int process2(int upperLim, int colLim, int leftDiaLim, int rightDiaLim) {
if (colLim == upperLim) {//列限制信息和皇后数一致了，即放完了所有皇后
return 1;
}
int pos = 0; //可以放皇后的位置
int mostRightOne = 0;
//colLim | leftDiaLim | rightDiaLim 总限制
//~(colLim | leftDiaLim | rightDiaLim) 可以放皇后的位置
//pos 指定n个皇后时可以放皇后的位置
pos = upperLim & (~(colLim | leftDiaLim | rightDiaLim));
int res = 0;
while (pos != 0) {
mostRightOne = pos & (~pos + 1);//按照二进制的方式表示pos，取到pos最右侧的1在哪个位置
pos = pos - mostRightOne; //每次减去最右侧一个1（当前循环尝试了），即按照这种方式来尝试所有可以尝试的次数
res += process2(upperLim,
colLim | mostRightOne, //当前处理的位置加入下次尝试的列限制中
(leftDiaLim | mostRightOne) << 1, //左侧限制向左侧移动一位作为下次尝试的左侧限制
(rightDiaLim | mostRightOne) >>> 1);// 右侧限制向右侧移动一位作为下次尝试的右侧限制
}
return res;
}
public static void main(String[] args) {
long start = System.currentTimeMillis();
System.out.println(nQueens(1));
System.out.println("耗时=" + (System.currentTimeMillis() - start));
start = System.currentTimeMillis();
System.out.println(nQueens(2));
System.out.println("耗时=" + (System.currentTimeMillis() - start));
start = System.currentTimeMillis();
System.out.println(nQueens(3));
System.out.println("耗时=" + (System.currentTimeMillis() - start));
start = System.currentTimeMillis();
System.out.println(nQueens(4));
System.out.println("耗时=" + (System.currentTimeMillis() - start));
start = System.currentTimeMillis();
System.out.println(nQueens(5));
System.out.println("耗时=" + (System.currentTimeMillis() - start));
start = System.currentTimeMillis();
System.out.println(nQueens(6));
System.out.println("耗时=" + (System.currentTimeMillis() - start));
start = System.currentTimeMillis();
System.out.println(nQueens(7));
System.out.println("耗时=" + (System.currentTimeMillis() - start));
start = System.currentTimeMillis();
System.out.println(nQueens(8));
System.out.println("耗时=" + (System.currentTimeMillis() - start));
start = System.currentTimeMillis();
System.out.println(nQueens(10));
System.out.println("耗时=" + (System.currentTimeMillis() - start));
start = System.currentTimeMillis();
System.out.println(nQueens(11));
System.out.println("耗时=" + (System.currentTimeMillis() - start));
start = System.currentTimeMillis();
System.out.println(nQueens(15));
System.out.println("耗时=" + (System.currentTimeMillis() - start));
start = System.currentTimeMillis();
System.out.println(nQueens2(15));
System.out.println("耗时=" + (System.currentTimeMillis() - start));
}
}