八皇后问题
八皇后问题（英文：Eight queens），是由国际象棋棋手马克斯·贝瑟尔于1848年提出的问题，是回溯算法的典型案例。
问题表述为：在8×8格的国际象棋上摆放8个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解，后来有人用图论的方法解出92种结果。如果经过±90度、±180度旋转，和对角线对称变换的摆法看成一类，共有42类。计算机发明后，有多种计算机语言可以编程解决此问题。
皇后之间需满足：
- 不在同一行上
- 不在同一列上
- 不在同一斜线上
代码
代码语言：javascript复制/**
* @BelongsProject:
* @BelongsPackage:
* @Author: tangshi
* @CreateTime: 2023-03-28 14:19
*/
public class EightEmperor {
/**
* 棋盘大小 8X8
*/
public static int checkSize = 4;
/**
* 棋盘(一维数组:下标0开始)
* 注释：数组下标表示行 值表示列
* 示例：check[4]=3 ->皇后在第4行3列
*/
private static int check[];
/**
* 解法个数
*/
private static int sum = 0;
static {
//生成棋盘，默认值-1表示这行没皇后
check = new int[checkSize];
for (int i = 0; i < check.length; i ) {
check[i] = -1;
}
}
public static void main(String[] args) {
System.out.println(checkSize "X" checkSize "解法如下：");
playChess(check,0);
}
/**
* 放置皇后
*
* @param check 棋盘
* @param index 放置的列，默认开始放第一列
*/
public static void playChess(int[] check, int index) {
for (int i = 0; i < checkSize; i ) {
//皇后放置在第index行 i列
check[index] = i;
//是否可以放置当前位置标识
boolean is = true;
//从第index列开始放，所以只需要判断小于index-1列的皇后是否符合规则
//因为大于index列没有放置皇后，不需要判断
for (int j = 0; j <= index - 1; j ) {
//判断是否对角线 行、列有值
if (check[j] == i (index - j) || check[j] == i - (index - j) || check[j] == i) {
//不能放置
is = false;
break;
}
}
if (is) {
//可以放置，如果是最后一行停止放置，否则继续放置下一行
if (index==checkSize-1){
printf(check);
}else {
playChess(check,index 1);
}
} else {
//不可以放置，重置当前行的值
check[index] = -1;
}
}
}
/**
* 棋盘输出
* @param check
*/
public static void printf(int[] check){
sum ;
System.out.println("第" sum "种解法，如图：");
int[][] ints=new int[checkSize][checkSize];
for (int i = 0; i < check.length; i ) {
ints[i][check[i]]=1;
}
for (int i = 0; i < checkSize; i ) {
for (int j = 0; j < checkSize; j ) {
System.out.print(ints[i][j] " ");
}
System.out.println();
}
}
}输出
代码语言：javascript复制4X4解法如下：
第1种解法，如图：
0 1 0 0
0 0 0 1
1 0 0 0
0 0 1 0
第2种解法，如图：
0 0 1 0
1 0 0 0
0 0 0 1
0 1 0 0 
