![Java解决八皇后问题及利用回溯法的动态搜索路径的GUI展示[含详细解析],第1张](/aiimages/Java%E8%A7%A3%E5%86%B3%E5%85%AB%E7%9A%87%E5%90%8E%E9%97%AE%E9%A2%98%E5%8F%8A%E5%88%A9%E7%94%A8%E5%9B%9E%E6%BA%AF%E6%B3%95%E7%9A%84%E5%8A%A8%E6%80%81%E6%90%9C%E7%B4%A2%E8%B7%AF%E5%BE%84%E7%9A%84GUI%E5%B1%95%E7%A4%BA%5B%E5%90%AB%E8%AF%A6%E7%BB%86%E8%A7%A3%E6%9E%90%5D.png "Java解决八皇后问题及利用回溯法的动态搜索路径的GUI展示[含详细解析],第1张")
- 1、前言
- 2、什么是八皇后问题
- 2.1 问题
- 2.2 直观的解释
- 3、解决八皇后问题
- 3.1 代码
- 3.2 控制台运行结果
- 4、动态展示部分的Java GUI 代码
- 4.1 主界面——Jframe类
- 4.2 面板——JPanel类
- 4.3 鼠标监听器——MouseListener类
- 4.4 queen.png
- 4.5 代码结构
- 5、GUI部分代码解释
- 5.1 搜索算法模型[再强调一次]
- 5.2 函数功能
- 5.2.1 初始化绘制8×8网格的函数
- 5.2.2 回溯法主要实现函数eightQueen
- 5.2.3 判断落子点是否合法函数isLegalLoc
- 5.2.4 鼠标监听函数mouseCliscked(MouseEvent e)
- 5.2.5 打印落子路径的函数printLocation
- 6、动态展示结果
- 6.1 八皇后问题运行结束界面
- 6.2 八皇后问题运行中的界面
- 6.3 整体走一遍吧！
- 7、存在的小问题
- 8、创新点
- 9、结语
这篇博文，我不仅解决了八皇后问题（自己的见解），同时我还实现了用回溯法动态搜索的八皇后问题路径的GUI展示。这是全网独家的教程，我也相信这个教程（输出的结果）能对要入门该算法的同学有一个非常直观的学习体验。其中，八皇后问题的搜索算法我使用了经典的回溯法。
申明：无论是从八皇后算法到整个GUI框架的搭建，都由我独立完成。还是那句话，如果对你有帮助，不要白嫖（手动doge.png）~
八皇后问题，是一个古老而著名的问题，是回溯算法的典型案例。该问题是国际西洋棋棋手马克斯·贝瑟尔于1848年提出：在
8
×
8
8 times 8
8×8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。
那什么是回溯法呢？我参考了维基百科的解释：
回溯法（backtracking）是暴力搜索算法的一种。它采用试错的思想，它尝试分步的去解决一个问题。在分步解决问题的过程中，当它通过尝试发现，现有的分步答案不能得到有效的正确的解答的时候，它将取消上一步甚至是上几步的计算，再通过其它的可能的分步解答再次尝试寻找问题的答案。回溯法通常用最简单的递归方法来实现，在反复重复上述的步骤后可能出现两种情况：
- 找到一个可能存在的正确的答案
- 在尝试了所有可能的分步方法后宣告该问题没有答案
下面我通过java注释的形式展示利用回溯法的思想，解决八皇后问题的第一次搜索：
其中，-代表这个位置可以放棋子，*代表该位置不能放棋子，而+代表这个位置已经放下棋子了。我用这三个符号代表一个
8
×
8
8 times 8
8×8的棋盘，每个位置都可以用坐标表示。
我自己总结的回溯法的搜索策略就是：从左到右不回头，从上往下走，找不到就从下往上回头往右找，这样扫荡一遍，就不会遗漏棋盘上的任何一种可能出现的位置。回溯法这种算法思想用代码实现需要结合递归的 *** 作。
就上面的例子来说，显然最后一个皇后的落子为**(7,5)，由于此时无子可落（棋盘上没有-了）且皇后数不足八个，要进入的下一层递归直接找到出口。所以我们需要回溯，通过return;首先回到(7,5)的帧栈，执行pollLast语句，取出(7,5)**在链表中的位置。这里要注意一下，如果(7,5)的右边还有符号-，也就是可以放置棋子的地方，比方说(7,6)。此时这个位置的棋子就要被put进链表中（用for循环遍历该行）。接着，虚拟棋盘应该变为：
接上文，也就是上图的第6个棋盘；同理，继续执行回退帧栈的 *** 作，取出**(3,4)**，虚拟棋盘变为上图第5个，通过for循环在第四行继续按列扫荡，我们找到另外一个空位(6,4),以此类推。
3、解决八皇后问题 3.1 代码 我在代码中做出了非常详细的解释，这也是我一个字一个字打出来的切身体会。
回溯法的巧妙之处在于,我们不用先定义
8
×
8
8times8
8×8的棋盘，而是通过for循环对每一列的每一行或者每一行的每一列进行判断（每个皇后的位置一定是每一行有且只有一个，并且是每一列有且只有一个）。这里我统一对棋盘的每一行的每一列进行遍历。也就是说，这个棋盘是虚拟的，我们通过逐行搜索来记录符合位置规范的落子。所以我们要记录下我们所摆放的棋子路径。（更具体的解释详见下面的代码与解释）
我定义了EightQueen类实现八皇后的回溯法，还包含了一个静态的Location类。下面每个函数的功能，我都做了注释。[这个EightQueen类是独立的，与动态展示部分没有直接关系]
package EightQueen;
import java.util.linkedList;
public class EightQueen{
private static final int SIZE = 8; //皇后的个数，此处设为8，表示8个皇后
private static int count = 0; //记录摆放的方式数
public static void main(String[] args) {
linkedList list = new linkedList();
eightQueen(list, 0, 0); //从棋盘的第0行第0列开始
System.out.println("八皇后共有 " + count + "种摆放方式");
}
static class Location {
int x ; //对应棋盘的列
int y ; //对应棋盘的行
Location(int x, int y){
this.x = x;
this.y = y;
}
@Override
public String toString() {
return "(" + x + ", " + y + ")";
}
}
private static void eightQueen(linkedList list, int x, int y) {
if(list.size() == SIZE){ //当list元素个数为8时，表示8个皇后都摆放完毕
printLocation(list); //打印皇后摆放方式
return ;//当八个皇后都摆放完毕,我们使用return可以返回之前的栈空间执行剩下的语句
}
for(int i = x ; i < SIZE ; i++){
Location loc = new Location(i, y);
if(isLegalLoc(list, loc)){
list.offer(loc); //将第y行的皇后摆放好
eightQueen(list, 0, y+1); //开始摆放y+1行的皇后，同样从第0列开始摆放
//这里我们用到栈的数据结构来实现回溯法,递归到底部然后回溯到保存之前信息的栈空间,然后执行pollLast的语句
list.pollLast(); //假如总共排放的皇后不能达到8个的话，都要将其撤回，再试探其它的摆法。这就是回溯法。
}//pollLast方法:Retrieves and removes the last element of this list,or returns null if this list is empty.
}
//假如有一行的每一列都放不下,那么for循环结束后自动返回之前的栈空间;递归中每一层，也就是每次进入一个方法体后我们都会创建一个新的栈空间
}
private static boolean isLegalLoc(linkedList list, Location loc) {
for(Location each : list){
if(loc.x == each.x || loc.y == each.y) //判断是否在同一行或同一列
return false;
else if (Math.abs(loc.x - each.x) == Math.abs(loc.y - each.y)) //判断是否在同一对角线或反对角线上
return false;
}
return true;
}
private static void printLocation(linkedList list) {
for(Location each : list){
System.out.print(each.toString() + "t");
}
System.out.println();
count ++;
}
}
3.2 控制台运行结果
以下代码关键的地方我都做了注释，比较需要注意的就是Listener类。
4.1 主界面——Jframe类Mainframe类（继承自Jframe）调用Jpanel类。
package EightQueen;
import java.awt.EventQueue;
import javax.swing.Jframe;
public class Mainframe extends Jframe {
int windowWidth;
int windowHeight;
int n=0;
public static void main(String[] args) {
EventQueue.invokeLater(new Runnable() {
public void run() {
try {
Mainframe frame = new Mainframe();
frame.setVisible(true);
} catch (Exception e) {
e.printStackTrace();
}
}
});
}
public Mainframe() {
setDefaultCloseOperation(Jframe.EXIT_ON_CLOSE);
setBounds(600, 200, 1200, 649);
this.setTitle("八皇后问题的动态表示");
windowWidth = this.getWidth(); // 获得Jframe宽
windowHeight = this.getHeight(); // 获得Jframe高
Jpanel contentPane = new Jpanel();
add(contentPane);
this.setVisible(true);
}
}
4.2 面板——JPanel类
Jpanel类（继承JPanel类）调用Listenr类。
package EightQueen;
import java.awt.Color;
import java.awt.Graphics;
import javax.swing.ImageIcon;
import javax.swing.JPanel;
import javax.swing.JLabel;
import javax.swing.JButton;
import java.awt.Font;
import javax.swing.JScrollPane;
import javax.swing.Jtextarea;
public class Jpanel extends JPanel {
int w = 600;
int h = 600;
static int x[] = new int[8];
static int y[] = new int[8];
JScrollPane scrollPane;
Jtextarea textarea;
private ImageIcon icon = new ImageIcon("src/EightQueen/queen.png");
public Jpanel() {
setSize(1158,600);
setLayout(null);
JLabel lblNewLabel = new JLabel("u516Bu7687u540Eu95EEu9898u52A8u6001u5C55u793A");
lblNewLabel.setBounds(826, 13, 190, 52);
lblNewLabel.setFont(new Font("宋体", Font.PLAIN, 20));
add(lblNewLabel);
JButton btnNewButton_1 = new JButton("动态展示");
btnNewButton_1.setBounds(826, 558, 168, 29);
btnNewButton_1.setFont(new Font("宋体", Font.PLAIN, 18));
add(btnNewButton_1);
btnNewButton_1.addMouseListener(new Listener(this));
Font x = new Font("Serif",0,20);
textarea = new Jtextarea();
textarea.setFont(x);
scrollPane = new JScrollPane(textarea);
scrollPane.setBounds(676, 52, 482, 493);
scrollPane.setHorizontalScrollBarPolicy(JScrollPane.HORIZONTAL_SCROLLBAR_ALWAYS);
scrollPane.setVerticalScrollBarPolicy(JScrollPane.VERTICAL_SCROLLBAR_ALWAYS);
scrollPane.setViewportView(textarea);
textarea.setLineWrap(true);
add(scrollPane);
}
@Override
public void paint(Graphics g) {
try {
super.paintComponent(g);
super.paint(g);
// 设置线条颜色（RED为红色）
g.setColor(Color.black);
//绘制水平8个，垂直8个方格。 同时内部64个方格填写数字。
for (int i = 1; i <= 8; i++) {
// 绘制第i条水平线
g.drawLine(0, (w / 8) * i, w, (w / 8) * i);
// 绘制第i条竖直线
g.drawLine((h / 8) * i, 0 , (h / 8) * i, h );
//记录进入数组
x[i-1] = (w / 8) * (i-1)+14;
y[i-1] = (h / 8) * (i-1)+14;
//icon.paintIcon(this, paint, Jpanel.x[i-1], Jpanel.y[i-1]);
}
} catch (Exception e) {
e.printStackTrace();
}
}
}
4.3 鼠标监听器——MouseListener类
Listener类（继承MouseListener类），实现回溯算法解决八皇后问题，并监听鼠标点击事件。在Jpanel类中通过btnNewButton_1.addMouseListener(new Listener(this));与该类联系。
package EightQueen;
import java.awt.Graphics;
import java.awt.event.MouseEvent;
import java.awt.event.MouseListener;
import java.util.linkedList;
import javax.swing.ImageIcon;
import javax.swing.JButton;
public class Listener implements MouseListener {
private Jpanel Panel;//
int height;
private Graphics g;
private static ImageIcon icon = new ImageIcon("src/EightQueen/queen.png");
private Location temp;
private static final int SIZE = 8; // 皇后的个数，此处设为8，表示8个皇后
private static int count = 0; // 记录摆放的方式数
static linkedList list = new linkedList();
public Listener(Jpanel P) {
// TODO Auto-generated constructor stub
Panel = P;
}
public Listener() {
}
static class Location {
int x; // 对应棋盘的列
int y; // 对应棋盘的行
Location(int x, int y) {
this.x = x;
this.y = y;
}
@Override
public String toString() {
return "(" + x + ", " + y + ")";
}
}
private void eightQueen(linkedList list, int x, int y) throws Exception {
if (list.size() == SIZE) { // 当list元素个数为8时，表示8个皇后都摆放完毕
printLocation(list); // 打印皇后摆放方式
return;// 当八个皇后都摆放完毕,我们使用return可以返回之前的栈空间执行剩下的语句
}
for (int i = x; i < SIZE; i++) {
Location loc = new Location(i, y);
if (isLegalLoc(loc)) {
list.offer(loc); // 将第y行的皇后摆放好
icon.paintIcon(Panel, g, Jpanel.x[loc.x], Jpanel.y[loc.y]);
Thread.sleep(15);// 直接抛出异常
eightQueen(list, 0, y + 1); // 开始摆放y+1行的皇后，同样从第0列开始摆放
// 这里我们用到栈的数据结构来实现回溯法,递归到底部然后回溯到保存之前信息的栈空间,然后执行pollLast的语句
temp = list.pollLast(); // 假如总共排放的皇后不能达到8个的话，都要将其撤回，再试探其它的摆法。这就是回溯法
g.clearRect(Jpanel.x[temp.x], Jpanel.y[temp.y], icon.getIconWidth(), icon.getIconHeight());
Thread.sleep(15);
}
}
}
private boolean isLegalLoc(Location loc) {
for (Location each : list) {
if (loc.x == each.x || loc.y == each.y) // 判断是否在同一行或同一列
return false;
else if (Math.abs(loc.x - each.x) == Math.abs(loc.y - each.y)) // 判断是否在同一对角线或反对角线上
return false;
}
return true;
}
private void printLocation(linkedList list) throws InterruptedException {
count++;
StringBuilder str = new StringBuilder("路径" + count + ":");
for (Location each : list) {
System.out.print(each.toString() + "t");
str.append(each.toString());
}
Panel.textarea.append(str.toString() + "rn");
//Panel.textarea.setCaretPosition(Panel.textarea.getText().length());
Panel.textarea.paintImmediately(Panel.textarea.getX(), Panel.textarea.getY(), Panel.textarea.getWidth(),
Panel.textarea.getHeight());
Panel.textarea.setCaretPosition(Panel.textarea.getdocument().getLength());
Panel.invalidate();
System.out.println();
}
@Override
public void mouseClicked(MouseEvent e) {
// TODO Auto-generated method stub
JButton btn = (JButton) (e.getSource());
if (btn.getActionCommand().trim().equals("动态展示")) {
try {
g = Panel.getGraphics();
eightQueen(list, 0, 0);
} catch (Exception e1) {
// TODO Auto-generated catch block
e1.printStackTrace();
}
}
}
@Override
public void mousePressed(MouseEvent e) {
// TODO Auto-generated method stub
}
@Override
public void mouseReleased(MouseEvent e) {
// TODO Auto-generated method stub
}
@Override
public void mouseEntered(MouseEvent e) {
// TODO Auto-generated method stub
}
@Override
public void mouseExited(MouseEvent e) {
// TODO Auto-generated method stub
}
}
4.4 queen.png
4.5 代码结构
5、GUI部分代码解释
5.1 搜索算法模型[再强调一次]
在八皇后问题中我用到栈的数据结构来实现回溯法，递归到底部然后回溯到保存之前信息的栈空间，然后执行pollLast的语句，取出棋子。假如有一行的每一列都放不下符合规范的棋子，那么for循环结束后就会自动返回之前的栈空间；递归中每一层，也就是每次进入一个方法体后我都会创建一个新的栈空间。
这个程序的回溯法巧妙在：每一行中可能有n列是符合条件的，但是如果最终的皇后数不到8的话，我们需要回溯，执行pollLast语句，然后继续之前栈空间的for循环，然后依次类推。一旦我们完成了八个皇后的放置的时候，此时一定是在第八行，我们继续执行for循环直到结束，然后回到上一个递归调用方法的帧栈继续执行for循环；直到棋子的所有摆放情况都已经遍历完了，最终我们的虚拟棋盘会变为空。
这个函数调用了Graphics类，根据我在原界面的设计的长宽，画出8条等间距的竖线和8条等间距的横线。
这个函数的初始化输入是一个初始化的空链表；x=0，y=0分别代表了棋盘的第一个位置。这个函数用到了递归，利用一个for循环对每一行遍历。一旦在该行落子，马上进入下一个递归并在下一行的第0列开始继续搜索合适的落子点并准备进行绘制。一旦从这个函数上一个状态的堆栈退出来，马上取出不合适的落子并在棋盘上清除。
这个函数的输入是一个Location类，该类是Listener类的内部类。通过x，y判断该落子点和存在链表中的“棋子”是否在行、列或者斜线上有冲突。
如果有冲突返回false，反之返回true。
这个函数调用了MouseListener接口，当点击“动态展示”按钮的时候调用方法5.2.2。
在这个函数中我对textarea进行了 *** 作，利用append添加每一条路径。我利用textarea.setCaretPosition(Panel.textarea.getdocument().getLength())函数让光标始终定位在textarea的最后一行。并使用paintImmediately函数动态地刷新文本域。
6、动态展示结果 6.1 八皇后问题运行结束界面 由于八皇后动态运行结束，所以左边的棋盘为空，右边的文本域展示的是回溯法搜索得到的全部92条路径。
此时左边的棋盘打印出了六个棋子，此时回溯法在寻找合适的路径6。
此时左边的棋盘打印出了四个棋子，此时在寻找合适的路径13。
在Listener类中可以通过修改eightQueen函数中的Thread.sleep(15);而修改皇后图标显示的速度。
7、存在的小问题- 代码跑起来后，GUI面板右侧文本域打印出的路径超过17个之后，文本框滚动条没办法往下滑动。运行完，输出92条路径之后才能滑动。
- 没有暂停按钮。
以上问题影响不大，博主随缘更新。
8、创新点- 回溯法解决八皇后问题的过程中，并不需要记录整棵“搜索树”，而只需记录从初始状态到当前状态的一条搜索路径，是“线性链状”的，其最大优点是占用空间少。
- 利用WindowBuider进行八皇后问题的GUI动态演示。利用鼠标监听器MouseListener监听按钮的动作，并用Graphics类进行绘制GUI界面。
- 在进行八皇后问题求解的时候，我使用了链表进行 *** 作。构造了Location类对链表进行 *** 作，在该类中有棋子的x和y坐标的属性，并重写了toString(该方法在testArea中打印一个合适的被放置的棋子的具体位置)。当有合适棋子放置的时候调用offer方法，要移除棋子的时候调用pollLast方法。
- 使用ImageIcon 加载棋子 的图片，并调用该类的paintIcon方法绘制图片，调用Graphics类的clearRect方法清除图片。
本篇博文的教程应该是八皇后问题的集大成之作了，我抽空将大二95分的人工智能导论的报告之一整理成了博文。有问题欢迎评论，我会虚心接受。希望大家能多多点赞、关注、收藏，你的支持是对我持续创作的帮助！
严正申明：转载请联系博主，不允许盗用!
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）