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 = http://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相关内容感兴趣的读者可查看本站专题：《Java数据结构与算法教程》、《Java字符与字符串操作技巧总结》、《java日期与时间操作技巧汇总》、《Java操作DOM节点技巧总结》和《Java缓存操作技巧汇总》

希望本文所述对大家java程序设计有所帮助。

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。