八皇後問題c語言
㈠ 如何用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語言代碼
#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語言程序的實現
這是個前不久,我為別人寫的一個代碼;
八皇後問題共有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
㈣ 用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程序設計教程》。。。
㈤ 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 "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語言編寫8皇後問題
#include "stdafx.h"
#include "stdio.h"
#include "malloc.h"
#define MAX 8
static int Queen[8][8];
static int a=1;
typedef struct
{
int *elem;
int top;
}ColStack;//棧：存放每一行放置皇後的列號
void InitQueen()
{
int i,j;
for(i = 0; i < 8; i++)
{
for(j = 0; j < 8; j++)
{
Queen[i][j] = 0;
}
}
}
int InitStack(ColStack &CS)//初始化棧
{
CS.elem = (int *)malloc(MAX*sizeof(int));
if(!CS.elem) return 0;
CS.top = -1;
return 1;
}
int Push(ColStack &CS, int e)//進棧
{
if(CS.top >= 8) return 0;
CS.top++;
CS.elem[CS.top] = e;
return 1;
}
int Pop(ColStack &CS, int &e)//退棧
{
if(CS.top == -1)return 0;
e = CS.elem[CS.top];
CS.top--;
return 1;
}
int Back(ColStack &CS,int &e)//回溯
{
Pop(CS,e);
Queen[CS.top+1][e] = 0;
if(e == 7 && CS.top == -1)
{
return 0;
}
if(e == 7 && CS.top != -1)
{
Back(CS,e);
}
return 1;
}
int OK(int i, int j)//檢查(i,j)上能否放棋子
{
int k, m;
for(k = i; k >= 0; k--)//檢查同列
{
if(Queen[k][j] == 1) return 0;
}
k = i; m = j;
while(k >= 0 && m >= 0)
{
if(Queen[k][m] == 1) return 0;
k--; m--;
}
k = i; m = j;
while(k >= 0 && m < 8)
{
if(Queen[k][m] == 1) return 0;
k--;m++;
}
return 1;
}
//進入本函數時，在8*8棋盤前i-1行已放置了互不攻
// 擊的i-1個棋子。現從第 i 行起繼續為後續棋子選擇
// 滿足約束條件的位置。當求得(i>8)的一個合法布局
// 時，輸出之。
int queen(int i, ColStack &CS, int start)
{
int j, k,e;
if(i>=8)
{
printf("第%d種情況：\n",a);
for(j = 0; j < 8; j++)
{
for(k = 0; k < 8; k++)
{
if(Queen[j][k] == 0)
{
printf("# ");
}
else
{
printf("@ ");
}
}
printf("\n");
}
a++;
}else
{
for(j = start+1; j < 8; j++)
{
if(OK(i,j) == 1)
{
Queen[i][j]=1;
Push(CS,j);
queen(i+1,CS,-1);
return 1;
}
}
}
if(j == 8)
{
if(Back(CS,e) == 1)
{
queen(CS.top+1,CS,e);
}
if(Back(CS,e) == 0)
{
return 1;
}
}
}
int main()
{
InitQueen();
ColStack cs;
InitStack(cs);
queen(0,cs,-1);
return 0;
}
㈧ c語言八皇後
#include "stdio.h"
int count;
int queen [10], column[20],left[20],right[20];
void prt1()
{ int j;
printf("No.%d ",++count);
for (j=1;j<=8;j++) printf("%3d",queen[j]);
printf("\n");
}
void try(int i)
{int j;
for (j=1;j<=8;j++)
if (column[j] && left[i-j+8] && right[i+j])
{ queen[i]=j; column[j]=0;
left[i-j+8]=0; right[i+j]=0;
if (i<8) try(i+1);
else prt1();
column[j]=left[i-j+8]=right[i+j]=1;
}
}
main()
{int i;
for (i=1;i<=16;i++)
column[i]=left[i]=right[i]=1;
count=0; try(1);
}
㈨ c語言編程：八皇後問題
/***八皇後問題**/
#include<stdio.h>
int row[8]= {0}, col[8] = {0};//四個輔助數組用來確定
int right[15] ={0},left[15] = {0};//是否那人能夠放皇後
int sum = 0; //計數器,用來計共有多少組可行解
int X[8]; //用X[i]以及他的值表示皇後的位置
void OutPut()
{
int i,j;
for(i=0;i<=7;i++)
{
for(j=0;j<=7;j++)
{
if(j==X[i])
printf("A");
else
printf(".");
}
printf("\n");
}
}
void NQuene(int m) // 遞歸求解
{
int i = 0 ;
int flag ; // 標志變數
if(m>=8)
{
sum++;
printf("No %d:\n",sum);
OutPut();
}
else
{
for(i=0;i<8;i++)
{
X[m]=i ; //第m行i列
flag= row[m]||col[i]||right[m-i+7]||left[i+m];//flag為1表明此位置不能存放皇後
if(!flag) //標志為0表明可以存放皇後
{
row[m]=1 , col[i]=1; //X[m]=i後相應的位置後
right[m-i+7]=1, left[i+m]=1; //對應的輔助數組的相應位置標記為1
NQuene(m+1);
row[m]=0 , col[i] = 0; //遞歸後釋放相應的數值
right[m-i+7]=0, left[i+m]= 0;
}//if
}//for
}//else
}
void main()
{
int m=0;
NQuene(m);
getch();
}