引入
八皇后问题：是一个古老而著名的问题，是回溯算法的典型案例。该问题是国际西洋棋棋手马克斯·贝瑟尔于1848 年提出：在 8×8 格的国际象棋上摆放八个皇后，使其不能互相攻击，即： 任意两个皇后都不能处于同一行 、 同一列或同一斜线上，问有多少种摆法(92)。
根据排列组合：C64 取8，一共有4.426×10的9次方种方案
不难发现，每一行只能放一个皇后，所以8！=40320种方案
然后在40320种方案中，挑选符合题意的方案！
八皇后地图
根据条件我们可知每行每列最多都只能有一个皇后，这样可以在一定程度上缩减问题的规模。在第一行的某一列选择放置一个皇后，共有8种不同的选择，而第二行只能选择剩下的7列，也就是7种选择，剩下每一行的选择都会递减1，
那么总共可供选择的方案有8的阶乘种，已经是一种远优于暴力解法的解法，
但是这个阶乘的时间复杂度恐怕也难以令人接受，还有更优的解法吗？
解法
- 回溯递归法
- 回溯非递归法
- 生成遍历法
回溯递归法
回溯递归法基本框架
int a[n];
Queens(int k){
if(k==n){ //最后行皇后摆放ok
return
}
for (int i = 下界; i <=上界; i++) { //从当前行第一列开始遍历当前行所有列可能出现的位置
a[k]=i;//放一个皇后
if(check(k)){ //满足的约束条件，符和则放下一行位置的皇后
Queens(k+1);
}
//如果此位置皇后位置不合法，则回溯到当前行的下一列的位置(i++)继续递归搜索
}
}
基本思路：
- 第一个皇后先放第一行第一列
- 第二个皇后放在第二行第一列、然后判断是否 OK， 如果不 OK，继续放在第二列、第三列、依次把所有列都
放完，找到一个合适 - 继续第三个皇后，还是第一列、第二列……直到第 8 个皇后也能放在一个不冲突的位置，算是找到了一个正确 解
- 当得到一个正确解时，在栈回退到上一个栈时，就会开始回溯，即将第一个皇后，放到第一列的所有正确解， 全部得到.
- 然后回头继续第一个皇后放第二列，后面继续循环执行 1,2,3,4 的步骤
小结：当我们选择了第一个皇后的位置之后，与其处于同行同列同斜线的位置便都无法被选择，第二个皇后只能放在未被第一个皇后所辐射到的位置上，接着放置第三个皇后，同样不能放在被前两个皇后辐射到的位置上，
- 若此时已经没有未被辐射的位置能够被选择，也就意味着这种摆法是不可行的，我们需要回退到上一步，给第二个皇后重新选择一个未被第一个皇后辐射的位置，再来看是否有第三个皇后可以摆放的位置，如还是没有则再次回退至选择第二个皇后的位置，
- 若第二个皇后也没有更多的选择则回退到第一个皇后，重新进行位置的选择。
- 完成一次可行解即递归找到出口后，此时递归栈的栈顶会被弹出，次栈顶元素会被顶上，即下一行会继续搜索每列的位置，直到搜索到第一行所有列为止
图解
1.第一层递归，尝试在第一行摆放第一个皇后：
2.第二层递归，尝试在第二行摆放第二个皇后（前两格被第一个皇后封锁，只能落在第三格）：
3.第三层递归，尝试在第三行摆放第三个皇后（前四格被第一第二个皇后封锁，只能落在第五格）：
4.第四层递归，尝试在第四行摆放第四个皇后（第一格被第二个皇后封锁，只能落在第二格）：
5.第五层递归，尝试在第五行摆放第五个皇后（前三格被前面的皇后封锁，只能落在第四格）：
6.由于所有格子都“绿了”，第六行已经没办法摆放皇后，于是进行回溯，重新摆放第五个皇后到第八格。
7.第六行仍然没有办法摆放皇后，第五行也已经尝试遍了，于是回溯到第四行，重新摆放第四个皇后到第七格。
8.继续摆放第五个皇后，以此类推…
代码
package Algorithm.Recursion;
/** * @author Jerssy * @version V1.0 * @Description 递归回溯二维数组法 * @create 2021-02-27 19:55 */
public class EightQueen4 {
private static final int MAX_QUEEN_LENGTH=8;
private int totalCount=0;
private final int [][] queenArray=new int[MAX_QUEEN_LENGTH][MAX_QUEEN_LENGTH];
private void putQueens(int i){
if (i==MAX_QUEEN_LENGTH) { //递归边界. 只要走到这里,所有皇后必然不冲突,找到一次可行解
printQueens();
return;
}
//遍历每行的每一列
for (int j = 0; j < MAX_QUEEN_LENGTH; j++) {
if(checkLegal(i,j)){
queenArray[i][j]=1;//将此皇后放在第i行j列设置占位
putQueens(i+1);//探测下一行所有的列
//queenArray[i][j]=0;//每次递归完成即下一行皇后摆放出现不合法的则清空当前位置，并回溯到第i行j+1的位置即下一列①
}
queenArray[i][j]=0;//②此位置与①效果相同，因为校验位置失败则退出i+1的递归，继续执行下面代码
}
}
private boolean checkLegal(int n, int j){
for (int i = 0; i < MAX_QUEEN_LENGTH; i++) { //检查行列
if(queenArray[i][j]==1){
return false;
}
}
//因为这里是在放好了一行的皇后后，接着在下一行的某列寻找合适位置，所以只需要检查前一行某列位置的皇后与当前位置的皇后是否存在冲突
for (int k = n-1,m=j-1; k>=0&&m>=0; k--,m--) { //检查当前皇后的位置与当前位置的前一行所有列的左对角线
if (queenArray[k][m]==1 ) {
return false;
}
}
for (int k = n-1,m=j+1; k>=0&&m<MAX_QUEEN_LENGTH; k--,m++) { //检查当前皇后的位置与当前位置的前一行所有列的右对角线
if ( queenArray[k][m]==1 ) {
return false;
}
}
return true;
}
private void printQueens(){
totalCount++;
System.out.println("第"+totalCount+"种解法---------------------------");
for (int i = 0; i <MAX_QUEEN_LENGTH ; i++) {
for (int j = 0; j <MAX_QUEEN_LENGTH; j++) {
if (queenArray[i][j]==1){
System.out.print(" * ");
}else System.out.print(" 0 ");
}
System.out.println("");
}
}
public static void main(String[] args) {
long start= System.currentTimeMillis();
EightQueen4 eightQueen4 = new EightQueen4();
eightQueen4.putQueens(0);
long end= System.currentTimeMillis();
System.out.println("一共耗时"+(end-start));
}
}
效果
使用 int Q[8][8]; 存储八皇后的数据，看起来比较直观，但是深入思考一下，每一行只存放1个数据，这样使用二维数组会造成空间的浪费，所以可使用 int Q[10];
来存储八个皇后的位置，比如 Q[0]：第0行皇后的列数 Q[1]：第1行皇后的列数 …
用一个一维数组即可解决问题. arr[8] =
{0 , 4, 7, 5, 2, 6, 1, 3} //对应 arr 下标 表示第几行，即第几个皇后，arr[i] = val , val 表示第 i+1 个皇后，放在第 i+1
行的第 val+1 列
改进一：使用一维数组
package Algorithm.Recursion;
/** * @author Jerssy * @version V1.0 * @Description 八皇后递归回溯一维数组法 * @create 2021-02-27 9:56 */
public class EightQueen {
private static final int maxCount=8;
private int tailNumber=0;
int[] queueArray=new int[maxCount];
public static void main(String[] args) {
long start= System.currentTimeMillis();
EightQueen eightQueens = new EightQueen();
eightQueens. putQueens(0);
long end= System.currentTimeMillis();
System.out.println("一共存在的解："+ eightQueens.tailNumber);
System.out.println("一共耗时"+(end-start));
}
//校验皇后放的位置合法性
private boolean isLegal(int n){
for (int i = 0; i < n; i++) {
//当前行的元素与前一行(n-1)的元素位于相同的列或者位于斜线上
//行号-列号之差绝对值相等说明在同一条对角线上
if (queueArray[n]==queueArray[i]||Math.abs(queueArray[n] - queueArray[i]) ==Math.abs(n-i)) {
return false;
}
}
return true;
}
//递归回溯放皇后
private void putQueens(int n) {
//这里产生了回溯，当递归找到出口后，此时递归栈的栈顶会被弹出，次栈顶元素会被顶上，即下一行会继续搜索每列的位置，直到搜索到第一行所有列为止
if (n==maxCount) { //递归边界. 只要走到这里,所有皇后必然不冲突,找到一次可行解
printQueens();
return;
}
//遍历当前行的每一列
for (int i = 1; i <=maxCount; i++) {
queueArray[n]=i;//先把当前这个皇后 n , 放到该行的第 1 列
if (isLegal(n)){ //如果该位置皇后合法则递归放下一行的皇后
putQueens(n+1);
}
//如果此位置皇后位置不合法，则回溯到当前行的下一列的位置(i++)
}
}
private void printQueens(){
tailNumber++;
System.out.println("第"+tailNumber+"种解-----------------------------");
for (int k : queueArray) {
for (int j = 1; j <= maxCount; j++) {
if (j == k) {
System.out.print(" * ");
} else System.out.print(" 0 ");
}
System.out.println("");
}
}
}
因为每放置一个皇后需要移动到下一行，不需要对该行判断，只需要对列主副对角线进行判断即可；
如何用一个值代表一条线呢？
平面坐标系中的副对角线实际上也就是二维数组中的主对角线
所以得出:
任意一条副对角线公式为
y = x + b => b = y – x + n(数组中没有负数所以平移n位)
任意一条主对角线公式为
y = – x + b => b = x + y
主对角线: rup[x+y]
副对角线: lup[y-x+n]
b 是任意一条主副对角线到（0，0）的截距
那我们就可以通过一个一维数组来表示二维数组中的每一条主副对角线
至多会有2*n条主或副对角线，所以只需要开2n的空间就可以了
改进二：使用主副对角线判断
package Algorithm.Recursion;
/** * @author Jerssy * @version V1.0 * @Description 八皇后递归回溯主副对角线法 * @create 2021-02-28 10:38 * * 本质是递归回溯 * 只是判断条件不同 * * 每放置一个皇后需要移动到下一行，不需要对该行判断，只需要对列主副对角线进行判断即可 * * 那么问题来了如何用一个值代表一条线呢 * * 列: column[y] * * 平面坐标系中的副对角线实际上也就是二维数组中的主对角线 * 所以得出: * 任意一条副对角线公式为 * y = x + b => b = y - x + n(数组中没有负数所以平移n位) * 任意一条主对角线公式为 * y = - x + b => b = x + y * * 主对角线: rup[x+y] * 副对角线: lup[y-x+n] * * b 是任意一条主副对角线到（0，0）的截距 * * 那我们就可以通过一个一维数组来表示二维数组中的每一条主副对角线 * * 至多会有2*n条主或副对角线，所以只需要开2n的空间就可以了 * */
public class EightQueen5 {
private final int[] column; //同栏是否有皇后，1表示有
private final int[] rup; //主对角线
private final int[] lup; //副对角线
private final int[] queen; //皇后位置
private int num; //解法
private static final int maxCount=8;
public EightQueen5() {
column = new int[maxCount+1];
rup = new int[2*maxCount+1];
lup = new int[2*maxCount+1];
for (int i = 1; i <=maxCount; i++)
column[i] = 0;
for (int i = 1; i <=2*maxCount; i++)
rup[i] = lup[i] = 0; //初始定义全部无皇后
queen = new int[maxCount+1];
}
public void putQueens(int i) {
if (i >maxCount) {
printQueen();
} else {
for (int j = 1; j <=maxCount; j++) { //遍历当前行的所有列
if ((column[j] == 0) && (rup[i+j] == 0) && (lup[i-j+maxCount] == 0)) {
//若无皇后
queen[i] = j; //设定为占用
column[j] = rup[i+j] = lup[i-j+maxCount] = 1;
putQueens(i+1); //递归调用
column[j] = rup[i+j] = lup[i-j+maxCount] = 0;
}
}
}
}
private void printQueen() {
num++;
System.out.println("第"+num+"种解-----------------------------");
for (int y = 1; y <= maxCount; y++) {
for (int x = 1; x <= maxCount; x++) {
if(queen[y]==x) {
System.out.print(" * ");
} else {
System.out.print(" 0 ");
}
}
System.out.println();
}
}
public static void main(String[] args) {
long start= System.currentTimeMillis();
EightQueen5 queen = new EightQueen5();
queen.putQueens(1); //循环调用
long end= System.currentTimeMillis();
System.out.println("一共耗时"+(end-start));
}
}
回溯非递归法
回溯法从问题本身出发，寻找可能出现的所有情况。和穷举法类似，但回溯法如果发现情况不存在就返回上一步继续尝试其他
分支，直到找到所有解或者搜索完所有分支为止
其策略为：能进则进，不能进则换，不能换则退
回溯非递归法基本框架(就是一般的回溯法)
int a[n];int i=1
while(i>0){ //有路可走,但没有回溯到第一行
a[i]//设置第一个皇后的占位
while(i<=n&& a[i]位置不合法){
寻找a[i]下一个列的占位
}
if(在搜索范围内){
if(i==n)//找到一组可行解
打印皇后
else{
n++//继续寻找完整的解
}
}
else{
//回溯到上一行继续寻找占位，i--;并清空当前 a[i]的所占空间
}
}
回溯非递归法代码
package Algorithm.Recursion;
/** * @author Jerssy * @version V1.0 * @Description 八皇后解法：回溯法 * @create 2021-02-27 18:03 * * 回溯法从问题本身出发，寻找可能出现的所有情况。和穷举法类似，但回溯法如果发现情况不存在就返回上一步继续尝试其他 * 分支，直到找到所有解或者搜索完所有分支为止 * * 递归是从问题结果出发，不断的自己调用自己 * * 能进则进，不能进则换，不能换则退 * * * 回溯法框架： * * int a[n];int i=1 * while(i>0){//有路可走,但没有回溯到第一行 * a[i]//设置第一个皇后的占位 * while(i<=n&& a[i]位置不合法){ * 寻找a[i]下一个列的占位 * } * if(在搜索范围内){ * if(i==n)//找到一组可行解 * 打印皇后 * else{ * n++//继续寻找完整的解 * } * } * else{ * //回溯到上一行继续寻找占位，i--;并清空当前 a[i]的所占空间 * } * } * */
public class EightQueen3 {
private static final int MAX_QUEEN_LENGTH=8;
private int tailNumber=0;
private final int[] queenArray=new int[MAX_QUEEN_LENGTH+1];//记录每列皇后的位置，从1的位置开始记录
private void putQueens(){
int n=1;//代表行
while (n>0){ //找到一组可行解后此时n为8，则从当前行开始寻找此行其他的可行解，然后回溯到下一行继续寻找，直到第一行回溯完为止退出循环
queenArray[n]++;
while (queenArray[n]<=MAX_QUEEN_LENGTH&&!isLegal(n)){ //遍历一行的所有列，如果不合法则继续找当前行的下一列位置，如果此行所有列均不合法则queenArray[n]代表的列数会自增到9
queenArray[n]++;
}
//在搜索空间内
if (queenArray[n]<=MAX_QUEEN_LENGTH) { //当前行第queenArray[n]列的皇后的位置符合条件，否则当前行所有列位置均不合法则需要回溯到上一行
if(n==MAX_QUEEN_LENGTH){ //找到一组解
printQueens();
}
else n++;//没找全继续找
}
else { //不在则回溯到上一行，并清空占位
queenArray[n]=0;
n--;
}
}
}
//校验皇后放的位置合法性
private boolean isLegal(int n){
for (int i = 1; i <n; i++) {
//当前行的元素与前一行(n-1)的元素位于相同的列或者位于斜线上
//行号-列号之差绝对值相等说明在同一条对角线上
if (queenArray[n]==queenArray[i]||Math.abs(queenArray[n] - queenArray[i]) ==Math.abs(n-i)) {
return false;
}
}
return true;
}
private void printQueens(){
tailNumber++;
System.out.println("第"+tailNumber+"种解-----------------------------");
for (int i = 1; i <=MAX_QUEEN_LENGTH; i++) {
for (int j = 1; j <= MAX_QUEEN_LENGTH; j++) {
if (j == queenArray[i]) {
System.out.print(" * ");
} else System.out.print(" 0 ");
}
System.out.println("");
}
}
public static void main(String[] args) {
long start= System.currentTimeMillis();
new EightQueen3().putQueens();
long end= System.currentTimeMillis();
System.out.println("一共耗时"+(end-start));
}
}
生成遍历法
package Algorithm.Recursion;
/** * @author Jerssy * @version V1.0 * @Description 八皇后解法:生成遍历法：先产生所有的可能，然后根据限制条件过滤结果 * @create 2021-02-27 17:26 * * 此方法相比递归和回溯效率要差，因为回溯是只要当前分支无法继续搜素下去时候就会停止搜索，返回上一行寻找其他可行分支。 */
public class EightQueen2 {
int[] queueArray=new int[8]; int tailNumber = 0, maxCount = 8,executeNum=0;
private void search(int n) {
executeNum++;//执行次数
//检查每个可能，看是否会冲突
if(n == maxCount) {
for(int i = 0; i < maxCount; i++) { //当前行位置的皇后
for (int j = i + 1; j < maxCount; j++) { //下一行位置的皇后
//当前行的元素与下一行的元素位于相同的列或者位于斜线上则冲突
if (queueArray[i] == queueArray[j] || Math.abs(queueArray[i] - queueArray[j]) == Math.abs(i - j)) {
return;
}
}
}
//找到一个没冲突的可能
tailNumber++;
}
//遍历生成所有的可能
else for(int i = 0; i < maxCount; i++) {
queueArray[n] = i;
search(n+1);
}
}
public static void main(String[] args) {
long start= System.currentTimeMillis();
EightQueen2 eightQueue2 = new EightQueen2();
eightQueue2.search(0);
System.out.println("可行解:"+eightQueue2.tailNumber);
System.out.println("一共执行次数："+eightQueue2.executeNum);
long end= System.currentTimeMillis();
System.out.println("一共耗时"+(end-start));
}
}
制作八皇后小游戏
搞清楚了八皇后问题下面可以开发个八皇后小游戏验证是否正确
先看效果图
一：绘制棋盘
public QueenFrame() {
setSize(FRAME_WIDTH,FRAME_HEIGHT);
setLocationRelativeTo(null);//窗口居中
JPanel queenPanel = new JPanel();
//棋盘初始化
initialization(queenPanel);
queenPanel.setLayout(new GridLayout(MAX_QUEEN_LENGTH,MAX_QUEEN_LENGTH));
add(queenPanel,BorderLayout.CENTER);
setResizable(false);
setVisible(true);
//关闭窗口事件
addWindowListener(new WindowAdapter() {
@Override
public void windowClosing(WindowEvent e) {
System.exit(0);
}
});
}
//初始化棋盘
private void initialization(JPanel queenPanel) {
for (int i=0;i<MAX_QUEEN_LENGTH;i++){
for (int j=0;j<MAX_QUEEN_LENGTH;j++){
queenMap[i][j]=new QueenPanelMap(i,j);
queenMap[i][j].unConflict=0;
int finalI = i;
int finalJ = j;
//为每个棋格绑定鼠标点击事件
queenMap[i][j].addMouseListener(new MouseAdapter() {
@Override
public void mouseClicked(MouseEvent e) {
setCursor(Cursor.getPredefinedCursor(Cursor.HAND_CURSOR));
putQueens(e, finalI, finalJ);
}
});
queenPanel.add(queenMap[i][j]);
}
}
}
二 放置皇后
//放置皇后
private void putQueens(MouseEvent e, int n , int j) {
JPanel panel=(JPanel) e.getComponent();
if (panel.getComponents().length==0) { //如果当前棋格里没有放皇后
QueenImage queenImage = new QueenImage();
queenImage.setBackground(panel.getBackground());
panel.add(queenImage,BorderLayout.CENTER);
panel.validate();//添加了皇后组件重载此棋格容器
lastLine=n;
isChecked=false;
if (!checkLegal(n, j)){
System.out.println("游戏结束");
JOptionPane.showMessageDialog(QueenFrame.this,"很遗憾,你输了");
clearQueenMap();
return;
}
queenMap[n][j].unConflict=1;
totalNum++;
if (totalNum==MAX_QUEEN_LENGTH) {
//1 5 8 6 3 7 2 4
int selectI = JOptionPane.showConfirmDialog(QueenFrame.this, "恭喜，你赢了！是否在来一次？", "提示",JOptionPane.YES_NO_OPTION);
if (selectI == 0) {
clearQueenMap();
}
}
}
else { //再次点击删除已放置的皇后
panel.remove(panel.getComponents()[0]);
panel.repaint();
queenMap[n][j].unConflict=0;
totalNum--;
}
}
三 验证八皇后问题
先看个错误的
在测试个通过的
正确的一种解法– 1 5 8 6 3 7 2 4
完整代码
package Algorithm.Recursion;
import javax.swing.*;
import java.awt.*;
import java.awt.event.MouseAdapter;
import java.awt.event.MouseEvent;
import java.awt.event.WindowAdapter;
import java.awt.event.WindowEvent;
/** * @author Jerssy * @version V1.0 * @Description 模拟八皇后游戏 * @create 2021-02-28 15:33 * * repaint()方法是重绘，而validate()是重载，一般来说，从一个容器中删除某个组件需要调用repaint()，而把某个组件添加到某一容器中，则需调用validate() * 当你改变一个会影响它们外观的属性时调用repaint();当你改变一个会影响它们宽度/高度的属性时， revalidate()被调用 * * invalidate()将容器标记为无效。意味着内容在某种程度上是错误的，必须重新布局。但它只是一种标志/旗帜。有可能以后必须刷新多个无效容器。 * * validate()执行重新布局。这意味着要求所有大小的无效内容，并且LayoutManager将所有子组件的大小设置为正确的值。 * revalidate()只是两者的总和。它将容器标记为无效并执行容器的布局。 * */
public class EightQueenGame {
private static final int FRAME_WIDTH=600;//窗口长
private static final int FRAME_HEIGHT=600;//窗口宽
private static final int MAX_QUEEN_LENGTH=8;//棋盘最大容量
public static void main(String[] args) {
new QueenFrame();
}
static class QueenFrame extends Frame {
private final QueenPanelMap[][] queenMap=new QueenPanelMap[MAX_QUEEN_LENGTH][MAX_QUEEN_LENGTH];//棋盘数组
private int totalNum=0;//记录步数
private int lastLine=0;//上一行
private boolean isChecked=false;//是否校验过了
private int checkedLen=0;//校验次数
public QueenFrame() {
setSize(FRAME_WIDTH,FRAME_HEIGHT);
setLocationRelativeTo(null);//窗口居中
JPanel queenPanel = new JPanel();
//棋盘初始化
initialization(queenPanel);
queenPanel.setLayout(new GridLayout(MAX_QUEEN_LENGTH,MAX_QUEEN_LENGTH));
add(queenPanel,BorderLayout.CENTER);
setResizable(false);
setVisible(true);
//关闭窗口事件
addWindowListener(new WindowAdapter() {
@Override
public void windowClosing(WindowEvent e) {
System.exit(0);
}
});
}
//初始化棋盘
private void initialization(JPanel queenPanel) {
for (int i=0;i<MAX_QUEEN_LENGTH;i++){
for (int j=0;j<MAX_QUEEN_LENGTH;j++){
queenMap[i][j]=new QueenPanelMap(i,j);
queenMap[i][j].unConflict=0;
int finalI = i;
int finalJ = j;
//为每个棋格绑定鼠标点击事件
queenMap[i][j].addMouseListener(new MouseAdapter() {
@Override
public void mouseClicked(MouseEvent e) {
setCursor(Cursor.getPredefinedCursor(Cursor.HAND_CURSOR));
putQueens(e, finalI, finalJ);
}
});
queenPanel.add(queenMap[i][j]);
}
}
}
//放置皇后
private void putQueens(MouseEvent e, int n , int j) {
JPanel panel=(JPanel) e.getComponent();
if (panel.getComponents().length==0) { //如果当前棋格里没有放皇后
QueenImage queenImage = new QueenImage();
queenImage.setBackground(panel.getBackground());
panel.add(queenImage,BorderLayout.CENTER);
panel.validate();//添加了皇后组件重载此棋格容器
lastLine=n;
isChecked=false;
checkedLen=0;
if (!checkLegal(n, j)){
System.out.println("游戏结束");
JOptionPane.showMessageDialog(QueenFrame.this,"很遗憾,你输了");
clearQueenMap();
return;
}
queenMap[n][j].unConflict=1;
totalNum++;
if (totalNum==MAX_QUEEN_LENGTH) {
//1 5 8 6 3 7 2 4
int selectI = JOptionPane.showConfirmDialog(QueenFrame.this, "恭喜，你赢了！是否在来一次？", "提示",JOptionPane.YES_NO_OPTION);
if (selectI == 0) {
clearQueenMap();
}
}
}
else { //再次点击删除已放置的皇后
panel.remove(panel.getComponents()[0]);
panel.repaint();
queenMap[n][j].unConflict=0;
totalNum--;
}
}
//清空棋盘
private void clearQueenMap() {
for (int i=0;i<MAX_QUEEN_LENGTH;i++){
for (int j=0;j<MAX_QUEEN_LENGTH;j++){
if (queenMap[i][j].getComponents().length!=0) {
queenMap[i][j].remove(queenMap[i][j].getComponents()[0]);
queenMap[i][j].repaint();
}
queenMap[i][j].unConflict=0;
}
}
totalNum=0;
}
//校验皇后放的位置合法性
private boolean checkLegal(int n, int j) {
if (n ==MAX_QUEEN_LENGTH||n<0) {
return true;
}
for (int k = 0; k < MAX_QUEEN_LENGTH; k++) {
//校验当前行所有的列及当前列所有的行
if (lastLine==n){
if (queenMap[n][k].unConflict == 1||queenMap[k][j].unConflict==1) {
return false;
}
}
else {
//校验对角线
if (Math.abs(j-k)==Math.abs(lastLine-n)) {
if (queenMap[n][k].unConflict == 1) {
return false;
}
}
}
}
//校验当前行后面的行①
checkedLen++;
if (!isChecked&&!checkLegal(n+1,j)) {
return false;
}
//这里定位到①位置递归开始的位置，否则②位置又从n=7的位置开始向上递归，这是完全不必要的因为这些位置已经在①步骤检查过了
isChecked=true;
System.out.println(n);
return checkLegal(MAX_QUEEN_LENGTH-checkedLen - 1, j);//②校验当前行前面的行
}
}
private static class QueenPanelMap extends JPanel {
private int unConflict=0;
public QueenPanelMap(int i,int j) {
if ((j+i) %2==0) {
setBackground(Color.WHITE);
}
else setBackground(Color.BLUE);
}
}
private static class QueenImage extends JPanel {
Image imageIcon;
private static int dstWidth=0;
private static int dstHeight=0;
private static int maxWidth=0;
private static int maxHeight=0;
public QueenImage() {
imageIcon= new ImageIcon("Algorithm\\src\\Algorithm\\Recursion\\queen.png").getImage();
int srcWidth= imageIcon.getWidth(null);
if (srcWidth<0) {
throw new RuntimeException("加载图片失败");
}
int srcHeight= imageIcon.getHeight(null);
maxWidth=FRAME_WIDTH/MAX_QUEEN_LENGTH;
maxHeight=FRAME_HEIGHT/MAX_QUEEN_LENGTH;
dstWidth=srcWidth;
dstHeight=srcHeight;
float k;
if (srcWidth>maxWidth){
dstWidth=maxWidth;
k=(float)srcWidth/(float)maxWidth;
dstHeight=Math.round((float)srcHeight/k);
}
else if (srcWidth<maxWidth/2) {
dstWidth=maxWidth/2;
}
srcHeight=dstHeight;
if (srcHeight>maxHeight){
dstHeight=maxHeight;
k=(float)srcHeight/(float)maxHeight;
dstWidth=Math.round((float)dstWidth/k);
}
else if (srcHeight < maxHeight / 2) {
dstHeight=maxHeight;
}
}
public void paintComponent(Graphics g){
super.paintComponent(g);
setBounds((maxWidth-dstWidth)/2-1,(maxHeight-dstHeight)/2-3,dstWidth,dstHeight);
g.drawImage(imageIcon,0,0,dstWidth , dstHeight, this);
}
}
}
本文地址：https://blog.csdn.net/weixin_49561445/article/details/114270361
黄山市民网：https://www.huangshanshimin.com/
