package queen;
import java.util.Date;
public class SimpleQueen {
private final int size ;//棋盘大小
private boolean[][] isOccupied ;//初始化为false
private static int hasQueen = 0;//已经存在的皇后数
private static int count = 0;//统计总数
public SimpleQueen(int size){
this.size = size;
isOccupied = new boolean[size][size];
}
/**
* 条件一,判断此列是否有摆放皇后
*/
private boolean isColOccupied(int line){
for(int i = 0; i < size; i++){
if(isOccupied[i][line] == true){
return false;
}
}
return true;
}
/**
* 条件二,判断对角线是否有摆放皇后
*/
private boolean isFourPointsOccupied(int row,int col){
int i ,j ;//四次for循环的时候一定需要将i j进行重新初始化,否则越界,容易调用的是上一次for循环后 i j的值
//判断右下角
for(i=row,j=col;i < size&&j < size; i++,j++){
if(isOccupied[i][j] == true){
return false;
}
}
//判断左上角
for(i=row,j=col;i >= 0&&j >= 0; i--,j--){
if(isOccupied[i][j] == true){
return false;
}
}
//判断右上角
for(i=row,j=col;i >= 0&&j < size; i--,j++){
if(isOccupied[i][j] == true){
return false;
}
}
//判断左下角
for(i=row,j=col;i < size&&j >= 0; i++,j--){
if(isOccupied[i][j] == true){
return false;
}
}
return true;
}
/**
* 开始从第i行安放皇后的位置
*/
private void place(int row){
if(row >= size) //从第row行安放皇后,如果row大于棋盘的行数,程序结束
return;
for(int i = 0; i < size; i++){
if(isColOccupied(i) && isFourPointsOccupied(row, i)){
isOccupied[row][i] = true;//条件一、二均满足,则该位置可以放置皇后
hasQueen++;//并且皇后数加一
if(hasQueen == size){
count++;//得到方案个数
printQueen();//调用打印函数
isOccupied[row][i] = false;//对数组该位置还原为false,以进行下一种情况查找
hasQueen--;
continue;//for循环中,该语句后面的不需要执行,进入下一次for循环
}
//进行到这一步说明:程序查找 row 行 i 列
this.place(row+1);
this.isOccupied[row][i] = false;
hasQueen--;
}
}
}
/**
* 打印满足条件的摆放方法
*/
private void printQueen(){
System.out.println("第 " + count + " 种摆放方案如下:");
for(int i = 0; i < size; i++){
for(int j = 0; j < size; j++){
if(isOccupied[i][j]==true)
System.out.print("+ ");
else
System.out.print("- ");
}
System.out.println();
}
}
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
long start = new Date().getTime();
new SimpleQueen(5).place(0);
System.out.println("\n一共有 " + count + " 种摆放方案");
long end = new Date().getTime();
System.out.println("一共耗时 "+(end-start)+" ms");
}
}
分享到:
相关推荐
8皇后问题 8皇后问题 8皇后问题
八皇后问题 最简单dfs模板代码八皇后问题 最简单dfs模板代码八皇后问题 最简单dfs模板代码八皇后问题 最简单dfs模板代码八皇后问题 最简单dfs模板代码八皇后问题 最简单dfs模板代码八皇后问题 最简单dfs模板代码八...
一段关于皇后问题的代码 这是我能写出来的最简单的了! 希望大家能够喜欢!
老师上课提供的八皇后问题的思路。在 n 行 n 列的国际象棋棋盘上,若两个皇后位于同一行、同一列、同一对角线上,则称为它们为互相攻击。n皇后问题是指找到这 n 个皇后的互不攻击的布局
8皇后问题算法实现,基于Java的8皇后问题
很简单,很好用的代码,用于解决八皇后问题(八皇后问题,是一个古老而著名的问题,是回溯算法的典型例题。该问题是十九世纪著名的数学家高斯1850年提出:在8X8格的国际象棋上摆放八个皇后,使其不能互相攻击,即...
详细的介绍了8皇后问题的思路及算法代码 思路清晰
利用回溯法解决8皇后问题,简单并且和很好理解!
解决8皇后的C++最简单的实现,(试验与回朔)
c语言的代码,解决8皇后问题,输出为棋盘式的0,1点阵图,有需要可下载
8皇后问题和由他推广得到的N皇后问题。题目来源于国际象棋的玩法,因为皇后所在的位置可以纵向、横向、两个斜向四个方向的“捕捉”,所以8皇后问题就是要求如何布置8个皇后在8*8的棋盘上而使他们互相无法“捕捉”。...
极好的8皇后问题的算法解析,有非常详细的解释和代码
下面给出使用栈求解 n 皇后问题的思路: 定义一个栈,用于存储已摆放皇后的位置信息。 初始将第一个皇后放到第一行第一列,入栈。 重复以下操作,直到栈为空: 取出栈顶元素,表示当前正在处理的行。 在该行从左到...
8皇后问题 人工智能设计的8皇后问题,启发式搜索
8皇后问题复杂性描述,输入一定方格个数,即可输出最好的排列方式。
8皇后问题求一个精确解,通过递归调用,实现回溯的方法,也是一个深度优先搜索的经典问题
用python解决的8皇后问题,版本是python3.4
n皇后问题C++源码。{典型的8皇后问题的扩展)
c++经典皇后问题 8皇后,超简单递归实现算法(1页代码搞定)
8皇后问题的c代码8皇后问题的c代码8皇后问题的c代码