c语言n皇后

A. 求教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!

B. c语言 n皇后 求高手

八皇后问题各种语言版本：
http://ke..com/view/698719.htm
#include<iostream.h>

const int n = 15 ; //15皇后问题.改动n可变成N皇后问题
const int n_sub = n - 1 ;
int queen[n] ; //N个棋子.N对应每一列,如n=0的棋子只下在0列,1下1....类推
bool row[n] ; //棋局的每一行是否有棋,有则为1,无为0 ;
bool passive[2*n-1] ; //斜率为1的斜线方向上是不是有皇后
bool negative[2*n-1] ; //斜率为负1的斜线方向上是不是有皇后.
//之所以用全局变量,因全局数组元素值自动为0

int main()
{
int cur = 0 ;//游标,当前移动的棋子(哪一列的棋子)
bool flag = false ; //当前棋子位置是否合法
queen[0] = -1 ; //第0列棋子准备,因一开始移动的就是第0列棋子
int count = 0 ; //一共有多少种下法 ;
cout<<"============================Starting============================="<<endl ;

while(cur>=0)
{
while(cur>=0 && queen[cur]<n && !flag) //当还不确定当前位置是否可下
{
queen[cur]++ ;
// cout<<"第"<<cur<<"列棋子开始走在第"<<queen[cur]<<"行"<<endl ;
// cin.get() ;
if(queen[cur] >= n) { //如果当前列已经下完(找不到合法位置)
// cout<<"当前行是非法行,当前列棋子走完,没有合法位置,回溯上一列棋子"<<endl ;
// cin.get() ;
queen[cur] = -1 ; //当前列棋子置于准备状态
cur-- ; //回溯到上一列的棋子
if(cur>=0) {
row[queen[cur]] = false ;
passive[queen[cur] + cur] = false ;
negative[n_sub + cur - queen[cur]] = false ;
}
//由于要移下一步,所以回溯棋子原位置所在行应该没有棋子啦.置row[]为false
//并且棋子对应的斜线的标志位passive[cur]和negative[cur]也应该要设为false ;
}
else {
//先判断棋子所在行没有棋子
if(row[queen[cur]] == false) { //当前行没有棋子
// cout<<"棋子"<<cur<<"所在行没有其他棋子,正在检查斜线"<<endl ;
flag = true ; // 暂设为true,或与之前棋子斜交,则再设为false ;
//以下检查当前棋子是否与之前的棋子斜线相交
if( passive[queen[cur] + cur] == true || negative[n_sub + cur - queen[cur]] == true) {
flag = false ;
// cout<<"出现斜线相交,该位置不合法"<<endl ;
}
else
flag = true ;
if(flag) { //没有斜交,位置合法
// cout<<"斜线也没有相交,该位置合法"<<endl ;
if(cur == n-1) //如果是最后一个棋子
{
// cout<<"棋子走完一轮,总走法加1"<<endl ;
count++ ; //总走法加一 ;
}
row[queen[cur]] = true ;// 当前行设为有棋子
passive[queen[cur] + cur] = true ;//当前行正斜率方向有棋子
negative[n_sub + cur - queen[cur]] = true ; //当前行负斜率方向上也有棋子
cur++ ;
if(cur >= n) {
cur-- ;
row[queen[cur]] = false ;
passive[queen[cur] + cur] = false ;
negative[n_sub + cur - queen[cur]] = false ;//原理同回溯
}
flag = false ;
}
}
}//else
}
}
cout<<n<<"皇后问题一共有"<<count<<"种解法"<<endl ;
return 0 ;
}
你自己修改一下吧。

C. N皇后回溯问题 解释下这程序 C语言

#include <stdio.h>

#define DelayTime 20000
#define TopX 10
#define TopY 5

int N;/*此处开始设置几个全局变量 N即代表皇后个数*/
int a[8], b[15], c[15];
int Num = 0;/*Num代表解决方法个数*/
int row;
/******************************************************************************/
void BackTrack (int row)
{
int col;
for (col=1; col<=N; col++)
{
if (a[col-1] + b[row+col-2] + c[row-col+N-1] == 0) /*1，为什么这里要等于0？ if语句里的3个表达式都代表什么呢？*/
{
a[col-1] = 1;
b[row+col-2] = 1;
c[row-col+N-1] = 1;
gotoxy(col*2 + TopX, row + TopY); /* 2，这里的gotoxy（）语句是做什么的？ 仅仅是跳到相应位置，打印Q*/
putch('Q');

if (row < N)
{
BackTrack (row + 1); /* 3，这句什么意思? 递归调用*/
}
else
{
Num++;
gotoxy(40, 9); /* 4，这里又是做什么的？什么用？*/
printf("Num: %d ", Num);
delay(DelayTime); /* 5，这里又有什么用？延迟*/
}

a[col-1] = 0;
b[row+col-2] = 0; /* 6，这个三个表达式怎么又成0了？*/
c[row-col+N-1] = 0;
gotoxy(col*2 + TopX, row + TopY); /* 7，这又是什么用?*/
putch('.');

}
}
}
/********************************************************************************/
void main()
{
int i, j;
clrscr();

gotoxy(1, 10);
printf("Input the number of queen: ");
while(N <= 0 || N > 100)
{
scanf("%d", &N);
if(N > 100) printf("Two huge number, input again:");
if(N <= 0) printf("Can's smaller than 1, again:");
}

clrscr();

for(i=1; i<=N; i++)
{
for(j=1; j<=N; j++)
{
gotoxy(i*2 + TopX, j + TopY); /* 8，这里又是什么用? 将光标移动到指定位置说明：gotoxy（x，y）将光标移动到指定行y和列x。
*/
putch('.');
}
}

BackTrack(1); /* 9，为什么是1呢？不是应该传递的是皇后的数量吗?第一行，N为皇后的数量*/

gotoxy(12, 17); /* 10，这又是什么用？*/
printf ("There are %d kinds of solution.\n", Num);

getch();
}

D. N皇后问题c语言代码不知道哪里有问题，求高手啊！

//以下是我手头有的AC程序
#include<stdio.h>
#include<math.h>
int place(int k,int *X)//检查可不可以放置一个新的皇后
{
int i=1;
while(i<k){
if((X[i]==X[k])||(abs(X[i]-X[k])==abs(i-k)))return 0;
i++;
}
return 1;
}
void Nqueens(int n,int *X)
{
int k=1,i;X[1]=0;
while(k>0){
X[k]=X[k]+1;
while((X[k]<=n)&&(!place(k,X)))X[k]++;
if(X[k]<=n)if(k==n){
for(i=1;i<=n;i++)printf("%-6d",X[i]);
printf("\n");
}
else {k++;X[k]=0;}
else k=k-1;
}
}
int main()
{
int n;
int i;
printf("请输入皇后的个数:");
scanf("%d",&n);
int X[20];
Nqueens(n,X);
}

E. c语言 N皇后问题

q[j] == i表示与上个棋子同列（同行是不可能，不用考虑），还有情况得舍弃的就是斜线，左斜和右斜，)(abs(q[j]-i)==(abs(j-k))))这个就表示与前面的棋子是否在同一斜线，左斜右斜都包括了，你自己写写就能总结出这个式子了，数学计算而已。不懂HI我