【算法设计与分析基础】八皇后有关问题
用Java实现八皇后问题的图形界面:
显示前请先按start键,然后按next键输出一个个的结果,slower和faster调节演示速度。
可以通过操作 → 输入来判断是否满足八皇后条件,输入格式:8个数字,两个数字之间空一格。
① R.java 定义全局变量。变量都被定义为静态。
static void sleep(double i) 暂停 i 秒钟
package eq; public class R { //////////// 矩阵大小 ///////////////// public static int rect_x = 50; public static int rect_y = 50; public static int rect_Height = 30; public static int rect_Width = 30; ///////////////////////////////////////// public final static int n = 8;//八皇后问题 ///////////// 窗口大小 ///////////////// public final static int frame_Height = rect_y + rect_Height*n + 100; public final static int frame_Width = rect_x + rect_Width * n + 50; public static ButtonPanel bp = new ButtonPanel(); public static QueuePanel qp = new QueuePanel(); public static SurfaceView sv; public static Deal d = new Deal(); public static Input i = new Input(); public static double sleeptime = 0.0; public static boolean displaychoice = false; public static int x; public static int y; public static boolean next = true; /** * 暂停一段时间 * @param i 单位秒 */ public static void sleep(double i){ try { Thread.sleep((int)(i*(double)1000)); } catch (InterruptedException e) { // TODO 自动生成的 catch 块 e.printStackTrace(); }; } }② SurfaceView.java 主窗口,添加按钮面板和八皇后国际象棋面板后,就是整个图形界面。
package eq; import java.awt.event.ActionEvent; import java.awt.event.ActionListener; import javax.swing.JFrame; import javax.swing.JMenu; import javax.swing.JMenuBar; import javax.swing.JMenuItem; public class SurfaceView extends JFrame implements ActionListener { public SurfaceView(){ this.setSize(R.frame_Width,R.frame_Height); this.setDefaultCloseOperation(EXIT_ON_CLOSE); this.setTitle("QueueProblem"); this.setLayout(null); R.bp.setBounds(0,0,R.frame_Width,R.bp.bt.Box_Height+10); this.add(R.bp); R.qp.setBounds(0,R.bp.getHeight(),R.frame_Width,(int)((double)R.frame_Height*0.9)); JMenuBar JMB =new JMenuBar(); this.setJMenuBar(JMB); JMenu Item = new JMenu("操作"); JMB.add(Item); JMenuItem input = new JMenuItem("输入"); Item.add(input); input.addActionListener(this); this.add(R.qp); } @Override public void actionPerformed(ActionEvent e) { if(e.getActionCommand().equals("输入")){ R.i.setVisible(true); } } }③ QueuePanel.java 八皇后国际象棋面板。
1. void isinthePanel(int a,int b,Graphics g) 如果是在八皇后面板内,那么就画一个圆
2. void paintchoice(Graphics g)
当指向一个皇后棋子的时候,它会在它的横竖斜上画一个黑圆,需要设置R.java中的displaychoice=true。
3. void paint(Graphics g) JPanel等控件的绘画函数,可以用Graphics来画圆画正方形之类的图形。
4. void isQueue(double x,double y)判断该坐标是不是在八皇后面板内,是就令R.x=i;R.y=j;,否则就赋值-1。
5. void mouseMoved(MouseEvent e)鼠标移动过程中,如果指向了皇后棋子,就重绘面板图形,使其横竖斜上出现黑 圆圈,需要设置R.java中的displaychoice=true。
package eq; import java.awt.BasicStroke; import java.awt.Color; import java.awt.Font; import java.awt.Graphics; import java.awt.Image; import java.awt.event.MouseEvent; import java.awt.event.MouseMotionListener; import java.io.File; import java.io.IOException; import java.awt.Graphics2D; import javax.imageio.ImageIO; import javax.swing.JPanel; public class QueuePanel extends JPanel implements MouseMotionListener { //FFC995 //CC813D String path = ""; public QueuePanel(){ this.setBackground(new Color(255,255,255)); path = new File("").getAbsolutePath() + "\\queue.png"; this.addMouseMotionListener(this); } public void rd(){ this.repaint(); } void isinthePanel(int a,int b,Graphics g){ int x = R.x + a; int y = R.y + b; int oval_x; int oval_y; if(x>=0 && x<R.n && y>=0 && y<R.n){ oval_x = (R.rect_x + y*R.rect_Width)+(int)((double)R.rect_Width*0.4);//行 oval_y = (R.rect_y + x*R.rect_Height)+(int)((double)R.rect_Height*0.4);//列 g.drawOval(oval_x,oval_y ,(int)((double)R.rect_Height*0.2) ,(int)((double)R.rect_Width*0.2 )); /*g.drawRect(R.rect_x + y * R.rect_Width, R.rect_y + x * R.rect_Height, R.rect_Width, R.rect_Height);*/ } } public void paintchoice(Graphics g){ if(R.x!=-1 && R.y!=-1){ int i; int oval_x; int oval_y; ((Graphics2D)g).setStroke(new BasicStroke(2.0f)); g.setColor(new Color(0,0,0)); for(i=-1;++i<R.n;){ oval_x = (R.rect_x+i*R.rect_Width)+(int)((double)R.rect_Width*0.4);//行 oval_y = (R.rect_y+R.x*R.rect_Height)+(int)((double)R.rect_Height*0.4);//列 g.drawOval(oval_x,oval_y ,(int)((double)R.rect_Height*0.2) ,(int)((double)R.rect_Width*0.2 )); oval_x = (R.rect_x+R.y*R.rect_Width)+(int)((double)R.rect_Width*0.4);//行 oval_y = (R.rect_y+i*R.rect_Height)+(int)((double)R.rect_Height*0.4);//列 g.drawOval(oval_x,oval_y ,(int)((double)R.rect_Height*0.2) ,(int)((double)R.rect_Width*0.2 )); } int k; for(k=0;++k<R.n;){ isinthePanel(k,k,g); isinthePanel(-k,k,g); isinthePanel(k,-k,g); isinthePanel(-k,-k,g); } } } public void paint(Graphics g){ super.paint(g); int i,j; Image img = null; // g.drawString(path, 10, 10); try { img = ImageIO.read(new File(path)); // img = ImageIO.read(getClass().getResource("/queue.png")); } catch (IOException e) { // TODO 自动生成的 catch 块 e.printStackTrace(); } g.setColor(new Color(0,0,0)); g.setFont(new Font("Georgia",Font.PLAIN,20)); g.drawString(String.valueOf((R.d.n)%(92)+1)+"\\"+"92", R.rect_x, R.rect_y-3); for(i=-1;++i<R.n;){ for(j=-1;++j<R.n;){ if((i+j)%2==0){ g.setColor(new Color(0xFF,0XC9,0X95)); } else{ g.setColor(new Color(0xCC,0X81,0X3D)); } g.fillRect(R.rect_x + j * R.rect_Width, R.rect_y + i * R.rect_Height, R.rect_Width, R.rect_Height); if(j == R.d.col[i]){ g.drawImage(img, R.rect_x + j * R.rect_Width+3, R.rect_y + i * R.rect_Height+3, R.rect_Width-6, R.rect_Height-6 , this); } } } if(R.displaychoice) paintchoice(g); } void isQueue(double x,double y){ double i = (y-R.rect_x)/R.rect_Height;//行 double j = (x-R.rect_y)/R.rect_Width;//列 if( i>=0 && i< R.n && j>=0 && j< R.n){ R.x = (int)i; R.y = (int)j; } else{ R.x = -1; R.y = -1; } } @Override public void mouseDragged(MouseEvent e) { // TODO 自动生成的方法存根 } <span style="white-space:pre"> </span>@Override <span style="white-space:pre"> </span>public void mouseMoved(MouseEvent e) { <span style="white-space:pre"> </span>if(R.displaychoice){ <span style="white-space:pre"> </span>int x = e.getX(); <span style="white-space:pre"> </span>int y = e.getY(); <span style="white-space:pre"> </span>isQueue(x,y); <span style="white-space:pre"> </span>if(R.x!=-1 && R.y!=-1 && R.d.col[R.x] == R.y){ <span style="white-space:pre"> </span>rd(); <span style="white-space:pre"> </span>} <span style="white-space:pre"> </span>} <span style="white-space:pre"> </span>} }④ ButtonPanel.java 按钮面板。显示四个按钮next slower faster start。
package eq; import java.awt.Color; import java.awt.Font; import java.awt.Graphics; import java.awt.event.MouseEvent; import java.awt.event.MouseListener; import javax.swing.JPanel; public class ButtonPanel extends JPanel implements MouseListener { BoxText bt = new BoxText("next","华文琥珀",Font.PLAIN,20,0,0); BoxText bt1 = new BoxText("slower","华文琥珀",Font.PLAIN,20,bt.Box_Width+10,0); BoxText bt2 = new BoxText("faster","华文琥珀",Font.PLAIN,20,bt.Box_Width+bt1.Box_Width+20,0); BoxText bt3 = new BoxText("start","华文琥珀",Font.PLAIN,20,bt.Box_Width+bt1.Box_Width+bt2.Box_Width+30,0); boolean start = false; public ButtonPanel(){ this.setBackground(new Color(255,255,255)); this.addMouseListener(this); } public void paint(Graphics g){ super.paint(g); bt.draw(g); bt1.draw(g); bt2.draw(g); bt3.draw(g); } @Override public void mouseClicked(MouseEvent e) { // TODO 自动生成的方法存根 } @Override public void mousePressed(MouseEvent e) { // TODO 自动生成的方法存根 } @Override public void mouseReleased(MouseEvent e) { // TODO 自动生成的方法存根 int x = e.getX(); int y = e.getY(); if(e.getButton()==e.BUTTON1){ /** * 如果点击到了"next"按钮 */ if(start && R.next && bt.isClicked(x, y)){ R.next = false; R.x = -1; R.y = -1; Thread t = new Thread(new Runnable(){ public void run(){ R.d.n++; R.d.solve_next(); } }); t.start(); } /** * 如果点击到了"slower"按钮 */ if(bt1.isClicked(x, y)){ R.sleeptime+=0.1; } /** * 如果点击到了"faster"按钮 */ if(bt2.isClicked(x, y)){ if(R.sleeptime>=0.1){ R.sleeptime-=0.1; } } /** * 如果点击到了"start"按钮 */ if(bt3.isClicked(x, y)){ R.d.n = 0; for(int i = -1;++i<R.n;){ R.d.col[i] = 0; } Thread t = new Thread(new Runnable(){ public void run(){ R.d.solve(-1); } }); t.start(); start = true; } } } @Override public void mouseEntered(MouseEvent e) { // TODO 自动生成的方法存根 } @Override public void mouseExited(MouseEvent e) { // TODO 自动生成的方法存根 } }⑤ GameBegin.java main函数在这个文件里
package eq; import java.lang.reflect.InvocationTargetException; public class GameBegin { public static void main(String[] args){ try { javax.swing.SwingUtilities.invokeAndWait(new Runnable(){ public void run(){ R.sv = new SurfaceView(); R.sv.setVisible(true); } }); }catch (InvocationTargetException | InterruptedException e) { // TODO 自动生成的 catch 块 e.printStackTrace(); } } }⑥ Deal.java 八皇后算法函数都在这一文件里
1. class Position,用于存储一个坐标,分别是 row 行 和 col 列
2. void solve(int beginrow) 从第beginrow行开始往右挪动棋子。如果棋子摆放成功,就进入beginrow+1行。如果棋子到了第8列也摆放不成功,第beginrow行的棋子回第一列,然后进入beginrow-1行。
3. void solve_next() 获取下一个解,只需要把第8行的棋子往右挪一格子
4. boolean check(int r)判断第r行的皇后是不是满足八皇后条件,即横竖斜没有其它皇后,用斜率来判断。
5. void displaycol()用于测试用,与算法无关系。
package eq; class Position{ int row; int col; Position(int r,int c){ this.row = r; this.col = c; } } public class Deal { int[] col = new int[R.n]; int n = 0; public Deal(){ } public void solve(int beginrow){ int i, j; Position p; //从指定行的下面一行开始往下遍历 for(i=beginrow;++i<R.n;){ //从当前列开始往后遍历 for(j=col[i];j<R.n;j++){ R.qp.rd(); R.sleep(R.sleeptime); //赋值 col[i]=j; //检查该行与前面所有行是否能共存 if(check(i)){ break; } } //如果当前列遍历到最后 if(j >= R.n){ //该列的皇后回到第一列 col[i]=0; //往上回溯一行,由于++i所以需要-2 i-=2; //上面一行的皇后右移一格,由于-2所以+1 if(i+1>=0) col[i+1]++; else i = -1;//如果是第一行最后一列回溯,即完成一个循环 } } } public void solve_next(){ //获得下一个解。把最后一行的皇后右移,继续遍历即可 col[R.n-1]++; solve(R.n-2); R.qp.rd(); R.next = true; } boolean check(int r){ int i; double k; for(i=r;--i>=0;){ k = Math.abs(((double)col[r]-(double)col[i])/((double)r-(double)i)); if(k == 1.0 || k == 0.0){ return false; } } return true; } void displaycol(){ int i; for(i=-1;++i<R.n;){ System.out.print(col[i]+1+ ","); } System.out.println(); } }
⑦ Input.java 输入窗口,按下菜单栏里的菜单项弹出。
package eq; import java.awt.event.ActionEvent; import java.awt.event.ActionListener; import javax.swing.JButton; import javax.swing.JFrame; import javax.swing.JOptionPane; import javax.swing.JTextField; public class Input extends JFrame implements ActionListener { JTextField JTF; Input(){ this.setSize(200,120); this.setDefaultCloseOperation(DISPOSE_ON_CLOSE); this.setLayout(null); JTF = new JTextField(); JTF.setBounds(10,10,180,25); this.add(JTF); JButton JB = new JButton("确定"); JB.addActionListener(this); JB.setBounds(10,50,60,30); this.add(JB); } @Override public void actionPerformed(ActionEvent e) { if(e.getActionCommand().equals("确定")){ String[] a = JTF.getText().split(" "); int i; for(i=-1;++i<a.length && i<R.n;){ R.d.col[i] = Integer.parseInt(a[i])-1; } R.qp.rd(); for(i=0;++i<R.n;){ if(!R.d.check(i)){ JOptionPane.showMessageDialog(R.sv,"不满足八皇后要求","错误",JOptionPane.ERROR_MESSAGE); break; } } if(i==R.n){ JOptionPane.showMessageDialog(R.sv,"满足八皇后要求","正确",JOptionPane.INFORMATION_MESSAGE); } } } }⑧ BoxText.java 按钮类。一个类变量代表一个按钮。
package eq; import java.awt.Color; import java.awt.Font; import java.awt.FontMetrics; import java.awt.Graphics; import javax.swing.JLabel; public class BoxText{ String text = ""; String fontface = ""; int fonttype = 0; int fontsize = 0; int Box_x = 0; int Box_y = 0; int Box_Height = 0; int Box_Width = 0; public BoxText(String text,String fontface,int fonttype,int fontsize,int Box_x,int Box_y){ /////////// 1. 获取值:text: 文本; fontface: 字体; fonttype: 字体类型; fontsize: 字体大小 /////////////////// ////////// Box_x,Box_y: 按钮左上角顶点所在位置 /////////////////// this.text = text; this.fontface = fontface; this.fonttype = fonttype; this.fontsize = fontsize; this.Box_x = Box_x; this.Box_y = Box_y; ////////////// 2. 根据字体的高度和宽度,设置箱子的高度和宽度 /////////////////////// Font f = new Font(fontface, fonttype, fontsize); FontMetrics fm = new JLabel().getFontMetrics(f); Box_Height = fm.getHeight() ; Box_Width = fm.stringWidth(text) + 20; } /** * 获取文本左下角顶点的坐标x * @return 文本左下角顶点的坐标x */ public int getText_x(){ return Box_x + 10; } /** * 获取文本左下角顶点的坐标y * @return 文本左下角顶点的坐标y */ public int getText_y(){ return Box_y + Box_Height - 5; } /** * 获取面板paint函数中的Graphics来将该箱子画上去 * @param g 某画板的Graphics */ public void draw(Graphics g){ g.setColor(new Color(0,0,0)); g.fillRect(Box_x,Box_y,Box_Width,Box_Height); g.setFont(new Font(fontface,fonttype,fontsize)); g.setColor(new Color(255,255,255)); g.drawString(text, getText_x(), getText_y()); } /** * 看箱子是否被按下 * @param x 鼠标弹起的x坐标 * @param y 鼠标谈起的y坐标 * @return 布尔类型:是否按下 */ public boolean isClicked(int x,int y){ return x >= Box_x && y >= Box_y && x <= Box_x+Box_Width && y <= Box_y + Box_Height; } }<strong> </strong>
算法分析:
本例子的jar文件下载:http://download.****.net/detail/u013580497/8902079
版权声明:本文为博主原创文章,未经博主允许不得转载。