N皇后问题JAVA实现源代码.docx

1、N皇后问题JAVA实现源代码2011/2012学年第2学期“算法分析与设计”上机报告学院系信息工程学院计算机科学系专业计算机科学与技术班级项目名称N皇后问题组长小组成员1. 问题描述.32. 算法分析.33. 伪代码.44. 演示程序设计.55. 演示界面.56. 算法实现.87. 总结.198. 参考文献. 201.问题描述：N皇后问题（n-queen problem）是一个经典的组合优化问题，也是一个使用回溯法（backtracking）的典型例子。回溯法是一种系统地搜索问题解的方法。为了实现回溯，首先需要为为问题定义一个解空间（solution space）,其至少包含问题的一个解（可能

2、是最优解）。我们要从中找出满足问题约束条件的解，即可行解（feasible solution）。回溯算法一次扩展一个解，在对部分解进行扩展后，检查到目前为止的解是否为问题的一个解，如果是，则输出；否则，检查是否可以继续扩展。如果可以，则继续扩展；否则，删除最后添加的元素，尝试当前位置是否有另一元素。若没有合法的扩展方式，则进行回溯（backtrack）。N皇后问题要求在一个nn的棋盘上放置n个皇后，且使得每两个皇后之间都不能相互攻击，即它们中的任意两个都不能位于同一行、同一列或者同一对角线上。这次的任务就是借助GUI实现N皇后问题的动态演示。我们设定皇后个数在四个到八个之间可选，所选编程语言为

3、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来完

4、成。N-QUEEN函数功能是求出N皇后问题的所有解。它在循环体中计算xk的值，并对每一个xk的值，调用PLACE过程测试它的合法性，即寻找满足约束条件的xk的值。如果找到了一个合法的放置位置，就进一步测试求得的(x1,x2,xk)是否为问题的解。如果是，就将其输出；否则，就将k的值增加1继续循环，即继续寻找下一个皇后合法的位置。如果不存在合法的xk值，就将k的值减1进行回溯。3.伪代码：N-QUEEN(n)1x1 0 /第一个皇后的列位置初始化2k 1 /当前列3while k 0 do4 xk xk+1 /到下一列5 while xkn not PLACE(k) do6 xk xk+17 i

5、f 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)1i 12while ik do3 if (xi=xk or abs(xi-xk)=abs(i-k) /同一列或同一对角线有 /两个皇后4 then return (false)5 i i+16 return(true)4.演示程序设计： 逐个输出所有的解选择皇后个数 调用N皇后问题算法 显示解的个数 控制 功能按钮

6、 动态演示皇后的布局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.算法实

7、现： 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.ActionList

8、ener;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.s

9、wing.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,Change

10、Listener JFrame 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 JR

11、adioButton(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,

12、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

13、(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(t

14、his); 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.setPaintTr

15、ack(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

16、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.ad

17、d(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 windowCl

18、osing(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); else k=k+1; xk=0; else k=k-1; return; /判断皇后位置

19、的合法性/ 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

20、 extends Applet public 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

21、(Color.blue); for(int i=1;i=m;i+) g2.drawString(Q,30+(Xji-1)*(240/m),10+i*(240/m); /皇后个数的选择/ SuppressWarnings(static-access) Override public 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.r

22、epaint(); 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

23、=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 /按钮功能的实现/ Override public void actionPerformed(ActionEvent e) if(e.getSource()=button1) j=0; timer1.start(); Toolkit.getDefaultToolkit().beep(); if(e.getSource()=button2) timer1.stop(); To