在n×n格的棋盘上放置彼此不受攻击的n个皇后。按照国际象棋的规则,皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。n后问题等价于在n×n格的棋盘上放置n个皇后,任何2个皇后不放在同一行或同一列或同一斜线上。
回溯算法描述:
void Queue(int n)
{
for (i=1; i<=n; i++) //初始化
x[i]=0;
k=1;
while (k>=1)
{
x[k]=x[k]+1; //在下一列放置第k个皇后
while (x[k]<=n && !Place(k))
x[k]=x[k]+1; //搜索下一列
if (x[k]<=n && k= =n) { //得到一个解,输出
for (i=1; i<=n; i++)
cout<<x[i];
return; }
else if (x[k]<=n && k<n)
k=k+1; //放置下一个皇后
else {
x[k]=0; //重置x[k],回溯
k=k-1;
} }
}
bool Place(int k) //考察皇后k放置在x[k]列是否发生冲突
{
for (i=1; i<k; i++)
if (x[k]= =x[i] | | abs(k-i)= =abs(x[k]-x[i]))
return false;
return true; }
NQueen.java //回溯算法
import java.util.*;
public class NQueen
{
public static void main(String[] args)
{
Scanner in=new Scanner(System.in);
System.out.println("Please enter the number of queen you want(请输入你要求解的皇后的个数)");
int n=in.nextInt();
double startTime=System.currentTimeMillis();//startTime
Queen(n);
double endTime=System.currentTimeMillis();//endTime
System.out.println("Basic Statements take(基本语句用时) "+(endTime-startTime)+" milliseconds!");
}
/**
*用回溯法设计函数Queen(n)求解
*/
public static boolean Place(int x[],int k)//考察皇后k放置在x[k]列是否发生冲突
{
for(int i=1; i<k; i++)
if (x[k]==x[i]||Math.abs(k-i)==Math.abs(x[k]-x[i]))
return false;
return true;
}
public static void Queen(int n)
{
int x[]=new int[n+1];
for (int i=1; i<=n; i++)//初始化
x[i]=0;
int k=1;
while (k>=1)
{
x[k]=x[k]+1;//在下一列放置第k个皇后
while (x[k]<=n&&!Place(x,k))
x[k]=x[k]+1;//搜索下一列
if (x[k]<=n && k==n)
{ //得到一个解,输出
System.out.println("The answer is(得到的解是):");
for (int i=1; i<=n; i++)
System.out.print("("+i+","+x[i]+")"+" ");
System.out.println();
return;
}
else if (x[k]<=n && k<n)
k=k+1;//放置下一个皇后
else
{
x[k]=0;//重置x[k],回溯
k=k-1;
}
}
}
}
分享到:
相关推荐
算法设计作业,用c++编写的,回溯法求解n皇后问题 运行环境VC6.0
回溯法求解n皇后问题,n皇后问题是一个非常有意思的游戏
算法分析与设计 用回溯法实现n皇后问题(java源码)
N皇后问题(n-queen problem)是一个经典的组合优化问题,也是一个使用回溯法(backtracking)的典型例子。回溯法是一种系统地搜索问题解的方法。 此文档包含算法分析、代码实现、演示程序、演示界面。
该代码为算法实验中比较典型的问题 回溯法求N皇后位置的问题,代码简单,适合初学者
回溯法实现N皇后问题 利用Java中Swing实现的界面比较抽象,但是基本功能还是实现了
在VC++6。0 下用C++语言描述用回溯法求解N皇后问题,是学习算法设计与分析的很好参考。
回溯法实现n皇后问题,并输出每种放法的皇后位置
使用回溯法解决n皇后问题,没有用到栈的结构(但实际算法类似于栈),代码比较简约漂亮
回溯法回溯法回溯法回溯法回溯法回溯法回溯法回溯法回溯法回溯法回溯法回溯法回溯法
N皇后问题求解,分别是递归方法实现和非递归方法实现,后者采用回溯方法,C语言实现的
n 皇后 回溯法n 皇后 回溯法 n 皇后 回溯法 n 皇后 回溯法 n 皇后 回溯法 n 皇后 回溯法
随机输入n个数,用c++回溯法求解n皇后问题
用回溯法求N后问题,已经运行过,可以正常使用
有多种方法解决八皇后问题,在这里我用的是回溯法解决八皇后问题。大家一起来学习呀!!
回溯法求解四皇后问题一种解法 代码都是运行过得,没有
n 皇后问题是一道经典的回溯算法问题,其目标是在一个 � × � n×n 的棋盘上放置 � n 个皇后,使得任意两个皇后都不能在同一行、同一列或同一斜线上。 栈可以用来辅助实现回溯算法,本质上就是手动维护了递归...
分别用随机算法和回溯法求解N皇后问题 附有详细C++源代码
使用分支限界法解决N皇后问题。因为是广度优先,而且占用比较多的额外空间,所以并不是解N皇后问题的很好的算法,主要是理解分支限界法的使用。