一、题目
N皇后问题要求求解在N*N的棋盘上放置N个皇后，
并使各皇后彼此不受攻击的所有可能的棋盘布局，
皇后彼此不受攻击的约束条件是：任何两个皇后均不能在棋盘上同一行、同一列或者同一对角线上出现。
输入：
给定棋盘的大小n
输出：
输出有多少种放置方法?
二、方法
回溯法：
利用试探性的方法，在包含问题所有解的解空间树中，将可能的结果搜索一遍，从而获得满足条件的解。搜索过程采用深度遍历策略，并随时判定结点是否满足条件要求，满足要求就继续向下搜索，若不满足要求则回溯到上一层，这种解决问题的方法称为回溯法。
回溯法求解问题步骤：
- 针对问题，画出问题的简易版解空间树
- 确定易于搜索的解空间结构
- 以深度优先方式搜索解空间，并且在搜索过程中永剪枝函数避免无效搜索(简单来说就是遍历过后不是我们要的就把它抛弃，用以提高效率)
以3皇后为例：
从第一层开始，一种可能一种可能的逐步遍历，遍历到底部如果还没找到便回溯到上一层继续遍历。
每一次递归时，此方格格放了可能非正解，就排除，提前判断check（），符合条件递归往下走。并给此方格标记‘W’，不符合在此列换下个格子，若都不符合此列递归完成到前一列状态，在判断，往往复复、直至得到正解输出继续未完成任务（此不是唯一解，所以还要继续，找到所有的解，若为唯一解，找到后用exit（0）退出程序）
每一次递归，如果不是正解，数组会被改变，所以不成立时用回溯回到上一个for循环状态
for (int i=0;i<n;i++){
if(check(res,i,row)){ //i——行|| row——列
res[i][row]='W';
dfs(res,n,row+1); //多重循环体，多多理解！
res[i][row]='*'; //回溯
}
}
check 作为判断是否符合条件，此格纵横斜均无皇后
纵：res[x][i]‘W’ 有返回false
横：res[i][y]‘W’ 有返回false
斜：斜向是 i+jx+y 正向、i-jx-y 反向
用check方法判断是否符合条件
static boolean check(char res[][],int x,int y){
for(int i=0;i<res.length;i++){
if(res[x][i]=='W')return false; //纵：res[x][i]‘W’ 有返回false
if(res[i][y]=='W')return false; //横：res[i][y]‘W’ 有返回false
for(int j=0;j<res.length;j++){
if(i+j==x+y&&res[i][j]=='W')return false;
if(i-j==x-y&&res[i][j]=='W')return false;
}
}
return true;
}
完整代码：
import java.util.Scanner;
public class NQueen{
public static void main(String[] args) { //主函数
Scanner scanner=new Scanner(System.in);//新创建一个输入的Scanner对象，然后赋值给sanner(作用就是获取控制台输入)
System.out.print("请输入皇后个数:");
int n=scanner.nextInt(); //输入函数
char res[][]=new char[n][n]; //对数组初始化
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
res[i][j]='*';
}
}
dfs(res,n,0); //调用深搜函数
System.out.print("符合条件的个数为:");
System.out.println(account);
}
static int account=0;
static void dfs(char res[][],int n,int row){
if(row==n){
account++;
System.out.println();
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
System.out.print(res[i][j]+" ");
}
System.out.println();
}
return;
}
for (int i=0;i<n;i++){
if(check(res,i,row)){
res[i][row]='W';
dfs(res,n,row+1);
res[i][row]='*';
}
}
}
static boolean check(char res[][],int x,int y){
for(int i=0;i<res.length;i++){
if(res[x][i]=='W')return false; //纵：res[x][i]‘W’ 有返回false
if(res[i][y]=='W')return false; //横：res[i][y]‘W’ 有返回false
for(int j=0;j<res.length;j++){
if(i+j==x+y&&res[i][j]=='W')return false;
if(i-j==x-y&&res[i][j]=='W')return false;
}
}
return true;
}
}
运行截图：
备注：一定重点理解多重循环！不然不好理解n皇后问题
部分资源来自原文链接