八皇后c语言
1. 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);
}
2. 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;
}
}
}
3. C语言八皇后的问题。 需要代码，外加步骤解释。谢谢
#include
<stdlib.h>
#include
<stdio.h>
int
m[8][8]
=
{0};//表示棋盘，初始为0，表示未放置皇后
int
num
=
0;//解数目
//对于棋盘前row-1行已放置好皇后
//检查在第row行、第column列放置一枚皇后是否可行
bool
check(int
row,int
column)
//
1,1
2,1
2,2
2,3
{
if(row==1)
return
true;
int
i,j;
//纵向只能有一枚皇后
for(i=0;i<=row-2;i++)
{
if(m[i][column-1]==1)
return
false;
}
//左上至右下只能有一枚皇后
//
i
=
row-2;
//
j
=
i-(row-column);
//
row
-
2
-
row
+
column
i
=
row
-
2;
j
=
column
-
2;
while(i>=0&&j>=0)
{
if(m[i][j]==1)
return
false;
i--;
j--;
}
//右上至左下只能有一枚皇后
i
=
row-2;
//
j
=
row+column-i-2;
j
=
column;
while(i>=0&&j<=7)
{
if(m[i][j]==1)
return
false;
i--;
j++;
//当已放置8枚皇后，为
}
return
true;
}
//可行解时，输出棋盘
void
output()
{
int
i,j;
num++;
printf("answer
%d:
",num);
for(i=0;i<8;i++)
{
for(j=0;j<8;j++)
printf("%d
",m[i][j]);
printf("
");
}
}
//采用递归函数实现八皇后回溯算法
//该函数求解当棋盘前row-1行已放置好皇后，在第row行放置皇后
void
solve(int
row)
{
int
j;
//考虑在第row行的各列放置皇后
for
(j=0;j<8;j++)
{
//在其中一列放置皇后
m[row-1][j]
=
1;
//
1,0
//检查在该列放置皇后是否可行
if
(check(row,j+1)==true)
{
//若该列可放置皇后，且该列为最后一列，则找到一可行解，输出
if(row==8)
output();
//若该列可放置皇后，则向下一行，继续搜索、求解
else
solve(row+1);
}
//取出该列的皇后，进行回溯，在其他列放置皇后
m[row-1][j]
=
0;
}
}
//主函数
int
main()
{
//求解八皇后问题
solve(1);
return
0;
}
/*
0
1
2
3
4
5
6
7
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
2
0
0
0
0
0
0
0
0
3
0
0
0
0
0
0
0
0
4
0
0
0
0
0
0
0
0
5
0
0
0
0
0
0
0
0
6
0
0
0
0
0
0
0
0
7
0
0
0
0
0
0
0
0
*/
4. 用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");
}
5. 八皇后问题求解的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
6. 八皇后问题的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;
}
到底是哪些奇葩老师布置的作业？
7. c语言编写八皇后问题
#include <stdlib.h>
#include<math.h>
#include<conio.h>
#include<stdio.h>
int N=0;
int a[10][10];
int yp=1;
FILE * fp;
void main()
{
int *pa;
int m,n,f,aa;
int check(),reback();
int prt();
clrscr();
fp=fopen("data.dat","w");
printf("please input the number of queens(4--10):");
scanf("%d",&N);
for(m=0;m<N;m++)
for(n=0;n<N;n++)
a[m][n]=0;
m=0;n=0;aa=0;
do{for(n=0;n<N;n++)
{
f=check(m,n);
if(m==N-1 && f==1){a[m][n]=1; prt();f=0;a[m][n]=0;}
if(f==1){ a[m][n]=1; break;}
if(n==N-1&&f==0)
{
do{
m--;
n=reback(m);
if(m==0 && n==N-1 && aa==1) break;
}while(n>=N-1);
}
}
aa=1;
m++;
if(m>=N)m=0;
}while(m<N &&n<N);
printf("\n\n********IT'S OVER!!********");
fprintf(fp,"\n\n**********IT'S OVER!!*******");
close(fp);
getch();
}
int check(int x1,int y1)
{int a1,b1;
for(a1=0;a1<x1;a1++){
for(b1=0;b1<N;b1++){
if(a[a1][b1]==1){
if(a1==x1||b1==y1) return(0);
if((a1-b1)==(x1-y1)) return(0);
if((a1+b1)==(x1+y1))return(0);
}
}
}
return(1);
}
int reback(int w)
{
int x;
for(x=0;x<N;x++)
if(a[w][x]==1)
{
a[w][x]=0;
return(x);
}
}
int prt()
{int t,y;
clrscr();
printf("\n************ %d **************\n\n",yp);
fprintf(fp,"\n************ %d **************\n\n",yp);
yp++;
for(t=0;t<N;t++){
for(y=0;y<N;y++){
printf("%3d",a[t][y]);
fprintf(fp,"%3d",a[t][y]);
}
printf("\n");
fprintf(fp,"\n");
}
getch();
return(0);
}
8. 如何用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;
}
9. 用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程序设计教程》。。。