c语言八皇后
⑴ C语言八皇后问题中怎样判断满足行列斜线没有棋子的条件
算法分析：数组a、b、c分别用来标记冲突，a数组代表列冲突，从a[0]~a[7]代表第0列到第7列，如果某列上已经有皇后，则为1，否则为0；
数组b代表主对角线冲突，为b[i-j+7]，即从b[0]~b[14]，如果某条主对角线上已经有皇后，则为1，否则为0；
数组c代表从对角线冲突，为c[i+j]，即从c[0]~c[14]，如果某条从对角线上已经有皇后，则为1，否则为0；
＃include
"stdio.h"
static
char
Queen[8][8];
static
int
a[8];
static
int
b[15];
static
int
c[15];
static
int
iQueenNum=0;
//记录总的棋盘状态数
void
qu(int
i);
//参数i代表行
int
main()
{
int
iLine,iColumn;
//棋盘初始化，空格为*，放置皇后的地方为@
for(iLine=0;iLine<8;iLine++)
{
a[iLine]=0;
//列标记初始化，表示无列冲突
for(iColumn=0;iColumn<8;iColumn++)
Queen[iLine][iColumn]='*';
}
//主、从对角线标记初始化，表示没有冲突
for(iLine=0;iLine<15;iLine++)
b[iLine]=c[iLine]=0;
qu(0);
return
0;
}
void
qu(int
i)
{
int
iColumn;
for(iColumn=0;iColumn<8;iColumn++)
{
if(a[iColumn]==0&&b[i-iColumn+7]==0&&c[i+iColumn]==0)
//如果无冲突
{
Queen[iColumn]='@';
//放皇后
a[iColumn]=1;
//标记，下一次该列上不能放皇后
b[i-iColumn+7]=1;
//标记，下一次该主对角线上不能放皇后
c[i+iColumn]=1;
//标记，下一次该从对角线上不能放皇后
if(i<7)
qu(i+1);
//如果行还没有遍历完，进入下一行
else
//否则输出
{
//输出棋盘状态
int
iLine,iColumn;
printf("第%d种状态为：\n",++iQueenNum);
for(iLine=0;iLine<8;iLine++)
{
for(iColumn=0;iColumn<8;iColumn++)
printf("%c
",Queen[iLine][iColumn]);
printf("\n"screen.width/2)this.width=screen.width/2"
vspace=2
border=0>;
}
printf("\n\n"screen.width/2)this.width=screen.width/2"
vspace=2
border=0>;
}
//如果前次的皇后放置导致后面的放置无论如何都不能满足要求，则回溯，重置
Queen[iColumn]='*';
a[iColumn]=0;
b[i-iColumn+7]=0;
c[i+iColumn]=0;
}
}
}
⑵ 八皇后问题的C语言代码
#include <math.h>
#include <stdio.h>
#define MAX 8 /* 棋子数及棋盘大小MAXxMAX */
int board[MAX];
/* 印出结果 */
void show_result()
{
int i;
for(i=0;i<MAX;i++)
printf("(%d,%d)",i,board[i]);
printf("\n");
}
/* 检查是否在同一直横斜线上有其它棋子 */
int check_cross(int n)
{
int i;
for(i=0;i<n;i++){
if(board[i]==board[n] || (n-i)==abs(board[i]-board[n]))return 1;
}
return 0;
}
/* 放棋子到棋盘上 */
void put_chess(int n)
{
int i;
for(i=0;i<MAX;i++){
board[n]=i;
if(!check_cross(n)){
if(n==MAX-1) show_result();/* 找到其中一种放法了...印出结果 */
else put_chess(n+1);
}
}
}
void main()
{
clrscr();
puts("The possible placements are:");
put_chess(0);
puts("\n Press any key to quit...");
getch();
return;
}
到底是哪些奇葩老师布置的作业？
⑶ 用C语言编写八皇后问题
#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 = 0; j < k; j ++)
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 = 0; i < N; i ++) {
x[t] = i;
if (place(t)) backtrack(t + 1);
}
}
void chessboard()
{
printf("第%d种解法:\n", ++ sum);
for (int i = 0; i < N; i ++) {
for (int j = 0; j < N; j ++)
if (j == x[i]) printf("@ ");
else printf("* ");
printf("\n");
}
printf("\n");
}
⑷ 八皇后c++源码讲解
回溯法:八皇后问题，一个经典问题
在程序设计中还有一种方法叫做"回溯法".他不是按照某种公式或确定的法则,求问题的解,而是通过试探和纠正错误的策略,找到问题的街.这种方法一般是从一个原始状态出发,通过若干步试探,最后达到目标状态终止.
回溯法在理论上来说,就是在一棵搜索树中从根结点出发,找到一条达到满足某条件的子结点的路径.在搜索过程中,对于每一个中间结点,他的位置以及向下搜索过程是相似的,因此完全可以用递归来处理.典型的例子就是着名的"八皇后问题".
"八皇后问题"是在国际象棋棋盘上放置八个皇后,使她们不能相吃.国际象棋中的皇后可以吃掉与她处于同一行,同一列,同一对角线上的棋子.因此每一行只能摆放一个皇后.因共有八行,所以每行有且只有一个皇后.
在本例中皇后的位置有一个一维数组来存放A(I)=J表示第I行皇后放在第J列.下面主要来看看怎么样判断皇后是否安全的问题.(1)首先,用一维数组来表示,已经解决了不在同一行的问题.(2)对于列可以引进一个标志数组C[J],若J列上已放了皇后,则C[J]=FALSE.(3)对于左上右下的对角线I-J为一常量,位于[-7,+7]之间,再此引入标志数组L[-7..7];对于左下右上的对角线,类似的有I+J等于常量,用数组R[2..16]来表示.当在第I行,第J列上放置了皇后,则只需设置:C[J]:=FALSE; L[I-J]:=FLASE; R[I+J]:=FALSE就可以解决皇后的安全问题了.
问题描述：在标准国际象棋的棋盘上（8*8格）准备放置8只皇后，我们知道，国际象棋中皇后的威力是最大的，她既可以横走竖走，还可以斜着走，遇到挡在她前进路线上的敌人，她就可以吃掉对手。要求在棋盘上安放8只皇后，使她们彼此互相都不能吃到对方，求皇后的放法。
/************************************************************************/
/* */
/* 问题：在8×8的国际象棋棋盘上放置8个皇后，要求任意两个皇后 */
/* 不能在同一行、同一列或同一条对角线上。 */
/* */
/* 本程序使用递归－回溯法求解8皇后问题。Visual C++ 6.0 调试通过。 */
/* 作者 晨星 2002年5月9日 */
/* */
/************************************************************************/
#include <stdio.h>
#include <conio.h>
#include <math.h>
#define QUEENS 8
//!记录解的序号的全局变量。
int iCount = 0;
//!记录皇后在各列上的放置位置的全局数组。
int Site[QUEENS];
//!递归求解的函数。
void Queen(int n);
//!输出一个解。
void Output();
//!判断第n个皇后放上去之后，是否有冲突。
int IsValid(int n);
/*----------------------------Main：主函数。 ----------------------------*/
void main()
{
//!从第0列开始递归试探。
Queen(0);
//!按任意键返回。
getch();
}
/*-----------------Queen：递归放置第n个皇后，程序的核心!----------------*/
void Queen(int n)
{
int i;
//!参数n从0开始，等于8时便试出了一个解，将它输出并回溯。
if(n == QUEENS)
{
Output();
return;
}
//!n还没到8，在第n列的各个行上依次试探。
for(i = 1 ; i <= QUEENS ; i++)
{
//!在该列的第i行上放置皇后。
Site[n] = i;
//!如果放置没有冲突，就开始下一列的试探。
if(IsValid(n))
Queen(n + 1);
}
}
/*------IsValid：判断第n个皇后放上去之后，是否合法，即是否无冲突。------*/
int IsValid(int n)
{
int i;
//!将第n个皇后的位置依次于前面n－1个皇后的位置比较。
for(i = 0 ; i < n ; i++)
{
//!两个皇后在同一行上，返回0。
if(Site[i] == Site[n])
return 0;
//!两个皇后在同一对角线上，返回0。
if(abs(Site[i] - Site[n]) == (n - i))
return 0;
}
//!没有冲突，返回1。
return 1;
}
/*------------Output：输出一个解，即一种没有冲突的放置方案。------------*/
void Output()
{
int i;
//!输出序号。
printf("No.%-5d" , ++iCount);
//!依次输出各个列上的皇后的位置，即所在的行数。
for(i = 0 ; i < QUEENS ; i++)
printf("%d " , Site[i]);
printf("n");
}
STL源代码
用了STL, 方法是一样的.
#include <iostream>
#include <string>
using namespace std;
void queen(const string t, const string s)
{
if (s=="") cout<<t<<endl;
else
for (int i=0; i<s.length(); i++) {
bool safe=true;
for (int j=0;j<t.length();j++) {
if (t.length()-j==abs(s[i]-t[j])) safe=false;
}
if (safe) queen(t+s[i], s.substr(0,i)+s.substr(i+1));
}
}
int main()
{
string s="01234567";
queen("",s);
system("PAUSE");
exit(EXIT_SUCCESS);
}
递归解八皇后问题
/*递归法解八皇后问题*/
/*作者黄国瑜，《数据结构（C语言版）》清华大学出版社*/
char Chessboard[8][8]; /*声明8＊8的空白棋盘*/
int N_Queens(int LocX, int LocY, int Queens) /*递归*/
{
int i,j;
int Result=0;
if(Queens == 8)/*递归结束条件*/
return 1;
else if(QueenPlace(LocX,LocY))/*递归执行部分*/
{
Chessboard[LocX][LocY] = 'Q';
for(i=0;i<8;i++)
for(j=0;j<8;j++)
{
Result += N_Queens(i,j,Queens+1);
if(Result>0)
break;
}
if(Result>0)
return 1;
else
{
Chessboard[LocX][LocY] = 'X';
}
}
else
return 0;
}
int QueenPlace(int LocX,int LocY) /*判断传入坐标本身及入八个方向上是否有皇后*/
{
int i,j;
if(Chessboard[LocX][LocY] != 'X')
return 0;
for(j=LocY-1;j>=0;j--)
if(Chessboard[LocX][j] != 'X')
return 0;
for(j=LocY+1;j<8;j++)
if(Chessboard[LocX][j] != 'X')
return 0;
for(i=LocX-1;i>=0;i--)
if(Chessboard[i][LocY] != 'X')
return 0;
for(i=LocX+1;i<8;i++)
if(Chessboard[i][LocY] != 'X')
return 0;
i= LocX - 1;
j= LocY - 1;
while (i>=0&&j>=0)
if(Chessboard[i--][j--] != 'X')
return 0;
i= LocX + 1;
j= LocY - 1;
while (i<8&&j>=0)
if(Chessboard[i++][j--] != 'X')
return 0;
i= LocX - 1;
j= LocY + 1;
while (i>=0&&j<8)
if(Chessboard[i--][j++] != 'X')
return 0;
i= LocX + 1;
j= LocY + 1;
while (i<8&&j<8)
if(Chessboard[i++][j--] != 'X')
return 0;
return 1;
}
main() /*主程序*/
{
int i,j;
for(i=0;i<8;i++)
for(j=0;j<8;j++)
Chessboard[i][j] = 'X';
N_Queens(0,0,0);
printf("the graph of 8 Queens on the Chessboard.is:n");
for(i=0;i<8;i++)
for(j=0;j<8;j++)
{
if(Chessboard[i][j] == 'Q')
printf("(%d,%d)n",i,j);
}
getch();
}
/*********************************************************
*****************八皇后问题*******************************
************根据严书给的类c算法求得************************
*********************************************************/
#include<stdio.h>
#define N 8
int col=1,row=1,slash=1,bslash=1;
int a[N][N];
int p,q,k,l;
int num=0;
void trial(int i)
{
int j; /*注 意，这里的j 一定要设为内部变量*/
if(i==N)
{
num++;
for(k=0;k<N;k++)
{
for(l=0;l<N;l++)
{
if(a[k][l]==1)
printf("@");
else printf("*");
}
printf("n");
}
printf("nn");
getchar();
}
else
{
for(j=0;j<N;j++)
{
for(k=0;k<i;k++)
if(a[k][j]==1)
{
col=0;
break;
} /*列*/
p=i-1;
q=j+1;
while((p>=0)&&(q<N))
{
if(a[p][q]==1)
{
slash=0;
break;
}
p--;
q++;
}
p=i-1;
q=j-1; /*对角*/
while((p>=0)&&(q>=0))
{
if(a[p][q]==1)
{
bslash=0;
break;
}
p--;
q--;
} /*斜对角*/
if((col==1)&&(slash==1)&&(bslash==1)) /*条件判断*/
{
a[i][j]=1;
trial(i+1);
}
col=1;slash=1;bslash=1;
a[i][j]=0;
}
}
}
void main()
{
trial(0);
printf("%dn",num);
getchar();
}
⑸ 求教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语言编写八皇后问题
#include "stdio.h" x0dx0a#include "windows.h" x0dx0a#define N 8 /* 定义棋盘大小 */ x0dx0aint place(int k); /* 确定某一位置皇后放置与否，放置则返回1，反之返回0 */ x0dx0avoid backtrack(int i);/* 主递归函数，搜索解空间中第i层子树 */ x0dx0avoid chessboard(); /* 每找到一个解,打印当前棋盘状态 */ x0dx0astatic int sum, /* 当前已找到解的个数 */ x0dx0ax[N]; /* 记录皇后的位置,x[i]表示皇后i放在棋盘的第i行的第x[i]列 */ x0dx0aint main(void) x0dx0a{ x0dx0abacktrack(0); x0dx0asystem("pause"); x0dx0areturn 0; x0dx0a} x0dx0aint place(int k) x0dx0a{ x0dx0a/* 测试皇后k在第k行第x[k]列时是否与前面已放置好的皇后相攻击。 x[j] == */ x0dx0a/* x[k] 时，两皇后在同一列上；abs(k - j) == abs(x[j] - x[k]) 时，两皇 */ x0dx0a/* 后在同一斜线上。两种情况两皇后都可相互攻击，故返回0表示不符合条件。*/ x0dx0afor (int j = 0; j < k; j ++) x0dx0aif (abs(k - j) == abs(x[j] - x[k]) || (x[j] == x[k])) return 0; x0dx0areturn 1; x0dx0a} x0dx0avoid backtrack(int t) x0dx0a{ x0dx0a/* t == N 时，算法搜索至叶结点，得到一个新的N皇后互不攻击的放置方案 */ x0dx0aif (t == N) chessboard(); x0dx0aelse x0dx0afor (int i = 0; i < N; i ++) { x0dx0ax[t] = i; x0dx0aif (place(t)) backtrack(t + 1); x0dx0a} x0dx0a} x0dx0avoid chessboard() x0dx0a{ x0dx0aprintf("第%d种解法:\n", ++ sum); x0dx0afor (int i = 0; i < N; i ++) { x0dx0afor (int j = 0; j < N; j ++) x0dx0aif (j == x[i]) printf("@ "); x0dx0aelse printf("* "); x0dx0aprintf("\n"); x0dx0a} x0dx0aprintf("\n"); x0dx0a}
⑺ C语言DFS八皇后问题，输出结果重复
重复输出是因为
for(int
i
=
0;
i
<
n;
i
++)
dfs(0,i);
由于在dfs内部，已经对当前行进行过遍历，在主函数只需用调用一次dfs(0,0)即可
而当5的时候，为什么会出错，具体原因不清楚
但根据调试发现，无法处理对角线间隔多行的情况，特别是第二个输出就错了，问题在往上返回的过程中，左下角位置本来是-1，变成了0，这种情况应该是在恢复地图时错误
⑻ 八皇后问题求解的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