问题描述
请设计一种算法，解决著名的n皇后问题。这里的n皇后问题指在一个n*n的棋盘上放置n个棋子，
使得每行每列和每条对角线上都只有一个棋子，求其摆放的方法数。
分析
精髓在check
rec[i]=col 判断同一列嘛 行就不用判断 因为 row+1 只判断 当前位置和上一行的皇后
正反斜线判断
i + rec[i] == row + col
i - rec[i] == row - col对应俩坐标 x+y 相同 就是 在同一条正斜线上
对应俩坐标 x-y 相同 就是 在同一条反斜线上
代码
package BlueCup.Seven_recursion;
import java.util.Scanner;
import static java.lang.System.out;
public class Dfs4N皇后 {
static int n;
static int[] rec;
static int cnt = 0;
public static void main(String[] args) {
Scanner cin = new Scanner(System.in);
n = cin.nextInt();
rec = new int[n];//记录皇后的位置
dfs(0);
System.out.println(cnt);
}
/**
* @param row 正在处理的行
*/
private static void dfs(int row) {
if (row == n) {
cnt++;
return;
}
for (int col = 0; col < n; col++) {//皇后所在行的位置（依次每个列防止皇后）
if (check(rec, col, row)) {//检查位置 是否与之前的皇后冲突
rec[row] = col;//标记皇后
dfs(row + 1);
}
}
}
/**
*
* @param rec 皇后的位置 索引位行 值该位置
* @param col 所在行的位置 i-->col 所在列的位置
* @param row 所处的行
* @return 是否可以在该位置防止皇后
*/
private static boolean check(int[] rec, int col, int row) {
for (int i = 0; i < row; i++) {//遍历行
if (rec[i] == col) {//列相同了
return false;
}
if (i + rec[i] == row + col) {//正斜线
return false;
}
if (i - rec[i] == row - col) {//反斜线
return false;
}
}
return true;
}
}
本文作者：Author： 寒光博客
文章标题：[CC150]n皇后问题 dfs 不回溯
本文地址：https://dxoca.cn/Algorithm/223.html 百度已收录
版权说明：若无注明，本文皆为“Dxoca's blog （寒光博客）”原创，转载请保留文章出处。
本文地址：https://dxoca.cn/Algorithm/223.html 百度已收录
版权说明：若无注明，本文皆为“Dxoca's blog （寒光博客）”原创，转载请保留文章出处。
把所有几何对称的情况都单独算，算8次吗？实际情况只有cnt/8种吗？
我也在想 几何对称 是不是可以在 col =n/2 的时候 停下来 cnt*2 就是结果
旋转
还有对称后旋转
嗯 的确哦，，，
你是说 n=几,,,
思考 为什么可以不回溯 在 32行j加 rec[i]=-1
明白了 为什么不回溯 因为 res是一位数组 当同样的一行第k(k>1)次扫描到的时候 res[i]就会更新新的数据 所以没必要回溯 新扫描会覆盖旧值 且check是 在皇后 左上 右上 和 所在列判断的 所以无需 回溯 妙啊 妙啊~！！
check的永远的 之前的数据