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);  }}