初识N皇后
前置知识：
如图在9*9的棋盘正中央有一颗皇后棋子。颜色加深位置代表该皇后的攻击范围，可以发现攻击范围是该皇后所在的行，所在的列，以及以皇后为中心的主对角线和次对角线，类似一个"米"字。
N皇后问题要求
现在有N*N的棋盘，里面要放N个皇后，问如何摆放这N个皇后，使得她们彼此不互相攻击？
解题思路
通过思考，我们发现如果每一行只放一个皇后，那么就可以规避掉皇后在 相同行上出现互相攻击的情况。
所以 在某一行放了一个皇后之后，只要判断 前面若干行上皇后的位置 是否与该行 皇后的位置发生 "列" 以及 "对角线" 的位置冲突。
那么如何判断"列"发生了位置冲突？ 当前行上摆放的一个皇后 ，她的所在列 与在她前面摆放的所有皇后的 列进行比较，只要找出任意一个皇后与该行皇后在同一列 ，直接返回false，表示该行皇后不能在这个列的位置摆放，直接去该行下一个列进行判断，直到满足条件进行下一个皇后的摆放或碰到棋盘列的边界退出
那么如何判断"对角线"上的位置冲突？ 观察上面皇后的攻击范围，我们发现，假设在一个皇后的对角线上摆放了另一个皇后，那么这两个皇后之间的行列位置将满足 ： |皇后1的行坐标 - 皇后2的 行坐标| = |皇后1的列坐标 - 皇后 2 的列坐标|。
说白了将这两个皇后之间的距离如果用曼哈顿距离来表示，那么就是一个等腰直角三角形的两条直角边。只要在某一行上摆放了一个皇后，发现 与之前已经摆放好的任意一个皇后 的 行列坐标关系 满足上面那个 规律 ，那就是对角线 上发生了位置冲突。
最后只需 将 列位置冲突 和 对角线 位置冲突 在判断时 用 "|" 连接起来即可，满足其中一个条件，那就表示位置冲突 。
Java代码
import java.util.Scanner;
/**
* @Author: 幸幸
* @Date: 2023/03/25/14:46
* @Description:
*/
public class NQueens {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.println("输入皇后数量");
int queenNumber = sc.nextInt();
int[] queensRecords = new int[queenNumber];//用数组的下标表示每一行，用数组下标对应的值表示皇后的列的位置
System.out.println(attempt(queensRecords, 0, queenNumber));//传进去0下标,代表我从第一行开始摆放
}
public static int attempt(int[]queensRecords,int nowRow,int queenNumber){
if(nowRow == queenNumber) return 1;//如果发现当前行能够来到棋盘越界的位置，证明这是一种可行的摆放皇后的方式，返回1表示是一种可行的方法
int res = 0;
for(int column = 0 ; column < queenNumber ;column++){//nowRow : 当前行的每一列进行判断
if(isValid(queensRecords,nowRow,column)){ //isValid:该方法表示当前行,当前列传进去,与之前摆放好的皇后的行列位置有冲突吗?没有那就true,直接去下一行摆放皇后,如果false,那么表示当前行的当前列不能摆放，尝试当前行的后面的列直到满足摆放要求或遇到列的边界退出
queensRecords[nowRow] = column;//用数组的下标表示每一行，用数组下标对应的值表示皇后的列的位置。也就是当前列满足摆放要求,将当前列位置象征的数字赋值给数组
res+=attempt(queensRecords,nowRow+1,queenNumber);//当前行摆放皇后成功了,那就去直接去下一行摆放皇后
}
}
return res;
}
private static boolean isValid(int[] queensRecords, int nowRow, int column) {
for(int preRow = 0 ; preRow<nowRow ;preRow++){
if (column == queensRecords[preRow] || Math.abs(nowRow-preRow)==Math.abs(column-queensRecords[preRow])){
return false;
}
}
return true;
}
}
LeetCode打印N皇后
这样的话，现在我们可以解决LeetCode上的一题N皇后了。
大致思路和上面差不多。依旧是用一个整型数组的下标表示皇后的行，下标对应的值代表皇后的列。
在初始化二维字符数组的时候 ，如果二维数组的列 和 一维整型数组的列（也就是皇后的列坐标）相同，那就在该位置填入'Q'
否则就填入'.'
一次成功后， 不要忘记把那个保存每一行字符串的集合给清空。
如果未清空上一次成功的字符串集合，则会在原先的基础上添加下一次的成功字符串
所以记得清空集合
当然这是我现在的水平能想出的一种方法吧。
写出来还是挺开心的。
LeetCode打印N皇后代码
import java.util.ArrayList;
import java.util.List;
/**
* @Author: 幸幸
* @Date: 2023/03/25/18:55
* @Description:
*/
public class Solution {
/* public static void main(String[] args) {
for (List<String> list : solveNQueens(9)) {
System.out.println(list);
}
}*/
public static List<List<String>> solveNQueens(int n) {
int[] queensRecord = new int[n]; // 下标代表行 ，下标对应的值代表列
char[][] c = new char[n][n];
List<String> stringList = new ArrayList<>();
List<List<String>> listList = new ArrayList<>();
attempt(queensRecord,0,n,c,stringList,listList);
return listList;
}
public static void attempt(int[] queensRecord, int nowRow, int n,char[][]c,List<String>stringList,List<List<String>>listList) {
if (nowRow == n){
//说明现在queenRecord 数组中 记录了 n个 皇后的 坐标
//我只需要把这个皇后的行列坐标放到 二维数组中即可
initAndAssign(queensRecord,c,stringList,listList); //将记录了皇后坐标的一维数组和 空的二维数组传入初始化并赋值
return;
}
for (int column = 0; column < n; column++) {
if (isValid(queensRecord, nowRow, column)) {
queensRecord[nowRow] = column;
attempt(queensRecord,nowRow+1,n,c,stringList,listList);
}
}
}
private static boolean isValid(int[] queensRecord, int nowRow, int column) {
for (int preRow = 0; preRow < nowRow; preRow++) {
if (column == queensRecord[preRow] || Math.abs(nowRow - preRow) == Math.abs(column - queensRecord[preRow]))
return false;
}
return true;
}
private static void initAndAssign(int[]queensRecord,char[][]c,List<String>stringList,List<List<String>> listList){
String temp = "";
for(int i = 0 ; i<c.length;i++){
for (int j = 0 ; j <c[i].length;j++){
if(j == queensRecord[i]){
temp+='Q';
}
else {
temp+='.';
}
} // 每一行写完，将他赋值到stringList中去。
stringList.add(temp);
temp = "";
}
ArrayList<String> listCopy = new ArrayList<>(stringList);
listList.add(listCopy); //这里需要把stringList清空,不然stringList还会保留上一次成功案例的一整组字符串
stringList.clear();
}
}
今日小记
今天早上去配眼镜了，然后遇到了一个极差的验光师，被坑了50验光费。早上很冷，去肯德基蹭了空调，可惜带了黑笔却没带纸。也是在那里大致了解了什么是N皇后，这个听起来挺玄乎的问题，今天算是理解了一点。然后又是四处找眼镜店，配了一副中规中矩的眼镜。
中午吃了一个芝麻包，一个肉包，一个青团。外边小店的青团里的馅是紫薯做的，学校里的青团里面是豆沙还有一颗桂圆。
回到学校已经下午三点了，浪费了一个早上。
从原本专科学机械当现在进入本科学计算机，不懂的还有很多很多。上课也不想听那些老师讲一些已经过时很久的知识点。在这个阶段很少有共同进退的朋友。原本专科的那些朋友现在感情也渐渐的淡了。似乎没有了前进的动力。不过这个月在bilibili刷到了左程云老师的算法视频，讲得真的很好。对我这种小白来讲，算是丰满了我的羽翼吧。还有张楠老师，没有他，我真不知道如何去应付本学期的javaEE。
今天就到这吧，任重道远，保障睡眠很重要。
标签：queensRecord,int,摆放,column,nowRow,初识,皇后,MyBlog2 From： https://www.cnblogs.com/doubleLucky/p/17255030.html