㈠ 八皇后问题求解的C语言程序的实现
这是个前不久,我为别人写的一个代码;
八皇后问题共有92种解;
以下代码是解决:对于固定一个皇后位置,输出所有可能情况.
如果这不适合你的答案你可以,稍微改改的哦~~
代码如下:
#include "stdio.h"
bool board[8][8]={0};
int num=0; //满足条件的个数
int inix,iniy; //输入一个皇后的初始位置
void output() //输出
{
int i, j;
for(i=0;i<8;i++)
{
for(j=0;j<8;j++)
{
if(!board[i][j]) printf("■ ");
else printf("◆ ");
}
printf("\n");
}
num++;
printf("\n\n");
return ;
}
bool check(int x,int y) //判断是否能放
{
int i, j ;
for(i=0; i<8 ; i++)
{
if(board[i][y]==1) return false;
}
for(i=0;i<8;i++)
{
if(board[x][i]==1) return false;
}
i=x; j=y;
while(i>0 && j>0 ) { i--; j--; }
for(;i<8 && j<8 ; i++,j++)
if(board[i][j]==1) return false;
i=x; j=y;
while(i>0 && j<7 ) {i--;j++;}
for(;i<8 && j>=0 ; i++ ,j--)
if(board[i][j]==1) return false ;
return true ;
}
void search(int x,int num) // 搜索函数
{
int i;
if(num>=8) { output(); return ;}
if(x==inix-1) search(inix,num+1);
else
{
for(i=0;i<8;i++)
{
if(check(x,i))
{
board[x][i]=1;
search(x+1,num+1);
board[x][i]=0;
}
}
}
return ;
}
int main()
{
scanf("%d %d",&inix,&iniy);
board[inix-1][iniy-1] = 1 ;
search(0,0);
printf("%d\n",num);
return 0;
}
例如:
输入 : 1 1
输出 :
◆ ■ ■ ■ ■ ■ ■ ■
■ ■ ■ ■ ◆ ■ ■ ■
■ ■ ■ ■ ■ ■ ■ ◆
■ ■ ■ ■ ■ ◆ ■ ■
■ ■ ◆ ■ ■ ■ ■ ■
■ ■ ■ ■ ■ ■ ◆ ■
■ ◆ ■ ■ ■ ■ ■ ■
■ ■ ■ ◆ ■ ■ ■ ■
◆ ■ ■ ■ ■ ■ ■ ■
■ ■ ■ ■ ■ ◆ ■ ■
■ ■ ■ ■ ■ ■ ■ ◆
■ ■ ◆ ■ ■ ■ ■ ■
■ ■ ■ ■ ■ ■ ◆ ■
■ ■ ■ ◆ ■ ■ ■ ■
■ ◆ ■ ■ ■ ■ ■ ■
■ ■ ■ ■ ◆ ■ ■ ■
◆ ■ ■ ■ ■ ■ ■ ■
■ ■ ■ ■ ■ ■ ◆ ■
■ ■ ■ ◆ ■ ■ ■ ■
■ ■ ■ ■ ■ ◆ ■ ■
■ ■ ■ ■ ■ ■ ■ ◆
■ ◆ ■ ■ ■ ■ ■ ■
■ ■ ■ ■ ◆ ■ ■ ■
■ ■ ◆ ■ ■ ■ ■ ■
◆ ■ ■ ■ ■ ■ ■ ■
■ ■ ■ ■ ■ ■ ◆ ■
■ ■ ■ ■ ◆ ■ ■ ■
■ ■ ■ ■ ■ ■ ■ ◆
■ ◆ ■ ■ ■ ■ ■ ■
■ ■ ■ ◆ ■ ■ ■ ■
■ ■ ■ ■ ■ ◆ ■ ■
■ ■ ◆ ■ ■ ■ ■ ■
4
㈡ 求教C语言回溯法写出八皇后问题的92种解
(1)全排列
将自然数1~n进行排列，共形成n!中排列方式，叫做全排列。
例如3的全排列是：1/2/3、1/3/2、2/1/3、2/3/1、3/1/2、3/2/1，共3!=6种。
(2)8皇后（或者n皇后）
保证8个皇后不能互相攻击，即保证每一横行、每一竖行、每一斜行最多一个皇后。
我们撇开第三个条件，如果每一横行、每一竖行都只有一个皇后。
将8*8棋盘标上坐标。我们讨论其中的一种解法：
- - - - - - - Q
- - - Q - - - -
Q - - - - - - -
- - Q - - - - -
- - - - - Q - -
- Q - - - - - -
- - - - - - Q -
- - - - Q - - -
如果用坐标表示就是：(1,8) (2,4) (3,1) (4,3) (5,6) (6,2) (7,7) (8,5)
将横坐标按次序排列，纵坐标就是8/4/1/3/6/2/7/5。这就是1~8的一个全排列。
我们将1~8的全排列存入输入a[]中(a[0]~a[7])，然后8个皇后的坐标就是(i+1,a[i])，其中i为0~7。
这样就能保证任意两个不会同一行、同一列了。
置于斜行，你知道的，两个点之间连线的斜率绝对值为1或者-1即为同一斜行，充要条件是|x1-x2|=|y1-y2|（两个点的坐标为（x1,y1）(x2,y2)）。我们在输出的时候进行判断，任意两个点如果满足上述等式，则判为失败，不输出。
下面附上代码：添加必要的注释，其中全排列的实现看看注释应该可以看懂：
#include<stdio.h>
#include<math.h>
#include<string.h>
#include<stdlib.h>
intprinted;
//该函数用于画图，这里为了节约空间则略去
//读者只需要将draw(a,k);去掉注释即可画图
voiddraw(int*a,intk)
{
inti,j;
for(i=0;i<k;i++)
{
printf(" ");
for(j=0;j<k;j++)
//有皇后输出Q，否则输出-
if(a[i]-1==j)printf("Q");elseprintf("-");
printf(" ");
}
printf(" ");
}
//递归实现全排列,a是数组，iStep是位置的测试点，k是皇后的个数，一般等于8
voidSettle(int*a,intiStep,intk)
{
inti,j,l,flag=1;
//如果iStep的数字等于a之前的数字，则存在重复，返回
for(i=0;i<iStep-1;i++)
if(a[iStep-1]==a[i])return;
//如果iStep==k，即递归结束到最后一位，可以验证是否斜行满足
if(iStep==k)
{
//双重循环判断是否斜行满足
for(j=0;j<k;j++)
for(l=0;l<k&&l!=j;l++)
//如果不满足，则flag=0
if(fabs(j-l)==fabs(a[j]-a[l]))flag=0;
//如果flag==1，则通过了斜行的所有测试，输出。
if(flag)
{
for(i=0;i<k;i++)
printf("(%d,%d)",i+1,a[i]);
printf(" ");
//如果去掉这里的注释可以获得画图，由于空间不够，这里略去
// draw(a,k);
//printed变量计算有多少满足题意的结果，是全局变量
printed++;
}
flag=1;
}
//如果未测试至最后末尾，则测试下一位（递归）
for(i=1;i<=k;i++)
{
a[iStep]=i;
Settle(a,iStep+1,k);
}
}
voidmain()
{
int*a;
intk;
//输入维数，建立数组
printf("Enterthesizeofthesquare:");
scanf("%d",&k);
a=(int*)calloc(k,sizeof(int));
//清屏，从iStep=0处进入递归
system("cls");
Settle(a,0,k);
//判断最后是否有结果
if(!printed)printf("Noanswersaccepted! ");
elseprintf("%dstatesavailable! ",printed);
}
附输出结果（输入k=8）：
(1,1)(2,5)(3,8)(4,6)(5,3)(6,7)(7,2)(8,4)
(1,1)(2,6)(3,8)(4,3)(5,7)(6,4)(7,2)(8,5)
(1,1)(2,7)(3,4)(4,6)(5,8)(6,2)(7,5)(8,3)
(1,1)(2,7)(3,5)(4,8)(5,2)(6,4)(7,6)(8,3)
(1,2)(2,4)(3,6)(4,8)(5,3)(6,1)(7,7)(8,5)
(1,2)(2,5)(3,7)(4,1)(5,3)(6,8)(7,6)(8,4)
(1,2)(2,5)(3,7)(4,4)(5,1)(6,8)(7,6)(8,3)
(1,2)(2,6)(3,1)(4,7)(5,4)(6,8)(7,3)(8,5)
(1,2)(2,6)(3,8)(4,3)(5,1)(6,4)(7,7)(8,5)
(1,2)(2,7)(3,3)(4,6)(5,8)(6,5)(7,1)(8,4)
(1,2)(2,7)(3,5)(4,8)(5,1)(6,4)(7,6)(8,3)
(1,2)(2,8)(3,6)(4,1)(5,3)(6,5)(7,7)(8,4)
(1,3)(2,1)(3,7)(4,5)(5,8)(6,2)(7,4)(8,6)
(1,3)(2,5)(3,2)(4,8)(5,1)(6,7)(7,4)(8,6)
(1,3)(2,5)(3,2)(4,8)(5,6)(6,4)(7,7)(8,1)
(1,3)(2,5)(3,7)(4,1)(5,4)(6,2)(7,8)(8,6)
(1,3)(2,5)(3,8)(4,4)(5,1)(6,7)(7,2)(8,6)
(1,3)(2,6)(3,2)(4,5)(5,8)(6,1)(7,7)(8,4)
(1,3)(2,6)(3,2)(4,7)(5,1)(6,4)(7,8)(8,5)
(1,3)(2,6)(3,2)(4,7)(5,5)(6,1)(7,8)(8,4)
(1,3)(2,6)(3,4)(4,1)(5,8)(6,5)(7,7)(8,2)
(1,3)(2,6)(3,4)(4,2)(5,8)(6,5)(7,7)(8,1)
(1,3)(2,6)(3,8)(4,1)(5,4)(6,7)(7,5)(8,2)
(1,3)(2,6)(3,8)(4,1)(5,5)(6,7)(7,2)(8,4)
(1,3)(2,6)(3,8)(4,2)(5,4)(6,1)(7,7)(8,5)
(1,3)(2,7)(3,2)(4,8)(5,5)(6,1)(7,4)(8,6)
(1,3)(2,7)(3,2)(4,8)(5,6)(6,4)(7,1)(8,5)
(1,3)(2,8)(3,4)(4,7)(5,1)(6,6)(7,2)(8,5)
(1,4)(2,1)(3,5)(4,8)(5,2)(6,7)(7,3)(8,6)
(1,4)(2,1)(3,5)(4,8)(5,6)(6,3)(7,7)(8,2)
(1,4)(2,2)(3,5)(4,8)(5,6)(6,1)(7,3)(8,7)
(1,4)(2,2)(3,7)(4,3)(5,6)(6,8)(7,1)(8,5)
(1,4)(2,2)(3,7)(4,3)(5,6)(6,8)(7,5)(8,1)
(1,4)(2,2)(3,7)(4,5)(5,1)(6,8)(7,6)(8,3)
(1,4)(2,2)(3,8)(4,5)(5,7)(6,1)(7,3)(8,6)
(1,4)(2,2)(3,8)(4,6)(5,1)(6,3)(7,5)(8,7)
(1,4)(2,6)(3,1)(4,5)(5,2)(6,8)(7,3)(8,7)
(1,4)(2,6)(3,8)(4,2)(5,7)(6,1)(7,3)(8,5)
(1,4)(2,6)(3,8)(4,3)(5,1)(6,7)(7,5)(8,2)
(1,4)(2,7)(3,1)(4,8)(5,5)(6,2)(7,6)(8,3)
(1,4)(2,7)(3,3)(4,8)(5,2)(6,5)(7,1)(8,6)
(1,4)(2,7)(3,5)(4,2)(5,6)(6,1)(7,3)(8,8)
(1,4)(2,7)(3,5)(4,3)(5,1)(6,6)(7,8)(8,2)
(1,4)(2,8)(3,1)(4,3)(5,6)(6,2)(7,7)(8,5)
(1,4)(2,8)(3,1)(4,5)(5,7)(6,2)(7,6)(8,3)
(1,4)(2,8)(3,5)(4,3)(5,1)(6,7)(7,2)(8,6)
(1,5)(2,1)(3,4)(4,6)(5,8)(6,2)(7,7)(8,3)
(1,5)(2,1)(3,8)(4,4)(5,2)(6,7)(7,3)(8,6)
(1,5)(2,1)(3,8)(4,6)(5,3)(6,7)(7,2)(8,4)
(1,5)(2,2)(3,4)(4,6)(5,8)(6,3)(7,1)(8,7)
(1,5)(2,2)(3,4)(4,7)(5,3)(6,8)(7,6)(8,1)
(1,5)(2,2)(3,6)(4,1)(5,7)(6,4)(7,8)(8,3)
(1,5)(2,2)(3,8)(4,1)(5,4)(6,7)(7,3)(8,6)
(1,5)(2,3)(3,1)(4,6)(5,8)(6,2)(7,4)(8,7)
(1,5)(2,3)(3,1)(4,7)(5,2)(6,8)(7,6)(8,4)
(1,5)(2,3)(3,8)(4,4)(5,7)(6,1)(7,6)(8,2)
(1,5)(2,7)(3,1)(4,3)(5,8)(6,6)(7,4)(8,2)
(1,5)(2,7)(3,1)(4,4)(5,2)(6,8)(7,6)(8,3)
(1,5)(2,7)(3,2)(4,4)(5,8)(6,1)(7,3)(8,6)
(1,5)(2,7)(3,2)(4,6)(5,3)(6,1)(7,4)(8,8)
(1,5)(2,7)(3,2)(4,6)(5,3)(6,1)(7,8)(8,4)
(1,5)(2,7)(3,4)(4,1)(5,3)(6,8)(7,6)(8,2)
(1,5)(2,8)(3,4)(4,1)(5,3)(6,6)(7,2)(8,7)
(1,5)(2,8)(3,4)(4,1)(5,7)(6,2)(7,6)(8,3)
(1,6)(2,1)(3,5)(4,2)(5,8)(6,3)(7,7)(8,4)
(1,6)(2,2)(3,7)(4,1)(5,3)(6,5)(7,8)(8,4)
(1,6)(2,2)(3,7)(4,1)(5,4)(6,8)(7,5)(8,3)
(1,6)(2,3)(3,1)(4,7)(5,5)(6,8)(7,2)(8,4)
(1,6)(2,3)(3,1)(4,8)(5,4)(6,2)(7,7)(8,5)
(1,6)(2,3)(3,1)(4,8)(5,5)(6,2)(7,4)(8,7)
(1,6)(2,3)(3,5)(4,7)(5,1)(6,4)(7,2)(8,8)
(1,6)(2,3)(3,5)(4,8)(5,1)(6,4)(7,2)(8,7)
(1,6)(2,3)(3,7)(4,2)(5,4)(6,8)(7,1)(8,5)
(1,6)(2,3)(3,7)(4,2)(5,8)(6,5)(7,1)(8,4)
(1,6)(2,3)(3,7)(4,4)(5,1)(6,8)(7,2)(8,5)
(1,6)(2,4)(3,1)(4,5)(5,8)(6,2)(7,7)(8,3)
(1,6)(2,4)(3,2)(4,8)(5,5)(6,7)(7,1)(8,3)
(1,6)(2,4)(3,7)(4,1)(5,3)(6,5)(7,2)(8,8)
(1,6)(2,4)(3,7)(4,1)(5,8)(6,2)(7,5)(8,3)
(1,6)(2,8)(3,2)(4,4)(5,1)(6,7)(7,5)(8,3)
(1,7)(2,1)(3,3)(4,8)(5,6)(6,4)(7,2)(8,5)
(1,7)(2,2)(3,4)(4,1)(5,8)(6,5)(7,3)(8,6)
(1,7)(2,2)(3,6)(4,3)(5,1)(6,4)(7,8)(8,5)
(1,7)(2,3)(3,1)(4,6)(5,8)(6,5)(7,2)(8,4)
(1,7)(2,3)(3,8)(4,2)(5,5)(6,1)(7,6)(8,4)
(1,7)(2,4)(3,2)(4,5)(5,8)(6,1)(7,3)(8,6)
(1,7)(2,4)(3,2)(4,8)(5,6)(6,1)(7,3)(8,5)
(1,7)(2,5)(3,3)(4,1)(5,6)(6,8)(7,2)(8,4)
(1,8)(2,2)(3,4)(4,1)(5,7)(6,5)(7,3)(8,6)
(1,8)(2,2)(3,5)(4,3)(5,1)(6,7)(7,4)(8,6)
(1,8)(2,3)(3,1)(4,6)(5,2)(6,5)(7,7)(8,4)
(1,8)(2,4)(3,1)(4,3)(5,6)(6,2)(7,7)(8,5)
92statesavailable!
㈢ 用C语言编写八皇后问题
如下是8皇后的程序：
#include<stdio.h>
#include<stdlib.h>
void eightqueen(int a[][99],int n);
void print(int a[][99]);
int up(int a[][99],int row,int col);
int down(int a[][99],int row,int col);
int left(int a[][99],int row,int col);
int right(int a[][99],int row,int col);
int num=0;
main()
{
int a[99][99]={0},n; //将皇后的位置放在一个二维的数组里面，a[i][j]=1表示该位置有一个皇后
eightqueen(a,0);
system("pause");
return 0;
}
void print(int a[][99]) //输出当前的一种合理的走法。
{
int i,row,col;
printf("Case %d\n",num);
for(row=0;row<8;row++)
{
for(col=0;col<8;col++)
{
printf("%d ",a[row][col]);
}
printf("\n");
}
printf("\n");
}
void eightqueen(int a[][99],int row) //通过回溯法计算8皇后的走法。
{
int col,i;
for(col=0;col<=7;col++)
{
//判断都前位置是否是合理的位置。
if ((up(a,row,col)==0)&&(down(a,row,col)==0)&&(left(a,row,col)==0)&&(right(a,row,col)==0))
{
a[row][col]=1; //如果是，将当前位置置为1（摆放一个皇后）
if(row==7) //所有的8个皇后都已经摆放好了，输出当前的情况。
{
num++;
print(a);
}
else
{
eightqueen(a,row+1); //在row+1摆放下一个皇后。
}
a[row][col]=0;
}
}
}
//判断同一行列是否有其他的皇后
int up(int a[][99],int row,int col)
{
int i;
for(i=0;i<8;i++)
{
if(a[i][col]==1)
{
return 1;
}
}
return 0;
}
//判断同一行上是否有其他的皇后
int down(int a[][99],int row,int col)
{
int i;
for(i=0;i<8;i++)
{
if(a[row][i]==1)
{
return 1;
}
}
return 0;
}
//判断左上到右下的对接线上是否有其他的皇后
int left(int a[][99],int row,int col)
{
int i;
for(i=0;i<8;i++)
{
if(((row+i)<8)&&((col+i)<8))
{
if(a[row+i][col+i]==1)
{
return 1;
}
}
if(((row-i)>=0)&&((col-i)>=0))
{
if(a[row-i][col-i]==1)
{
return 1;
}
}
}
return 0;
}
//判断左下到右上的对接线上是否有其他的皇后
int right(int a[][99],int row,int col)
{
int i;
for(i=0;i<8;i++)
{
if(((row+i)<8)&&((col-i)>=0)) //
{
if(a[row+i][col-i]==1)
{
return 1;
}
}
if(((row-i)>=0)&&((col+i)<8)) //这儿的判断有问题，
{
if(a[row-i][col+i]==1)
{
return 1;
}
}
}
return 0;
}