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