N皇后JAVA.docx
《N皇后JAVA.docx》由会员分享,可在线阅读,更多相关《N皇后JAVA.docx(21页珍藏版)》请在冰点文库上搜索。
N皇后问题实验报告
学院/系
信息工程系
专业
网络工程
班级
08K1
项目名称
N皇后问题
组长
Meter
小组成员
时间
2011-11-11
目录
1.问题描述 3
2.算法分析 3
3.伪代码 4
4.演示程序设计 5
5.演示界面 5
6.算法实现 8
7. 总结 19
8. 参考文献 20
1.问题描述:
N皇后问题(n-queenproblem)是一个经典的组合优化问题,也是一个使用回溯法(backtracking)的典型例子。
回溯法是一种系统地搜索问题解的方法。
为了实现回溯,首先需要为为问题定义一个解空间(solution
space),其至少包含问题的一个解(可能是最优解)。
我们要从中找出满足问题约束条件的解,即可行解(feasible solution)。
回溯算法一次扩展一个解,在对部分解进行扩展后,检查到目前为止的解是否为问题的一个解,如果是,则输出;否则,检查是否可以继续扩展。
如果可以,则继续扩展;否则,删除最后添加的元素,尝试当前位置是否有另一元素。
若没有合法的扩展方式,则进行回溯(backtrack)。
N皇后问题要求在一个n×n的棋盘上放置n个皇后,且使得每两个皇后之间都不能相互攻击,即它们中的任意两个都不能位于同一行、同一列或者同一对角线上。
这次的任务就是借助GUI实现N皇后问题的动态演示。
我们设定皇后个数在四个到八个之间可选,所选编程语言为JAVA。
2.算法分析:
N皇后问题是回溯法的一个经典例子,它的要求就是要找出在n×n的棋盘上放置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)
1x[1]←0 //第一个皇后的列位置初始化
2k←1 //当前列
3while k>0 do
4 x[k]←x[k]+1 //到下一列
5 while x[k]≤n&not PLACE(k) do6 x[k]←x[k]+1
7if x[k]≤n //找到一个位置
8then if k=n //测试是否为问题的解
9then output(X) //输出解
10else k←k+1 //转下一行,即给下一个皇后找位置
11x[1]←0 //初始化当前皇后列取值
12else k←k-1 //回溯
13return
PLACE(k)
1 i←1
2while i3if (x[i]=x[k]orabs(x[i]-x[k])=abs(i-k)) //同一列或同一对角线有//两个皇后4thenreturn(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.算法实现:importjava.applet.Applet;importjava.awt.BorderLayout;importjava.awt.Color;importjava.awt.Container;importjava.awt.Graphics;importjava.awt.Graphics2D;importjava.awt.GridLayout;importjava.awt.TextArea;importjava.awt.Toolkit;importjava.awt.event.ActionEvent;importjava.awt.event.ActionListener;importjava.awt.event.ItemEvent;importjava.awt.event.ItemListener;importjava.awt.event.WindowAdapter;importjava.awt.event.WindowEvent;importjava.util.Hashtable;importjavax.swing.BorderFactory;importjavax.swing.ButtonGroup;importjavax.swing.JButton;importjavax.swing.JFrame;importjavax.swing.JLabel;importjavax.swing.JPanel;importjavax.swing.JRadioButton;importjavax.swing.JScrollPane;importjavax.swing.JSlider;importjavax.swing.JTextField;importjavax.swing.event.ChangeEvent;importjavax.swing.event.ChangeListener;publicclassNQueenimplementsItemListener,ActionListener,ChangeListener{JFramef=newJFrame("NQUEENPROBLEMDEMO");Containercp=f.getContentPane();int[]x=newint[10];int[][]X=newint[10000][10];String[]str=newString[10000];intm=4,a=1,b=1,counter=0,j=1;Panel4panel4=newPanel4();TextAreat1=newTextArea(30,40);JTextFieldt2=newJTextField(10);JRadioButtonr1=newJRadioButton("4个");JRadioButtonr2=newJRadioButton("5个");JRadioButtonr3=newJRadioButton("6个");JRadioButtonr4=newJRadioButton("7个");JRadioButtonr5=newJRadioButton("8个");JButtonbutton1=newJButton("开始演示");JButtonbutton2=newJButton("暂停");JButtonbutton3=newJButton("清空");JSliderslider1=newJSlider(20,100);javax.swing.Timertimer1;/////////////////////////////////////////////窗口的布局//////////////////////////////////////publicNQueen(){cp.setLayout(newBorderLayout(20,20));"));t2.setBorder(BorderFactory.createTitledBorder("解的个数:JScrollPanescrollPane1=newJScrollPane(t1);scrollPane1.setBorder(BorderFactory.createTitledBorder("展示所有解:"));JPanelpanel1=newJPanel();panel1.setLayout(newGridLayout(2,1,10,20));JPanelpanel2=newJPanel();panel2.setLayout(newGridLayout(6,1));panel2.setBorder(BorderFactory.createTitledBorder("请选择皇后的个数:"));JPanelpanel3=newJPanel();panel3.setLayout(newGridLayout(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=newjavax.swing.Timer(slider1.getValue()*25,this);Hashtabletable=newHashtableJLabel>();table.put(newInteger(20),newJLabel("快"));table.put(newInteger(100),newJLabel("慢"));slider1.setLabelTable(table);ButtonGroupbuttong1=newButtonGroup();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(newWindowAdapter(){publicvoidwindowClosing(WindowEvente){System.exit(0);}});}////////////////////////////////////N皇后算法/////////////////////////////////////////////publicvoidnqueen(intn){intk;x[1]=0;k=1;for(inti=0;i<10000;i++){str[i]="";}while(k>0&&k<=n){x[k]=x[k]+1;while(x[k]<=n&&place(k)==false){x[k]=x[k]+1;}if(x[k]<=n)if(k==n){counter++;for(inti=1;i<=n;i++){X[a][i]=x[i];str[a]=str[a]+x[i]+",";}a++;System.out.print("\n");}else{}elsek=k+1;x[k]=0;k=k-1;}return;}///////////////////////判断皇后位置的合法性///////////////////publicbooleanplace(intb){intk=b,i=1;while(i{if(x[i]==x[k]||Math.abs(x[i]-x[k])==Math.abs(i-k))return(false);i=i+1;}return(true);}//////////////////////////////////////主方法///////////////////////////////////////////////***@paramargs*/publicstaticvoidmain(String[]args){new NQueen();//TODOAuto-generatedmethodstub}////////////////////////////////////////画棋盘和皇后的位置///////////////////////////////////////@SuppressWarnings("serial")publicclassPanel4extendsApplet{publicvoidpaint(Graphicsg){super.paint(g);Graphics2Dg2=(Graphics2D)g;g2.setColor(Color.white);g2.fillRect(0,0,500,600);g.setColor(Color.black);for(inti=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(inti=1;i<=m;i++){g2.drawString("Q",30+(X[j][i]-1)*(240/m),10+i*(240/m));}}}//////////////////////////////////////////////皇后个数的选择//////////////////////////////////////////@SuppressWarnings("static-access")@OverridepublicvoiditemStateChanged(ItemEvente){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);}}//TODOAuto-generatedmethodstub}/////////////////////////////////////////////////按钮功能的实现/////////////////////////////////////////////@OverridepublicvoidactionPerformed(ActionEvente){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(str[b]);t1.append("\n");panel4.repaint();j++;b++;if(b==counter+1)timer1.stop();Toolkit.getDefaultToolkit().beep();}//TODOAuto-generatedmethodstub}//////////////////////////////////////////////用滑块控制Timer的时间间隔////////////////////////////////////////publicvoidstateChanged(ChangeEvente){timer1.setDelay(slider1.getValue()*25);}}7.总结:我们将实现N皇后问题动态演示的程序大体上主要分了三个部分,一是N皇后问题算法的实现;二是程序界面的设计及界面功能的实现;三是做到算法实现过程的动态演示。其中N皇后问题算法的实现是首要的任务,只有算法本身得到了实现,下面将其进行动态演示的部分才能继续。老师在课堂上对N皇后问题有过的讲解,再经过我们课后的上机实际操作,在较短的时间内我们就对快速排序算法本身有了较为准确和深刻的认识,并将其用JAVA语言进行了实现。第二和第三部分同样是需要我们重点攻克的内容,要做好界面的设计及界面功能的实现,需要我们了解界面的布局方法、各种组件的特点及功能、功能实现怎么与算法相契合等;要做到算法实现过程的动态演示,我们必须能熟练地使用JAVA中的画图工具及对多线程有很好的了解等。虽然有这么一系列的问题摆在我们面前,但有了之前完成快速排序题目的知识积累,我们很快就有了解决的思路。为了能够更好的完成这次的程序设计,我们把所需的相关书籍等资料重新搜集过来,进行更加深入的学习,来完善我们在相关方面的知识。在将从图书馆借阅的书籍翻阅过后,我们大家决定集思广益,再次在一起分析了这个题目,大家经过认真地商讨后最终确定了这次程序编写的整体规划和较为详细的合作分工。在共同合作编写程序的过程当中,我们在自己负责的部分当中都或多或少的遇到了较为棘手的问题。例如:在棋牌上绘制皇后时不知怎么才能不把原先绘制的棋盘覆盖掉;显示解的个数时,计数器总是进行累计却不知为何;不知为什么在进行动态演示时皇后会在棋盘外等等。但是我们经过仔细地重新研究程序后,这出现这一系列问题的原因都被
3if (x[i]=x[k]orabs(x[i]-x[k])=abs(i-k)) //同一列或同一对角线有
//两个皇后
4thenreturn(false)
5 i←i+1
6 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.算法实现:
importjava.applet.Applet;importjava.awt.BorderLayout;importjava.awt.Color;
importjava.awt.Container;importjava.awt.Graphics;importjava.awt.Graphics2D;importjava.awt.GridLayout;importjava.awt.TextArea;importjava.awt.Toolkit;
importjava.awt.event.ActionEvent;importjava.awt.event.ActionListener;importjava.awt.event.ItemEvent;importjava.awt.event.ItemListener;importjava.awt.event.WindowAdapter;importjava.awt.event.WindowEvent;importjava.util.Hashtable;
importjavax.swing.BorderFactory;importjavax.swing.ButtonGroup;importjavax.swing.JButton;importjavax.swing.JFrame;
importjavax.swing.JLabel;
importjavax.swing.JPanel;importjavax.swing.JRadioButton;importjavax.swing.JScrollPane;importjavax.swing.JSlider;importjavax.swing.JTextField;
importjavax.swing.event.ChangeEvent;
importjavax.swing.event.ChangeListener;
publicclassNQueenimplements
ItemListener,ActionListener,ChangeListener
{
JFramef=newJFrame("NQUEENPROBLEMDEMO");Containercp=f.getContentPane();
int[]x=newint[10];
int[][]X=newint[10000][10];String[]str=newString[10000];intm=4,a=1,b=1,counter=0,j=1;
Panel4panel4=newPanel4();
TextAreat1=newTextArea(30,40);JTextFieldt2=newJTextField(10);
JRadioButtonr1=newJRadioButton("4个");JRadioButtonr2=newJRadioButton("5个");JRadioButtonr3=newJRadioButton("6个");JRadioButtonr4=newJRadioButton("7个");JRadioButtonr5=newJRadioButton("8个");
JButtonbutton1=newJButton("开始演示");JButtonbutton2=newJButton("暂停");JButtonbutton3=newJButton("清空");
JSliderslider1=newJSlider(20,100);
javax.swing.Timertimer1;
/////////////////////////////////////////////窗口的布局
//////////////////////////////////////
publicNQueen()
cp.setLayout(newBorderLayout(20,20));
"));
t2.setBorder(BorderFactory.createTitledBorder("解的个数:
JScrollPanescrollPane1=newJScrollPane(t1);scrollPane1.setBorder(BorderFactory.createTitledBorder("
展示所有解:
JPanelpanel1=newJPanel();panel1.setLayout(newGridLayout(2,1,10,20));JPanelpanel2=newJPanel();panel2.setLayout(newGridLayout(6,1));
panel2.setBorder(BorderFactory.createTitledBorder("请选择皇后的个数:
JPanelpanel3=newJPanel();panel3.setLayout(newGridLayout(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=newjavax.swing.Timer(slider1.getValue()*25,this);Hashtabletable=newHashtableJLabel>();table.put(newInteger(20),newJLabel("快"));table.put(newInteger(100),newJLabel("慢"));slider1.setLabelTable(table);ButtonGroupbuttong1=newButtonGroup();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(newWindowAdapter(){publicvoidwindowClosing(WindowEvente){System.exit(0);}});}////////////////////////////////////N皇后算法/////////////////////////////////////////////publicvoidnqueen(intn){intk;x[1]=0;k=1;for(inti=0;i<10000;i++){str[i]="";}while(k>0&&k<=n){x[k]=x[k]+1;while(x[k]<=n&&place(k)==false){x[k]=x[k]+1;}if(x[k]<=n)if(k==n){counter++;for(inti=1;i<=n;i++){X[a][i]=x[i];str[a]=str[a]+x[i]+",";}a++;System.out.print("\n");}else{}elsek=k+1;x[k]=0;k=k-1;}return;}///////////////////////判断皇后位置的合法性///////////////////publicbooleanplace(intb){intk=b,i=1;while(i{if(x[i]==x[k]||Math.abs(x[i]-x[k])==Math.abs(i-k))return(false);i=i+1;}return(true);}//////////////////////////////////////主方法///////////////////////////////////////////////***@paramargs*/publicstaticvoidmain(String[]args){new NQueen();//TODOAuto-generatedmethodstub}////////////////////////////////////////画棋盘和皇后的位置///////////////////////////////////////@SuppressWarnings("serial")publicclassPanel4extendsApplet{publicvoidpaint(Graphicsg){super.paint(g);Graphics2Dg2=(Graphics2D)g;g2.setColor(Color.white);g2.fillRect(0,0,500,600);g.setColor(Color.black);for(inti=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(inti=1;i<=m;i++){g2.drawString("Q",30+(X[j][i]-1)*(240/m),10+i*(240/m));}}}//////////////////////////////////////////////皇后个数的选择//////////////////////////////////////////@SuppressWarnings("static-access")@OverridepublicvoiditemStateChanged(ItemEvente){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);}}//TODOAuto-generatedmethodstub}/////////////////////////////////////////////////按钮功能的实现/////////////////////////////////////////////@OverridepublicvoidactionPerformed(ActionEvente){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(str[b]);t1.append("\n");panel4.repaint();j++;b++;if(b==counter+1)timer1.stop();Toolkit.getDefaultToolkit().beep();}//TODOAuto-generatedmethodstub}//////////////////////////////////////////////用滑块控制Timer的时间间隔////////////////////////////////////////publicvoidstateChanged(ChangeEvente){timer1.setDelay(slider1.getValue()*25);}}7.总结:我们将实现N皇后问题动态演示的程序大体上主要分了三个部分,一是N皇后问题算法的实现;二是程序界面的设计及界面功能的实现;三是做到算法实现过程的动态演示。其中N皇后问题算法的实现是首要的任务,只有算法本身得到了实现,下面将其进行动态演示的部分才能继续。老师在课堂上对N皇后问题有过的讲解,再经过我们课后的上机实际操作,在较短的时间内我们就对快速排序算法本身有了较为准确和深刻的认识,并将其用JAVA语言进行了实现。第二和第三部分同样是需要我们重点攻克的内容,要做好界面的设计及界面功能的实现,需要我们了解界面的布局方法、各种组件的特点及功能、功能实现怎么与算法相契合等;要做到算法实现过程的动态演示,我们必须能熟练地使用JAVA中的画图工具及对多线程有很好的了解等。虽然有这么一系列的问题摆在我们面前,但有了之前完成快速排序题目的知识积累,我们很快就有了解决的思路。为了能够更好的完成这次的程序设计,我们把所需的相关书籍等资料重新搜集过来,进行更加深入的学习,来完善我们在相关方面的知识。在将从图书馆借阅的书籍翻阅过后,我们大家决定集思广益,再次在一起分析了这个题目,大家经过认真地商讨后最终确定了这次程序编写的整体规划和较为详细的合作分工。在共同合作编写程序的过程当中,我们在自己负责的部分当中都或多或少的遇到了较为棘手的问题。例如:在棋牌上绘制皇后时不知怎么才能不把原先绘制的棋盘覆盖掉;显示解的个数时,计数器总是进行累计却不知为何;不知为什么在进行动态演示时皇后会在棋盘外等等。但是我们经过仔细地重新研究程序后,这出现这一系列问题的原因都被
JLabel>();
table.put(newInteger(20),newJLabel("快"));table.put(newInteger(100),newJLabel("慢"));slider1.setLabelTable(table);
ButtonGroupbuttong1=newButtonGroup();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(newWindowAdapter(){
publicvoidwindowClosing(WindowEvente){System.exit(0);
}
});
////////////////////////////////////N皇后算法
/////////////////////////////////////////////
publicvoidnqueen(intn)
intk;x[1]=0;k=1;
for(inti=0;i<10000;i++)
str[i]="";
while(k>0&&k<=n)
x[k]=x[k]+1;
while(x[k]<=n&&place(k)==false)
if(x[k]<=n)if(k==n)
counter++;
for(inti=1;i<=n;i++)
X[a][i]=x[i];str[a]=str[a]+x[i]+",";
a++;
System.out.print("\n");
else
k=k+1;x[k]=0;
k=k-1;
return;
///////////////////////判断皇后位置的合法性///////////////////
publicbooleanplace(intb)
intk=b,i=1;
while(i{if(x[i]==x[k]||Math.abs(x[i]-x[k])==Math.abs(i-k))return(false);i=i+1;}return(true);}//////////////////////////////////////主方法///////////////////////////////////////////////***@paramargs*/publicstaticvoidmain(String[]args){new NQueen();//TODOAuto-generatedmethodstub}////////////////////////////////////////画棋盘和皇后的位置///////////////////////////////////////@SuppressWarnings("serial")publicclassPanel4extendsApplet{publicvoidpaint(Graphicsg){super.paint(g);Graphics2Dg2=(Graphics2D)g;g2.setColor(Color.white);g2.fillRect(0,0,500,600);g.setColor(Color.black);for(inti=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(inti=1;i<=m;i++){g2.drawString("Q",30+(X[j][i]-1)*(240/m),10+i*(240/m));}}}//////////////////////////////////////////////皇后个数的选择//////////////////////////////////////////@SuppressWarnings("static-access")@OverridepublicvoiditemStateChanged(ItemEvente){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);}}//TODOAuto-generatedmethodstub}/////////////////////////////////////////////////按钮功能的实现/////////////////////////////////////////////@OverridepublicvoidactionPerformed(ActionEvente){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(str[b]);t1.append("\n");panel4.repaint();j++;b++;if(b==counter+1)timer1.stop();Toolkit.getDefaultToolkit().beep();}//TODOAuto-generatedmethodstub}//////////////////////////////////////////////用滑块控制Timer的时间间隔////////////////////////////////////////publicvoidstateChanged(ChangeEvente){timer1.setDelay(slider1.getValue()*25);}}7.总结:我们将实现N皇后问题动态演示的程序大体上主要分了三个部分,一是N皇后问题算法的实现;二是程序界面的设计及界面功能的实现;三是做到算法实现过程的动态演示。其中N皇后问题算法的实现是首要的任务,只有算法本身得到了实现,下面将其进行动态演示的部分才能继续。老师在课堂上对N皇后问题有过的讲解,再经过我们课后的上机实际操作,在较短的时间内我们就对快速排序算法本身有了较为准确和深刻的认识,并将其用JAVA语言进行了实现。第二和第三部分同样是需要我们重点攻克的内容,要做好界面的设计及界面功能的实现,需要我们了解界面的布局方法、各种组件的特点及功能、功能实现怎么与算法相契合等;要做到算法实现过程的动态演示,我们必须能熟练地使用JAVA中的画图工具及对多线程有很好的了解等。虽然有这么一系列的问题摆在我们面前,但有了之前完成快速排序题目的知识积累,我们很快就有了解决的思路。为了能够更好的完成这次的程序设计,我们把所需的相关书籍等资料重新搜集过来,进行更加深入的学习,来完善我们在相关方面的知识。在将从图书馆借阅的书籍翻阅过后,我们大家决定集思广益,再次在一起分析了这个题目,大家经过认真地商讨后最终确定了这次程序编写的整体规划和较为详细的合作分工。在共同合作编写程序的过程当中,我们在自己负责的部分当中都或多或少的遇到了较为棘手的问题。例如:在棋牌上绘制皇后时不知怎么才能不把原先绘制的棋盘覆盖掉;显示解的个数时,计数器总是进行累计却不知为何;不知为什么在进行动态演示时皇后会在棋盘外等等。但是我们经过仔细地重新研究程序后,这出现这一系列问题的原因都被
if(x[i]==x[k]||Math.abs(x[i]-x[k])==Math.abs(i-k))
return(false);i=i+1;
return(true);
//////////////////////////////////////主方法
//////////////////////////////////////////////
/**
*@paramargs
*/
publicstaticvoidmain(String[]args)
new NQueen();
//TODOAuto-generatedmethodstub
////////////////////////////////////////画棋盘和皇后的位置
///////////////////////////////////////@SuppressWarnings("serial")
publicclassPanel4extendsApplet
publicvoidpaint(Graphicsg)
super.paint(g);
Graphics2Dg2=(Graphics2D)g;g2.setColor(Color.white);g2.fillRect(0,0,500,600);g.setColor(Color.black);
for(inti=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(inti=1;i<=m;i++)
g2.drawString("Q",30+(X[j][i]-
1)*(240/m),10+i*(240/m));
//////////////////////////////////////////////皇后个数的选择
//////////////////////////////////////////@SuppressWarnings("static-access")@Override
publicvoiditemStateChanged(ItemEvente)
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;
if(e.getSource()==r3)
m=6;
if(e.getSource()==r4)
m=7;
if(e.getSource()==r5)
m=8;
/////////////////////////////////////////////////按钮功能的实现
/////////////////////////////////////////////@Override
publicvoidactionPerformed(ActionEvente)
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(str[b]);
t1.append("\n");panel4.repaint();
j++;b++;
if(b==counter+1)timer1.stop();
//////////////////////////////////////////////用滑块控制Timer的时间间隔////////////////////////////////////////
publicvoidstateChanged(ChangeEvente)
timer1.setDelay(slider1.getValue()*25);
7.总结:
我们将实现N皇后问题动态演示的程序大体上主要分了三个部分,一是N皇后问题算法的实现;二是程序界面的设计及界面功能的实现;三是做到算法实现过程的动态演示。
其中N皇后问题算法的实现是首要的任务,只有算法本身得到了实现,下面将其进行动态演示的部分才能继续。
老师在课堂上对N皇后问题有过的讲解,再经过我们课后的上机实际操作,在较短的时间内我们就对快速排序算法本身有了较为准确和深刻的认识,并将其用JAVA语言进行了实现。
第二和第三部分同样是需要我们重点攻克的内容,要做好界面的设计及界面功能的实现,需要我们了解界面的布局方法、各种组件的特点及功能、功能实现怎么与算法相契合等;要做到算法实现过程的动态演示,我们必须能熟练地使用JAVA中的画图工具及对
多线程有很好的了解等。
虽然有这么一系列的问题摆在我们面前,但有了之前完成快速排序题目的知识积累,我们很快就有了解决的思路。
为了能够更好的完成这次的程序设计,我们把所需的相关书籍等资料
重新搜集过来,进行更加深入的学习,来完善我们在相关方面的知识。
在将从图书馆借阅的书籍翻阅过后,我们大家决定集思广益,再次在一起分析了这个题目,大家经过认真地商讨后最终确定了这次程序编写的整体规划和较为详细的合作分工。
在共同合作编写程序的过程当中,我们在自己负责的部分当中都或多或少的遇到了较为棘手的问题。
例如:
在棋牌上绘制皇后时不知怎么才能不把原先绘制的棋盘覆盖掉;显示解的个数时,计数器总是进行累计却不知为何;不知为什么在进行动态演示时皇后会在棋盘外等等。
但是我们经过仔细地重新研究程序后,这出现这一系列问题的原因都被
copyright@ 2008-2023 冰点文库 网站版权所有
经营许可证编号:鄂ICP备19020893号-2