快捷導(dǎo)航

Java基于循環(huán)遞歸回溯實現(xiàn)八皇后問題算法示例

更新時間：2017年06月12日 08:49:09 作者：qq7342272

這篇文章主要介紹了Java基于循環(huán)遞歸回溯實現(xiàn)八皇后問題算法,結(jié)合具體實例形式分析了java的遍歷、遞歸、回溯等算法實現(xiàn)八皇后問題的具體步驟與相關(guān)操作技巧,需要的朋友可以參考下

本文實例講述了Java基于循環(huán)遞歸回溯實現(xiàn)八皇后問題。分享給大家供大家參考，具體如下：

運行效果圖如下：

棋盤接口

/**
 * 棋盤接口
 * @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;
  }
  //當(dāng)前行是否能放棋子
  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;
  }
  //主要的遞歸實現(xiàn)方法
  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個則打印結(jié)果
        }
        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);
  }
}

更多關(guān)于java相關(guān)內(nèi)容感興趣的讀者可查看本站專題：《Java數(shù)據(jù)結(jié)構(gòu)與算法教程》、《Java字符與字符串操作技巧總結(jié)》、《java日期與時間操作技巧匯總》、《Java操作DOM節(jié)點技巧總結(jié)》和《Java緩存操作技巧匯總》

希望本文所述對大家java程序設(shè)計有所幫助。

您可能感興趣的文章: