八皇后问题,我不会解,会解的告诉我 - 编程论坛

#2

lizhang2006-12-23 19:17

你是新手吗？

#3

lizhang2006-12-23 19:24

wo shu shang you

#4

lzy3406233392006-12-24 09:33

#include "stdafx.h"
#include <stdio.h>
#include <stdlib.h>

#define MAXSIZE 30
#define MARK 'Q'

void initial(void);
void display(void);
void class_1(void);
void class_2(void);
void class_3(void);
void class_4(void);

int n;
char board[MAXSIZE+1][MAXSIZE+1];

void main(void)
{
void (*funct[])() = { class_1, class_2,
class_4, class_3,
class_1, class_2
};
char line[100];

printf("\nOne Solution for N Queens' Problem");
printf("\n==================================");
printf("\n\nBoard Size Please (N > 3) --> ");
gets(line);
n = atoi(line);

if (n > 3) {
initial();
(*funct[n % 6])();
display();
}
else
printf("\nIllegal Board Size.");
}
void initial(void)
{
int i, j;

for (i = 1; i <= n; i++)
for (j = 1; j <= n; j++)
board[i][j] = ' ';
}
#define DRAWGRID (N) { inti;
printf("\n+");
for (i = 1; i <= N; i++) printf("-+"); }

#define DRAWLINE(N, r) { int i; printf("\n|"); for (i = 1; i <= N; i++) printf("%c|", board[r][i]); }

void display(void)
{
int r;

DRAWGRID(n);
for (r = 1; r <= n; r++) {
DRAWLINE(n, r);
DRAWGRID(n);
}
printf("\n");
}
void class_1(void)
{
int i;

for (i = 1; i <= n/2; i++)
board[2*i][i] = board[2*i-1][n/2+i] = MARK;
}
void class_2(void)
{
int i;

for (i = 1; i <= (n-1)/2; i++)
board[2*i][i] = MARK;
for (i = 1; i <= (n+1)/2; i++)
board[2*i-1][(n-1)/2+i] = MARK;
}

void class_3(void)
{
int i;

for (i = 1; i <= (n-3)/2; i++)
board[2*i+2][i] = board[2*i+3][(n-1)/2+i] = MARK;
board[1][n-1] = board[2][(n-2)/2] = board[3][n] = MARK;
}
void class_4(void)
{
int i;

if (n > 8) {
for (i = 1; i <= 3; i++)
board[2*i-1][n/2-2+i] = MARK;
board[2][n] = board[4][1] = board[6][n-1] = MARK;
for (i = 1; i <= n/2 - 3; i++)
board[2*i+5][i+1] = board[2*i+6][n/2+1+i] = MARK;
}
else {
for (i = 1; i <= 4; i++)
board[2*i][i] = MARK;
board[1][6] = board[3][5] = MARK;
board[5][8] = board[7][7] = MARK;
}
}

#5

lsw1112006-12-24 11:49

我是新手,谢谢解答!

#6

wangyasen2006-12-29 17:07

#include<iostream>
using namespace std;
#define QueenNumber 8
int y[QueenNumber]; file://存放行上的哪一列放了皇后
#define display( t) for(int i=0;i<QueenNumber;i++) cout<<"("<<i<<","<<y[i]<<")"<<" "; cout<<endl;
void bs(int x)
{
if(x>=QueenNumber){display(y);return;}
int k,i;
for(k=0;k<QueenNumber;k++)//遍历列
{
for(i=0;i<x;i++)
{
if(k==y[i]||x+k==i+y[i]||x-k==i-y[i]) break;
}
if(i>=x)
{
y[i]=k;
bs(x+1);
}
}
return;
}
int main()
{
bs(0);
return 0;
}
你可以自己再添写输出语句，用Q，#输出，这样一目了然。譬如说，四皇后的问题，如下显示
#Q##
###Q
Q###
##Q#

#7

知心如幻2006-12-31 18:55

我写的是多文件结构，不好给你

#8

nuciewth2007-01-03 20:42

/*C写的.回朔法*/
#include<stdio.h>

#define N 20

int x[N] ; //当前解
int sum = 0 ; //可行解的数量
int n=8 ; //规模
bool Place( int k )
{
int i;
for( i = 1 ; i < k ; i++ )
{
if(abs(k-i)==abs(x[k]-x[i])||x[i]==x[k])
{
return false;
}
}
return true;
}

void Backtrack( int t )
{
if( t > n)
{
sum++;
for(int i=1;i<=n;i++)
{
/* for(int j=1;j<=n;j++)
{
if(j==x[i])
{
printf("*");
}
else
{
printf(" ");
}
}
printf("\n");
*/
printf("%-3d%-3d\n",i,x[i]);
}
printf("\n");
}
else
{
for( int i = 1 ; i<= n ; i++ )
{
x[t] = i ;
if( Place( t )==true )
{
Backtrack( t + 1 ) ;
}
}
}
}

int main()
{
int i;
scanf("%d",&n);
for( i = 1 ; i <= n ; i++ )
{
x[i] = 0 ;
}
Backtrack( 1 ) ;
printf("%d\n",sum);
}