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我