欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

Java基于循环递归回溯实现八皇后问题算法示例

程序员文章站 2023-12-20 09:59:22
本文实例讲述了java基于循环递归回溯实现八皇后问题。分享给大家供大家参考,具体如下: 运行效果图如下: 棋盘接口 /** * 棋盘接口 * @a...

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

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

上一篇:

下一篇: