Question

八皇后问题求解的C语言程序的实现

若为n皇后问题就是在n*n的棋盘上放置n个皇后 。
〔基本要求〕八皇后问题是一个古老的搜索问题，可以用递归算法来实现，在递归过程中，一一测试每一种放法，直到得出全部正确答案为止。
〔实现提示〕定义一个8*8的二维数组（为方便处理，下标范围为1:8为好）；
对数组进行初始化；（全置空）
从n行开始放置第一个皇后（满足一行只有一个皇后的要求）后
对1～8列进行测试；若满足条件则保存皇后所在位置，直到所有皇后放置好；
输出每一个皇后应放置的位置

Answer 1

这是个前不久,我为别人写的一个代码;
八皇后问题共有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

Answer 2

此程序可解决N后问题，但输出效果没有上面的好

#include<iostream.h>

const int N = 20;

void main() {
cout<<"n后问题\n\n";
int n, m, good, col[N+1], a[N+1], b[2*N+1], c[2*N+1], j;
cout<<"n = "; cin>>n;
for(j = 0; j <= n; j++) a[j] = 1;
for(j = 0; j <= 2*n; j++) b[j] = c[j] = 1;
m = col[1] = good = 1; col[0]=0;
do {
if(good) {
if(m == n) {
cout<<"\n 列 行\n";
for(j = 1; j <= n; j++)
cout<<" "<<j<<" "<<col[j]<<endl;;
while(col[m] == n) {
m--;
a[col[m]] = b[m+col[m]] = c[n+m-col[m]] = 1;
}
col[m]++;
}
else { // m==n
a[col[m]] = b[m+col[m]] = c[n+m-col[m]] = 0;
col[++m] = 1;
}
}
else { //good
while(col[m] == n) {
m--;
a[col[m]] = b[m+col[m]] = c[n+m-col[m]] = 1;
}
col[m]++;
} // end good
good = a[col[m]] && b[m+col[m]] && c[n+m-col[m]];
} while(m);
cin>>n;
}

Answer 3

#include<stdio.h>

int q[20];
void Queens(int,int);
int Place(int,int);
void print(int);

int main()
{
int n;

printf("您要求的是几皇后问题？\n");
scanf("%d",&n);
Queens(1,n);

system("pause");
return 0;
}

void Queens(int k,int n)
{
int i;
if(n<k)
print(n);
else{
for(i=1;i<=n;i++)
if(Place(i,k)==1){
q[k]=i;
Queens(k+1,n);
}
}
}

int Place(int i,int k)
{
int j=1;
while(j<k){
if((q[j]==i)||abs(q[j]-i)==abs(j-k))
return 0;
j++;
}
return 1;
}

void print(int n)
{
int i;

for(i=1;i<=n;i++)
printf("<%d,%d>\t",i,q[i]);

printf("\n");
}