本文实例讲述了C语言八皇后问题解决方法。分享给大家供大家参考,具体如下:
1.概述:
八皇后问题是一个以国际象棋为背景的问题:如何能够在 8×8 的国际象棋棋盘上放置八个皇后,使得任何一个皇后都无法直接吃掉其他的皇后?为了达到此目的,任两个皇后都不能处于同一条横行、纵行或斜线上。
2.暴力法求解:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
|
#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 ( "%d\n" ,count);
return 0;
}
|
3.回溯法求解;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
|
#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 ( "%d\n" ,count);
return 0;
}
|
希望本文所述对大家C语言程序设计有所帮助。
原文链接:http://blog.csdn.net/qq_37999723/article/details/78148858