这里有新鲜出炉的Java设计模式,程序狗速度看过来!
java 是一种可以撰写跨平台应用软件的面向对象的程序设计语言,是由Sun Microsystems公司于1995年5月推出的Java程序设计语言和Java平台(即JavaEE(j2ee), JavaME(j2me), JavaSE(j2se))的总称。
这篇文章主要介绍了Java基于循环递归回溯实现八皇后问题算法,结合具体实例形式分析了java的遍历、递归、回溯等算法实现八皇后问题的具体步骤与相关操作技巧,需要的朋友可以参考下
本文实例讲述了Java基于循环递归回溯实现八皇后问题。分享给大家供大家参考,具体如下:
运行效果图如下:
棋盘接口
- /**
- * 棋盘接口
- * @author Administrator
- *
- */
- public interface Piece {
- abstract boolean isRow(int line);
- abstract boolean isCol(int line, int col);
- }
棋盘类:
- /**
- * 棋盘
- * @author Administrator
- *
- */
- public class Chessboard implements Piece {
- static boolean[][] che = null;
- public int row;
- public int col;
- private int num = 0;
- public Chessboard(int row, int col) {
- this.che = new boolean[row][col];
- this.row = row;
- this.col = col;
- }
- //当前行是否能放棋子
- public boolean isRow(int line) {
- for (int i = 0; i < this.row; i++) {
- if (che[i][line] == true) {
- return false;
- }
- }
- return true;
- }
- //棋子边角
- public boolean isCol(int line, int col) {
- int i = 0,
- j = 0;
- for (i = line, j = col; i < this.row && j < this.row; i++, j++) { //右下角;
- if (che[i][j] == true) {
- return false;
- }
- }
- for (i = line, j = col; i >= 0 && j >= 0; i--, j--) { //左上角;
- if (che[i][j] == true) {
- return false;
- }
- }
- for (i = line, j = col; i >= 0 && j < this.row; i--, j++) { // 右上角;
- if (che[i][j] == true) {
- return false;
- }
- }
- for (i = line, j = col; i < this.row && j >= 0; i++, j--) { //左下角;
- if (che[i][j] == true) {
- return false;
- }
- }
- return true;
- }
- public void pr() { //打印满足条件的摆放方法
- num++;
- System.out.println("第" + num + "种方式");
- System.out.print("-------------start-------------");
- for (int i = 0; i < this.row; i++) {
- System.out.println();
- for (int j = 0; j < this.row; j++) {
- if (che[i][j] == true) {
- System.out.print("Q ");
- } else {
- System.out.print(". ");
- }
- }
- }
- System.out.println();
- System.out.println("-------------end-------------");
- }
- }
皇后类
- /**
- * 皇后
- * @author Administrator
- *
- */
- public class empress {
- private Chessboard che = null;
- private int count = 0;
- private int row = 0;
- public empress(int row, int col) {
- this.che = new Chessboard(row, col);
- this.row = row;
- }
- //主要的递归实现方法
- public void mk(int line) {
- if (line > this.row - 1) return; //超过行则退出
- for (int i = 0; i < this.row; i++) {
- if (che.isRow(i) && che.isCol(line, i)) { //ture 为可以摆皇后;
- che.che[line][i] = true; //
- count++; //
- if (count > this.row - 1) {
- che.pr(); //摆放皇后8个则打印结果
- }
- mk(line + 1); //递归
- che.che[line][i] = false; //回溯
- count--;
- continue;
- }
- }
- return;
- }
- }
启动:
- import java.io.BufferedReader;
- import java.io.InputStreamReader;
- import java.util.Scanner;
- import javax.swing.JOptionPane;
- public class start {
- public static void main(String[] args) {
- String inputrow = JOptionPane.showInputDialog("输入行:");
- int row = Integer.parseInt(inputrow);
- String inputcol = JOptionPane.showInputDialog("输入列:");
- int col = Integer.parseInt(inputcol);
- empress emp = new empress(row, col);
- emp.mk(0);
- }
- }
希望本文所述对大家java程序设计有所帮助。
来源: http://www.phperz.com/article/17/0904/338320.html