N皇后问题——JAVA实现(源代码).doc

2011/2012学年第2学期“算法分析与设计”上机报告学院系信息工程学院计算机科学系专业计算机科学与技术班级项目名称N皇后问题组长小组成员目录1.问题描述.32.算法分析.33.伪代码.44.演示程序设计.55.演示界面.56.算法实现.87.总结.198.参考文献. 201. 问题描述：N皇后问题（n-queen problem）是一个经典的组合优化问题，也是一个使用回溯法（backtracking）的典型例子。回溯法是一种系统地搜索问题解的方法。为了实现回溯，首先需要为为问题定义一个解空间（solution space）,其至少包含问题的一个解（可能是最优解）。我们要从中找出满足问题约束条件的解，即可行解（feasible solution）。回溯算法一次扩展一个解，在对部分解进行扩展后，检查到目前为止的解是否为问题的一个解，如果是，则输出；否则，检查是否可以继续扩展。如果可以，则继续扩展；否则，删除最后添加的元素，尝试当前位置是否有另一元素。若没有合法的扩展方式，则进行回溯（backtrack）。N皇后问题要求在一个nn的棋盘上放置n个皇后，且使得每两个皇后之间都不能相互攻击，即它们中的任意两个都不能位于同一行、同一列或者同一对角线上。这次的任务就是借助GUI实现N皇后问题的动态演示。我们设定皇后个数在四个到八个之间可选，所选编程语言为JAVA。2. 算法分析：N皇后问题是回溯法的一个经典例子，它的要求就是要找出在nn的棋盘上放置n个皇后并使其不能相互攻击的所有解。设X=(x1,x2,，xn)表示问题的解，其中xi表示第i皇后放在第i行所在的列数。由于不存在两个皇后位于同一列上，因此xi互不相同。设有两个皇后分别位于棋盘( i , j )和( k , l )处，如果两个皇后位于同一对角线上，则表明它们所在的位置应该满足：i j = k l或i + j = k + l。综合这两个等式可得，如果两个皇后位于同一对角线上，那么它们的位置关系一定满足| j l | = | i k |。这是对皇后位置的合法性的判定，由函数PLACE来完成。N-QUEEN函数功能是求出N皇后问题的所有解。它在循环体中计算xk的值，并对每一个xk的值，调用PLACE过程测试它的合法性，即寻找满足约束条件的xk的值。如果找到了一个合法的放置位置，就进一步测试求得的(x1,x2,xk)是否为问题的解。如果是，就将其输出；否则，就将k的值增加1继续循环，即继续寻找下一个皇后合法的位置。如果不存在合法的xk值，就将k的值减1进行回溯。3. 伪代码：N-QUEEN(n)1 x1 0 /第一个皇后的列位置初始化2 k 1 /当前列3 while k 0 do4 xk xk+1 /到下一列5 while xkn not PLACE(k) do6 xk xk+17 if xkn /找到一个位置8 then if k=n /测试是否为问题的解9 then output(X) /输出解10 else k k+1 /转下一行，即给下一个皇后找位置11 x1 0 /初始化当前皇后列取值12 else k k-1 /回溯13 returnPLACE(k)1 i 12 while ik do3 if (xi=xk or abs(xi-xk)=abs(i-k) /同一列或同一对角线有 /两个皇后4 then return (false)5 i i+16 return(true)4. 演示程序设计： 逐个输出所有的解选择皇后个数 调用N皇后问题算法 显示解的个数 控制 功能按钮 动态演示皇后的布局5. 演示界面（1） 初始界面（2） 示例界面（例如选择8个皇后时）界面功能介绍： 1. 单选选项：选择皇后的个数，限定选择4个到8个之间； 2. 小文本框：输出相应皇后个数的解的个数； 3. 大文本域：逐个输出相应皇后个数的所有解；4. 中间区域：显示相应皇后个数的棋盘和可行的皇后布局； 5. “开始演示”按钮：点击开始执行演示过程； 6. “暂停”按钮：点击暂停演示过程，再次点击“开始演示”按钮继续演示过程； 7. “清空”按钮：点击把3中的内容清空； 8. 滑动条：拖动滑块可以在任意时刻调整演示速度。（3） 选择其它皇后个数时1. 4个2. 5个3. 6个4. 7个6. 算法实现： import java.applet.Applet;import java.awt.BorderLayout;import java.awt.Color;import java.awt.Container;import java.awt.Graphics;import java.awt.Graphics2D;import java.awt.GridLayout;import java.awt.TextArea;import java.awt.Toolkit;import java.awt.event.ActionEvent;import java.awt.event.ActionListener;import java.awt.event.ItemEvent;import java.awt.event.ItemListener;import java.awt.event.WindowAdapter;import java.awt.event.WindowEvent;import java.util.Hashtable;import javax.swing.BorderFactory;import javax.swing.ButtonGroup;import javax.swing.JButton;import javax.swing.JFrame;import javax.swing.JLabel;import javax.swing.JPanel;import javax.swing.JRadioButton;import javax.swing.JScrollPane;import javax.swing.JSlider;import javax.swing.JTextField;import javax.swing.event.ChangeEvent;import javax.swing.event.ChangeListener;public class NQueen implements ItemListener,ActionListener,ChangeListenerJFrame f=new JFrame(N QUEEN PROBLEM DEMO);Container cp=f.getContentPane();int x=new int10;int X=new int1000010;String str=new String10000;int m=4,a=1,b=1,counter=0,j=1;Panel4 panel4=new Panel4();TextArea t1=new TextArea(30,40);JTextField t2=new JTextField(10);JRadioButton r1=new JRadioButton(4个); JRadioButton r2=new JRadioButton(5个); JRadioButton r3=new JRadioButton(6个); JRadioButton r4=new JRadioButton(7个); JRadioButton r5=new JRadioButton(8个); JButton button1=new JButton(开始演示); JButton button2=new JButton(暂停); JButton button3=new JButton(清空); JSlider slider1=new JSlider(20,100);javax.swing.Timer timer1;/窗口的布局/public NQueen()cp.setLayout(new BorderLayout(20,20);t2.setBorder(BorderFactory.createTitledBorder(解的个数：);JScrollPane scrollPane1=new JScrollPane(t1);scrollPane1.setBorder(BorderFactory.createTitledBorder(展示所有解：);JPanel panel1=new JPanel();panel1.setLayout(new GridLayout(2,1,10,20);JPanel panel2=new JPanel();panel2.setLayout(new GridLayout(6,1);panel2.setBorder(BorderFactory.createTitledBorder(请选择皇后的个数：); JPanel panel3=new JPanel(); panel3.setLayout(new GridLayout(4,1,10,10); r1.addItemListener(this); r2.addItemListener(this); r3.addItemListener(this); r4.addItemListener(this); r5.addItemListener(this); button1.addActionListener(this); button2.addActionListener(this); button3.addActionListener(this); slider1.setPaintTicks(true);slider1.setMajorTickSpacing(40);slider1.setMinorTickSpacing(20);slider1.setPaintLabels(true);slider1.setPaintTrack(true);slider1.setSnapToTicks(true);slider1.addChangeListener(this);slider1.setBorder(BorderFactory.createTitledBorder(调节演示的速度);timer1=new javax.swing.Timer(slider1.getValue()*25,this);Hashtable table=new Hashtable();table.put(new Integer(20), new JLabel(快);table.put(new Integer(100), new JLabel(慢);slider1.setLabelTable(table); ButtonGroup buttong1=new ButtonGroup(); buttong1.add(r1); buttong1.add(r2); buttong1.add(r3); buttong1.add(r4); buttong1.add(r5); panel1.add(panel2); panel1.add(panel3); panel2.add(r1); panel2.add(r2); panel2.add(r3); panel2.add(r4); panel2.add(r5); panel2.add(t2); panel3.add(button1); panel3.add(button2); panel3.add(button3); panel3.add(slider1); cp.add(panel1,BorderLayout.WEST); cp.add(panel4,BorderLayout.CENTER); cp.add(scrollPane1,BorderLayout.EAST); f.setSize(865,600);f.setVisible(true);f.addWindowListener(new WindowAdapter()public void windowClosing(WindowEvent e)System.exit(0);); /N皇后算法/public void nqueen(int n)int k;x1=0;k=1;for(int i=0;i0&k=n)xk=xk+1;while(xk=n & place(k)=false)xk=xk+1;if(xk=n)if(k=n)counter+;for(int i=1;i=n;i+)Xai=xi;stra=stra+xi+,;a+;System.out.print(n);elsek=k+1;xk=0;elsek=k-1;return;/判断皇后位置的合法性/public boolean place(int b)int k=b,i=1;while(ik)if(xi=xk | Math.abs(xi-xk)=Math.abs(i-k)return(false);i=i+1;return(true);/主方法/* * param args */public static void main(String args)new NQueen();/ TODO Auto-generated method stub/画棋盘和皇后的位置/SuppressWarnings(serial)public class Panel4 extends Appletpublic void paint(Graphics g)super.paint(g);Graphics2D g2=(Graphics2D)g;g2.setColor(Color.white);g2.fillRect(0,0,500,600);g.setColor(Color.black);for (int i=0; i=m; i+) g2.drawLine(i*(240/m)+20,20, i*(240/m)+20,260); g2.drawLine(20, i*(240/m)+20, 260, i*(240/m)+20); g2.setColor(Color.blue);for(int i=1;i=m;i+)g2.drawString(Q,30+(Xji-1)*(240/m),10+i*(240/m);/皇后个数的选择/SuppressWarnings(static-access)Overridepublic void itemStateChanged(ItemEvent e)if(e.getStateChange()=e.SELECTED)if(e.getSource()=r1)m=4;a=1;b=1;j=1;counter=0;nqueen(m);t2.setText(+counter);panel4.repaint();System.out.print(m);if(e.getSource()=r2)m=5;a=1;b=1;j=1;counter=0;nqueen(m);t2.setText(+counter);panel4.repaint();System.out.print(m);if(e.getSource()=r3)m=6;a=1;b=1;j=1;counter=0;nqueen(m);t2.setText(+counter);panel4.repaint();System.out.print(m);if(e.getSource()=r4)m=7;a=1;b=1;j=1;counter=0;nqueen(m);t2.setText(+counter);panel4.repaint();System.out.print(m);if(e.getSource()=r5)m=8;a=1;b=1;j=1;counter=0;nqueen(m);t2.setText(+counter);panel4.repaint();System.out.print(m);/ TODO Auto-generated method stub/按钮功能的实现/Overridepublic void actionPerformed(ActionEvent e) if(e.getSource()=button1)j=0;timer1.start();Toolkit.getDefaultToolkit().beep();if(e.getSource()=button2)timer1.stop();Toolkit.getDefaultToolkit().beep();if(e.getSource()=button3)timer1.stop();t1.setText();b=1;Toolkit.getDefaultToolkit().beep();if(e.getSource()=timer1)t1.append(strb);t1.append(n);panel4.repaint();j+;b+;if(b=counter+1)timer1.stop();Toolkit.getDefaultToolkit().beep();/ TODO Auto-generated method stub/用滑块控制Timer的时间间隔/public void stateChanged(ChangeEvent e)timer1.setDelay(slider1.getValue()*25);7. 总结：我们将实现N皇后问题动态演示的程序大体上主要分了三个部分，一是N皇后问题算法的实现；二是程序界面的设计及界面功能的实现；三是做到算法实现过程的动态演示。其中N皇后问题算法的实现是首要的任务，只有算法本身得到了实现，下面将其进行动态演示的部分才能继续。老师在课堂上对N皇后问题有过的讲解，再经过我们课后的上机实际操作，在较短的时间内我们就对快速排序算法本身有了较为准确和深刻的认识，并将其用JAVA语言进行了实现。第二和第三部分同样是需要我们重点攻克的内容，要做好界面的设计及界面功能的实现，需要我们了解界面的布局方法、各种组件的特点及功能、功能实现怎么与算法相契合等；要做到算法实现过程的动态演示，我们必须能熟练地使用JAVA中的画图工具及对多线程