当前位置:  编程技术>java/j2ee

java N皇后实现问题解析

    来源: 互联网  发布时间:2014-10-21

    本文导语:  N皇后问题是一个典型的约束求解问题,利用递归机制,可以很快的得到结果。 N皇后问题的描述: 在一个n*n的棋盘上,摆放n个皇后,要求每个皇后所在行、列、以及两个对角线上不能出现其他的皇后,否则这些皇后之间将会...

N皇后问题是一个典型的约束求解问题,利用递归机制,可以很快的得到结果。
N皇后问题的描述:
在一个n*n的棋盘上,摆放n个皇后,要求每个皇后所在行、列、以及两个对角线上不能出现其他的皇后,否则这些皇后之间将会相互攻击。如下图所示。

利用递归机制,可以很容易的求解n皇后问题。针对八皇后,总共有92种解。下面将给出N-皇后问题的一般求解代码,在这里代码是使用java编码的。
总共设计了三个类,一个是皇后类(Queen),一个棋盘类(Board),一个是求解主程序类(NQueens)。具体代码如下:
代码如下:

import java.util.ArrayList;
import java.util.List;
public class NQueens {
private int numSolutions;//求解结果数量
private int queenSize;//皇后的多少
private Board board;//棋盘
private List queens = new ArrayList();//皇后
//private List nQueens = new ArrayList();
public NQueens(){
}
public NQueens(int size){
numSolutions = 0;
queenSize = size;
board = new Board(queenSize);
for (int i = 0; i < queenSize; i++) {
Queen queen = new Queen();
queens.add(queen);
}
}
public void solve(){
System.out.println("Start solve....");
putQueen(0);
}
private void putQueen(int index){
int row = index;
//如果此列可用
for (int col = 0; col < board.getQueenSize(); col++) {
if (board.getLayout()[row][col] == 0) {
//将皇后的位置置为此列位置
queens.get(row).setPosition(col);
//然后将相应的位置(此列的正下方以及两个对角线)加1(即使其不可用)
for (int i = row + 1; i < board.getQueenSize(); i++) {
board.getLayout()[i][col] ++;
if (row + col - i >= 0) {
board.getLayout()[i][row + col - i] ++;
}
if (i + col - row < board.getQueenSize()) {
board.getLayout()[i][i + col - row] ++;
}
}
if (row == board.getQueenSize()-1) {
numSolutions++;
printSolution(numSolutions);
}else {
putQueen(row + 1);
}
//回溯,将相应的位置(此列的正下方以及两个对角线)减1
for (int i = row + 1; i < board.getQueenSize(); i++) {
board.getLayout()[i][col] --;
if (row + col - i >= 0) {
board.getLayout()[i][row + col - i] --;
}
if (i + col - row < board.getQueenSize()) {
board.getLayout()[i][i + col - row] --;
}
}
}
}
}
//打印求解结果
private void printSolution(int i){
System.out.println("The "+i+ " solution is:");
for (int j = 0; j < board.getQueenSize(); j++) {
for (int k = 0; k < board.getQueenSize(); k++) {
System.out.print(queens.get(j).getPosition() == k ? " * ":" - ");
}
System.out.println();
}
System.out.println();
}
/**
* @param args
*/
public static void main(String[] args) {
//可以改变参数
NQueens nQueens = new NQueens(8);
nQueens.solve();
}
}
import java.io.Serializable;
//皇后类
public class Queen implements Serializable, Cloneable {
/**
*
*/
private static final long serialVersionUID = 7354459222300557644L;
//皇后的位置
private int position;
public Queen(){
}
public int getPosition() {
return position;
}
public void setPosition(int position) {
this.position = position;
}
public Object clone() throws CloneNotSupportedException {
return super.clone();
}
}
import java.io.Serializable;
//棋盘类
public class Board implements Serializable,Cloneable {
/**
*
*/
private static final long serialVersionUID = -2530321259544461828L;
//棋盘的大小
private int queenSize;
//棋盘的布局
private int[][] layout;
public Board(int size){
this.queenSize = size;
this.layout = new int[queenSize][queenSize];
//初始化,使棋盘所有位置都可用,即全部置为0
for (int i = 0; i < queenSize; i++) {
for (int j = 0; j < queenSize; j++) {
layout[i][j] = 0;
}
}
}
public int getQueenSize() {
return queenSize;
}
public void setQueenSize(int queenSize) {
this.queenSize = queenSize;
}
public int[][] getLayout() {
return layout;
}
public void setLayout(int[][] layout) {
this.layout = layout;
}
public Object clone() throws CloneNotSupportedException {
return super.clone();
}
}

    
 
 

您可能感兴趣的文章:

  • java实现八皇后问题示例分享
  • 8皇后的java实现。
  • java 公式解析 表达式解析 expression-analyzer
  • 请问各位:我用SUN公司的JAXP开发包解析XML文档,可不知道对XML解析后如何将结果写回文件中。请各位熟悉Java和XML的高手帮忙。
  • java解析xml之jdom解析xml示例分享
  • Java 的解析器代码生成器 AustenX
  • Java的HTML解析器 Jerry
  • java解析xml之dom4j解析xml示例分享
  • java解析xml之dom解析xml示例分享
  • Java的CSV解析包 CSVBeans
  • Java的CSV解析包 CSVObjects
  • 求教JAVA中XML解析问题
  • Java表达式解析器 JExel
  • Java代码解析工具 JavaFE
  • Java表达式语法解析库 parboiled
  • Java的HTML解析包 jScraper
  • Java的 RSS/Atom的解析器 FeedParser
  • Java的HL7解析器 HAPI
  • java解析xml用什么包?
  • 有什么java包可以支持解析html的。
  • Java结构化数据解析包 Lycia
  • Java的HTML解析库 gohtml
  •  
    本站(WWW.)旨在分享和传播互联网科技相关的资讯和技术,将尽最大努力为读者提供更好的信息聚合和浏览方式。
    本站(WWW.)站内文章除注明原创外,均为转载、整理或搜集自网络。欢迎任何形式的转载,转载请注明出处。












  • 相关文章推荐
  • 使用java jdk中的LinkedHashMap实现简单的LRU算法
  • java.util.Date 和 java.slq.Date 如何最简单实现互换?
  • java tomcat实现Session对象的持久化原理及配置方法介绍
  • 不太明白,利用RMI实现JAVA分布式应用 和 EJB实现JAVA分布式应用有什么区别。
  • java实现判断字符串是否全是数字的四种方法代码举例
  • java的API中有没有既实现了Map接口又实现了List接口的类?
  • java序列化实现Serializable接口
  • 我是java新手,请问java中与平台相关的操作是怎样实现的
  • java中Spring框架介绍及如何实现对Bean的管理
  • java文件复制代码片断(java实现文件拷贝)
  • java Servlet实现Session创建存取以及url重写代码示例
  • 要做一个在applet,实现可以托拽的图形(比如长方形和线段等)?那位高手有资料?或者有没有java的第三方类库实现此功能?
  • java 与 C++ 实现后绑定的方法
  • XUL的Java实现 javaXUL
  • 用JAVA实现与QQ相同的功能!
  • 请问《软件工程java语言实现》一书在那里能下载
  • 如何实现Java下的回调函数!
  • Java实现的XForms Chiba
  • Java的SAMBA客户端实现 jCIFS
  • Lua 实现的 Java 虚拟机 luje
  • yaml 的 java 实现 JYaml
  • java命名空间java.sql类types的类成员方法: java_object定义及介绍
  • IT科技资讯 iis7站长之家
  • java命名空间java.awt.datatransfer类dataflavor的类成员方法: imageflavor定义及介绍
  • 请问Java高手,Java的优势在那里??,Java主要适合于开发哪类应用程序
  • java命名空间java.lang.management类managementfactory的类成员方法: getcompilationmxbean定义及介绍
  • 如何将java.util.Date转化为java.sql.Date?数据库中Date类型对应于java的哪个Date呢
  • java命名空间java.lang.management接口runtimemxbean的类成员方法: getlibrarypath定义及介绍
  • 谁有电子版的《Java编程思想第二版(Thinking in java second)》和《Java2编程详解(special edition java2)》?得到给分
  • java命名空间java.lang.management接口runtimemxbean的类成员方法: getstarttime定义及介绍
  • 本人想学java,请问java程序员的待遇如何,和java主要有几个比较强的方向


  • 站内导航:


    特别声明:169IT网站部分信息来自互联网,如果侵犯您的权利,请及时告知,本站将立即删除!

    ©2012-2021,,E-mail:www_#163.com(请将#改为@)

    浙ICP备11055608号-3