A. c語言中8皇後問題--怎麼解決上下兩種方法是否重復
#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");
}
B. 用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;
}
C. c語言n皇後問題
if(i==n-1)執行到了,但是 i 取值有問題,j=0的時候i就增加到5,j>0之後if(i==n-1)就不可能成立了
D. 如何用C語言解決N皇後問題並作出流程圖
#include"iostream"
using namespace std;
const max_board = 13;
class Queen
{
public :
Queen(int size);
bool is_solved() const; //判斷是否已經填滿
void print() const; //列印結果
bool unguarded(int col) const; //判斷是否被鎖定
void insert(int col); //在該位放置皇後
void remove(int col); //移除皇後
// void solve_from(Queen &configuration);
int board_size; //邊界
private :
int count; //已放置皇後的數目
bool queen_square[max_board][max_board]; //棋盤
};
Queen::Queen(int size)
{
if(size<1)
board_size=1;
else
if(size>13)
board_size=13;
else
board_size=size;
count=0;
for(int i=0;i<board_size;i++)
for(int j=0;j<board_size;j++)
{
queen_square[i][j]=false;
}
}
bool Queen::is_solved() const
{
return count==board_size;
}
void Queen::print() const
{
for(int i=0;i<board_size;i++)
{
for(int j=0;j<board_size;j++)
{
cout<<queen_square[i][j]<<' ';
}
cout<<endl;
}
cout<<endl;
}
bool Queen::unguarded(int col) const
{
int i;
bool ok=true;
for(i=0;ok&&i<count;i++)
{
ok=!queen_square[i][col];
}
for(i=1;i<=col&&i<=count&&ok;i++)
{
ok=!queen_square[count-i][col-i];
}
for(i=1;i<board_size-col&&i<=count&&ok;i++)
{
ok=!queen_square[count-i][col+i];
}
return ok;
}
void Queen::insert(int col)
{
queen_square[count++][col]=true;
}
void Queen::remove(int col)
{
queen_square[--count][col]=false;
}
void solve_from(Queen &configuration)
{
if(configuration.is_solved())
configuration.print();
else
for(int col=0;col<configuration.board_size;col++)
if(configuration.unguarded(col))
{
configuration.insert(col);
solve_from(configuration);
configuration.remove(col);
}
}
int main()
{
int n;
cout<<"please input the size:\t";
cin>>n;
Queen queen(n);
solve_from(queen);
return 0;
}
E. C語言中關於4皇後或8皇後問題!
用棧,以及回溯法來做
#include<stdio.h>
#include<math.h>
int place(int b);
int a[10]; //定義棧來記錄皇後位置
int main(void)
{
int n; //輸入
int k; //第k個皇後
int j; //輸出結果用
scanf("%d",&n);
a[1]=0;
k=1; //第一個皇後開始
while(k>0)
{
a[k]=a[k]+1; //第一次是從1開始,以後是退回前一個皇後時這個皇後的位置向後挪一位
while(a[k]<=n&&!place(k)) // 位置合法?
a[k]=a[k]+1; //不合法再向後挪一位
if(a[k]<=n) //位置沒有超過合法位置
{
if(k==n) //全部皇後安放完
{
for(j=1;j<=n;j++)// 輸出位置
printf("%3d",a[j]);
printf("\n");
}
else //還有皇後沒有放
{
k++; //繼續放下一個皇後
a[k]=0; //初始化位置
}
}
else //位置不合法
k--; //退回去,回溯
}
return 0;
F. C語言八皇後問題
解題分析:這個問題是由高斯首先提出的。
解決這一問題的最直接方法是窮舉出所有擺法。我們先用回溯的思想按行遞推出一種合理方案。開始棋盤為空,第一個皇後可以放在第一行的任意一個位置。我們把它試置在(1,1)。這樣,滿足J=1或I=J的格子都不能再放皇後了。第二個皇後置在第二行,J可取3..8中的任意一列,我們先試放在(2,3)。那麼第三行的J可以取4..8,先試(3,4)。以此類推,第四個皇後在(4,2)((4,7),(4,8)也可);然後是(5,6)((5,8)也可);第六行就只有(6,8)這一個位置可選。這時,第七行已沒有空位置可放,說明前面皇後的位置試選得不對。回溯到上一行,由於第六行已沒有其他位置可選擇,只能刪除(6,8)這個皇後,再退到第五行,把(5,6)的皇後移到(5,8)。這樣,第六行又沒有可選位置了,回溯到第四行,把(4,2)移到(4,7)……最後,得出第一種可行方案:(1,1),(2,5),(3,8),(4,6),(5,3),(6,7),(7,2),(8,4)。
我們可以編寫一個程序,讓計算機按上述思路窮舉出所有擺法(網上也很多,搜「八皇後」)。經計算機窮舉,共有92種擺法。其實,這其中只有12種基本擺法,每種基本擺法又可經對稱(水平、豎直、及沿兩對角線翻轉)、旋轉(90、180、270度)等幾何變換得出另外7種。這8種擺法的實質是一樣的。那麼,擺法共應有12*8=96種,為什麼是92種呢?原來,在這12種基本擺法中,有一種是中心對稱圖形!用國際象棋記錄法是:a4,b6,c8,d2,e7,f1,g3,h5.
推而廣之還有所謂「N皇後問題」,即 在N*N的棋盤上,放置N個皇後。4皇後有2個答案,5後有10答,6後有4答,7後有40答,9後有352答,10後有724答。 超級簡單,自己寫的N皇後:(如果你硬要八就將N改為8就行了)源程序如下:
#include<stdio.h>
int q[20];
int count=0;
void print(int n)
{int i;<br>count++;<br>for(i=1;i<=n;i++)<br> {printf("(%d,%d)",i,q[i]);<br> }
printf("\n");
}
int Place(int i,int k)
{int j;<br>j=1;<br>while(j<k)<br> {if((q[j]==i) || abs(q[j]-i)==abs(j-k)) return 0;<br> j++;<br> }
return 1;
}
void Queens(int k,int n)
{int i;<br>if(k>n)<br> print(n);<br>else<br> {for(i=1;i<=n;i++)<br> if(Place(i,k)==1) <br> {q[k]=i;<br> Queens(k+1,n);<br> }
}
}
int main()
{int n;<br>scanf("%d",&n);<br>Queens(1,n);<br>getch();<br>return 0;<br>}
G. 用c語言解決八皇後問題,要求第一個皇後位置用鍵盤輸入,需要詳細代碼和解釋,謝謝、
#include "stdio.h"
#include "math.h"
int row[8];
void arrange(int k)
{
int i,j;
if(k>8){
for(i = 1;i<=8;i++)
printf("%2d\n",row[i]);//k>8時應該輸出各列皇後的行號
return ;
}
for(j = 1;j <=8;j++) //試探第k列的每一個行號
{
for(i = 1;i <k ;i++)
if(row [i] == j || (k-i) == abs(row[i] - j))
break;
if(i>=k) //成立說明第k列的第j行可用,則放置一個皇後
{
row [k] = j;
arrange(k+1); //安排第k+1列至第八列皇後
}
}
}
void main()
{
arrange(1);
}
這是全部八皇後的可能性的代碼,其中主要演算法以及有了,相信你可以自己改出來的,否則直接給你的話就沒有意義了。。。
聲明,這段代碼摘自西南交大《c程序設計教程》。。。