如何用C语言编写八皇后问题？

Python018

如何用C语言编写八皇后问题？,第1张

#include "stdio.h"

#include "windows.h"

#define N 8 /* 定义棋盘大小 */

int place(int k)/* 确定某一位置皇后放置与否，放置则返回1，反之返回0 */

void backtrack(int i)/* 主递归函数，搜索解空间中第i层子树 */

void chessboard()/* 每找到一个解,打印当前棋盘状态 */

static int sum, /* 当前已找到解的个数 */

x[N]/* 记录皇后的位置,x[i]表示皇后i放在棋盘的第i行的第x[i]列 */

int main(void)

{

backtrack(0)

system("pause")

return 0

}

int place(int k)

{

/* 测试皇后k在第k行第x[k]列时是否与前面已放置好的皇后相攻击。 x[j] == */

/* x[k] 时，两皇后在同一列上；abs(k - j) == abs(x[j] - x[k]) 时，两皇 */

/* 后在同一斜线上。两种情况两皇后都可相互攻击，故返回0表示不符合条件。*/

for (int j = 0j <kj ++)

if (abs(k - j) == abs(x[j] - x[k]) || (x[j] == x[k])) return 0

return 1

}

void backtrack(int t)

{

/* t == N 时，算法搜索至叶结点，得到一个新的N皇后互不攻击的放置方案 */

if (t == N) chessboard()

else

for (int i = 0i <Ni ++) {

x[t] = i

if (place(t)) backtrack(t + 1)

}

}

void chessboard()

{

printf("第%d种解法:\n", ++ sum)

for (int i = 0i <Ni ++) {

for (int j = 0j <Nj ++)

if (j == x[i]) printf("@ ")

else printf("* ")

printf("\n")

}

printf("\n")

}

这是经典题目，答案网上有的是，抄一个学学就可以了：

回溯法进行求解，程序实现如下：

#include<stdio.h>

#define Queens 8 //定义结果数组的大小，也就是皇后的数目

int a[Queens+1] //八皇后问题的皇后所在的行列位置，从1开始算起，所以加1

int main(){

int i, k, flag, not_finish=1, count=0

//正在处理的元素下标，表示前i-1个元素已符合要求，正在处理第i个元素

i=1

a[1]=1 //为数组的第一个元素赋初值

printf("The possible configuration of 8 queens are:\n")

while(not_finish){ //not_finish=l:处理尚未结束

while(not_finish &&i<=Queens){ //处理尚未结束且还没处理到第Queens个元素

for(flag=1,k=1flag &&k<ik++) //判断是否有多个皇后在同一行

if(a[k]==a[i])

flag=0

for (k=1flag&&k<ik++) //判断是否有多个皇后在同一对角线

if( (a[i]==a[k]-(k-i)) || (a[i]==a[k]+(k-i)) )

flag=0

if(!flag){ //若存在矛盾不满足要求，需要重新设置第i个元素

if(a[i]==a[i-1]){ //若a[i]的值已经经过一圈追上a[i-1]的值

i-- //退回一步，重新试探处理前一个元素

if(i>1 &&a[i]==Queens)

a[i]=1 //当a[i]为Queens时将a[i]的值置1

else

if(i==1 &&a[i]==Queens)

not_finish=0 //当第一位的值达到Queens时结束

else

a[i]++ //将a[il的值取下一个值

}else if(a[i] == Queens)

a[i]=1

else

a[i]++ //将a[i]的值取下一个值

}else if(++i<=Queens)

if(a[i-1] == Queens )

a[i]=1 //若前一个元素的值为Queens则a[i]=l

else

a[i] = a[i-1]+1 //否则元素的值为前一个元素的下一个值

}

if(not_finish){

++count

printf((count-1)%3 ? "\t[%2d]:" : "\n[%2d]:", count)

for(k=1k<=Queensk++) //输出结果

printf(" %d", a[k])

if(a[Queens-1]<Queens )

a[Queens-1]++ //修改倒数第二位的值

else

a[Queens-1]=1

i=Queens -1 //开始寻找下一个满足条件的解

}

}