本文实例讲述了C语言八皇后问题解决方法。分享给大家供大家参考，具体如下：
1.概述：
八皇后问题是一个以国际象棋为背景的问题：如何能够在 8×8 的国际象棋棋盘上放置八个皇后，使得任何一个皇后都无法直接吃掉其他的皇后？为了达到此目的，任两个皇后都不能处于同一条横行、纵行或斜线上。
2.暴力法求解:
#include<cstdio>#include<cmath>const int maxn=11;
int count=0;
//P为当前排列,hashTable记录整数x是否已经在P中int n,P[maxn] ,hashTable[maxn] = {
false}
;
//当前处理排列的第index号位void generateP(int index){
if(index==n+1)//递归边界,已经处理完排列的1~n位 {
bool flag=true;
//flag为true表示当前排列为一个合法方案 for(int i=1;
i<=n;
i++) {
for(int j=i+1;
j<=n;
j++) {
if(abs(i-j)==abs(P[i]-P[j]))//如果在对角线上 {
flag=false;
//不合法 }
}
}
if(flag) count++;
//若当前方案合法,count+1 return ;
}
for(int x=1 ;
x<=n ;
x++)//枚举1~n,试图将x填入P[index] {
if(hashTable[x]==false)//如果x不在P[0]~P[index-1]中 {
P[index]=x;
//令P的第index位为x,即把x加入当前排列 hashTable[x]=true;
//记x已在P中 generateP(index+1);
//处理排列的第index+1号位 hashTable[x]=false;
//已处理完P[index]为x的子问题,还原状态}
}
}
int main(){
n=8;
generateP(1);
printf("%dn",count);
return 0;
}
3.回溯法求解;
#include<cstdio>#include<cmath>const int maxn=11;
int count=0;
//P为当前排列,hashTable记录整数x是否已经在P中int n,P[maxn] ,hashTable[maxn] = {
false}
;
//当前处理排列的第index号位void generateP(int index){
if(index==n+1) {
count++;
return ;
}
for(int x=1;
x<=n;
x++)//第x行 {
if(hashTable[x]==false)//第x行还没有皇后 {
bool flag=true;
//flag表示当前皇后不会和之前的皇后冲突 for(int pre=1;
pre<index;
pre++)//遍历之前的皇后 {
//第index行的皇后的行号为x,第pre列皇后的行号为P[pre] if(abs(index-pre)==abs(x-P[pre])) {
flag=false;
//与之前的皇后在一条对角线,冲突 break;
}
}
if(flag)//如果可以把皇后放在第x行 {
P[index]=x;
//令第index列皇后的行数为x hashTable[x]=true;
//第x行已经被占用 generateP(index+1);
//递归处理第index+1行皇后 hashTable[x]=false;
//递归完毕,还原第x行为为占用状态 }
}
}
}
int main(){
n=8;
generateP(1);
printf("%dn",count);
return 0;
}
希望本文所述对大家C语言程序设计有所帮助。
您可能感兴趣的文章:
- C++基于回溯法解决八皇后问题示例
- 八皇后问题的相关C++代码解答示例
- C++实现八皇后问题的方法
- c++递归实现n皇后问题代码(八皇后问题)
- java实现八皇后问题示例分享
- python基于右递归解决八皇后问题的方法
- C#用递归算法解决八皇后问题
- C语言使用深度优先搜索算法解决迷宫问题(堆栈)
- C语言使用广度优先搜索算法解决迷宫问题（队列）
- C语言实现的猴子分桃问题算法解决方案
- C语言实现的猴子吃桃问题算法解决方案
- C语言解决螺旋矩阵算法问题的代码示例
