#include <stdio.h>
#include <iostream.h>
#define QueenNum 8
void output(int solution[QueenNum])
{
for(int i=0;i<QueenNum;i++)
{
cout<<solution[i]<<" ";
}
cout<<"\n";
}
int judge(int solution[QueenNum])
{
for(int i=0;i<QueenNum;i++)
{
for(int j=0;j<QueenNum;j++)
{
if(solution[j] ==0)
{
cout<<"incomplete solution";
output(solution);
return 1; //incomplete solution
}
else if(i != j && (solution[i] == solution[j] || solution[i]-solution[j] == i-j || solution[i]-solution[j] == j-i) )
{
cout<<"Error\n";
return 0; //Error solution
}
}
}
return 2; //right solution
}
int main(void)
{
int solution[QueenNum];
int k = 0;
bool flag = false;
for(int i=0;i<QueenNum;i++)
{
solution[i] = 0;
}
int test[QueenNum] = {2,4,3,1};
cout<<"====="<<judge(test);
while(k>=0)
{
while(solution[k]<QueenNum)
{
solution[k] = solution[k]+ 1;
if(judge(solution) == 2)
{
flag = true;
break;
}
else if(judge(solution) == 1)
{
k = k+1;
}
}
if(flag == true) //find the solution and exit
{
cout<<"========Solution!===========";
output(solution);
break;
}
solution [k] = 0;
k = k-1;
}
return 0;
}
回溯法在纸上画出来是很容易的,但是在具体实现时,个人认为有两点要注意:
1. judge方法,判断solution是否为正解、不完全解或者错误解
2. 当判断为错误解时,怎么回溯,上面的代码里回溯应该是solution[k]已经从1遍历到4,若判断1~4都是错误解,那么就只能回溯到上一步,让solution[k]取solution[k]+1的值
分享到:
相关推荐
8 Queen-代码思想简单易懂
This is the code for 8 Queen prob in C...
This is a simple program to help you to find the 8 Queen problem with climbhill method. Using vb6
8 queen implementation matlab
载的简单的8queen问题,很简单,有用得着的可以下载啦
WinFrom的8 Queen拼图应用程序如何使用示例8Queen拼图:许可信息 该软件是开放源代码,根据GNU通用公共许可证版本3.0许可。 有关详细信息,请参见 。 该类库创建了一种处理结构化异常处理的方法,从Exception类继承...
用C实现,8皇后的经典算法,其中有注释,希望下载者可以多提宝贵意见,谢谢!
Matlab,国际象棋棋盘上,八个王后问题,要求王后相互之间都不会吃掉对方。
在一个8×8的棋盘里放置8个皇后,要求每个皇后两两之间不相"冲"发现很少有关于C#的算法,这是最近写的一个八皇后的算法我写了很详细的注解。
用VC++解决八皇后问题, 基因算法
8 Queen's problem is an ancient and famous, the problem is the famous 19th century mathematician Gauss 1850 : in the 8x8 grid placed on the international chess 8 Queen's, making it unable to attack ...
visual c++ programmin 8 queen problem
八皇后问题-模拟退火技术 模拟退火技术的python / curses可视化解决了8个皇后问题
八皇后问题的C++实现 只是一个简单的深度优先求解,无聊做来玩的。
java环境下采用广度优先搜索来求解8-puzzle、8-queen等智能问题
八皇后算法
微机接口硬件实验报告八皇后问题图形版://8 Queen 递归算法 //如果有一个Q 为 chess[i]=j; //则不安全的地方是 k行 j位置,j+k-i位置,j-k+i位置 import java.awt.*; import java.awt.event.*; import javax.swing.*;...
queen8求解方法的伪代码,有助于正确理解回溯法。
实现8后问题的实验报告内涵源代码和结果截图,简易。
(new Queen()).compute( 8 ); } } 三、八皇后问题的Qbasic版的解决方案 10 I = 1 20 A(I) = 1 30 G = 1 40 FOR K = I - 1 TO 1 STEP -1 50 IF A(I) = A(K) THEN 70 60 IF ABS(A(I) - A(K)) <> I...