由八皇后问题想到的一个

zhaolinger2 2009-06-01 02:10:13

在n*n的棋盘上至少要放置多少个皇后才能控制住棋盘上的所有格子？
有没有人能够提供一个算法的？谢谢！

...全文

201 8 打赏收藏转发到动态举报

写回复

用AI写文章

8 条回复

切换为时间正序

请发表友善的回复…

发表回复

纯净水o 2009-06-09

打赏
举报

我给你个任意皇后数的程序
#include<stdio.h>
#include<stdlib.h>
#define NULL 0
#define STACK_INI_SIZE 30
#define STACKINCREMENT 20
typedef struct
{
int *top;
int *base;
int stacksize;
int length;
}sqstack;
main()
{
void initstack(sqstack *s);/*初始化栈*/
void operation(sqstack *s,int i);/*运算*/
void clearstack(sqstack *s);/*清空栈*/
sqstack s;
int i,flag1=1,flag2=1,flag3=1;
char ch;
initstack(&s);
printf("请输入皇后的个数(大于3以上的皇后数)\n");
while(flag1)
{
fflush(stdin);
scanf("%d",&i);
if(i<4)
printf("输入错误请重新输入\n");
else
flag1=0;
}
flag1=1;
while(flag1)
{

clearstack(&s);
operation(&s,i);
flag2=1;
printf("\n还继续么?(y/n)");
while(flag2)
{
fflush(stdin);
scanf("%c",&ch);
if(ch=='n'||ch=='N')
{
flag1=0;
flag2=0;
}
else if(ch=='y'||ch=='Y')
{
flag1=1;
flag2=0;
}
else
printf("\n输入错误请重新输入\n");
}
if(flag1)
{
printf("请输入皇后的个数(大于3以上的皇后数)");
while(flag3)
{
fflush(stdin);
scanf("%d",&i);
if(i<4)
printf("输入错误请重新输入\n");
else
flag3=0;
}
flag3=1;
}
}
}
void initstack(sqstack *s)
{
s->top=s->base=(int *)malloc(STACK_INI_SIZE*sizeof(int));
if(!s->base)
exit(1);
s->stacksize=STACK_INI_SIZE;
*(s->base)=0;
s->top++;
*(s->top)=101;
s->top++;
s->length=2;
}
void push(sqstack *s,int i)
{
int *p;
if(s->length>=s->stacksize)
{
s->base=(int *)realloc(s->base,(STACK_INI_SIZE+STACKINCREMENT)*sizeof(int));
if(!s->base)
exit(1);
s->top=s->base+s->stacksize;
s->stacksize+=STACKINCREMENT;
}
*(s->top)=i;
s->top++;
s->length++;
p=s->base;
}
int pop(sqstack *s)
{
int *p,k;
if(s->top==s->base)
exit(1);
else
{
p=s->top;
k=*(--p);
s->top--;
*(s->top)=NULL;
s->length--;
}
return(k/100);
}
void operation(sqstack *s,int i)
{
void stackoutput(sqstack *s);
int j,k,m,n,x,y,z,a,b=0,flag1=1,flag2=1,flag3=1,*p;
j=2;/*初始化从第2列*/
k=1;/*j代表当前列数的行数*/
while(s->top-1!=s->base)/*输出所有成立条件之后结束循环*/
{
flag1=1;/*旗帜*/
for(;k<=i&&flag1;k++)/*计算行数*/
{
p=s->top;
y=j;/*列*/
x=k;/*行*/
z=0;
flag2=1;
p--;
if((*(s->top-1)%100)==i)
p--;
while(p!=s->base&&flag2)
{
m=(*p)/100;/*行*/
n=(*p)%100;/*列*/
if(m==x)
flag2=0;
else if(x+y==m+n)
flag2=0;
else if(m-n==x-y)
flag2=0;
else
z++;
p--;
}
flag2=1;
if(j==1)
{
a=k*100+j;
if(k<i+1)
{
push(s,a);
k=0;
j=2;
}
else
{
s->top=s->base;
flag1=0;
}
}
else if(z==j-1)
{
a=k*100+j;
push(s,a);
if(j!=i)
{
j++;
k=0;
}
else
{
printf(" %3d.",++b);
stackoutput(s);
if(b%5==0)
printf("\n");
}
}
else if(k==i)
{
if((*(s->top-1)%100)==i)
k=pop(s);
flag3=1;
while(j!=1&&flag3)
{
k=pop(s);
j--;
if(k!=i)
flag3=0;
}
}
if(((*(s->top-1)/100)==i)&&(*(s->top-1)%100==i))
{
if((*(s->top-1)%100)==i)
k=pop(s);
flag3=1;
while(j!=1&&flag3)
{
k=pop(s);
j--;
if(k!=i)
flag3=0;
}
}
}
}
}
void clearstack(sqstack *s)
{
int *p;
p=s->top;
p--;
while(p!=s->base)
{
*p=NULL;
p--;
}
s->top=s->base;
s->top++;
*(s->top)=101;
s->top++;
s->length=2;
}
void stackoutput(sqstack *s)
{

int *p,*q;
q=p=s->top;
p--;
while(p!=s->base)
p--;
p++;
while(p!=s->top)
{
printf("%d",*p/100);
p++;
}
}

yxysdcl 2009-06-06

打赏
举报

可以把n*n个点搞两份，左边n*n个点(编号1~n*n),右边也n*n个点(编号1~n*n),如果左边点u上放一个皇后能控制的点的编号v,那么将左边的u到右边的v连一条边.最后,就是求选择左边最少的点,使得右边的所有点都被覆盖到,就是求支配集.这个是一个NP困难的问题,碰到过很多次,不过除了搜索没有想到过更好的算法..希望了解的人能提供些资料.

breezes2008 2009-06-05

打赏
举报

/*

*

日期：2008-11-9下午

函数功能：已知在N*N的方格内，摆上不同的“皇后”（国际象棋），使其不在同一行、同一列、同一对角线

,求出所有的解 当N=4时，输出2组解；当N=8时，输出92组解

算法：回溯法

*/



#include "stdio.h"

#include "math.h"

#define N 8   /*皇后数*/

#define DEBUG 1

void init(void);

void backtrack(int num);

void showAnswer(void);

int state[N][N];  /*棋盘状态*/

long count=0;  /*组解计数器*/

main()

{

    clrscr();

    init();

    backtrack(0);

    getch();

}



void init(void)

{

    int i,j;

    for (i=0;i<N;i++)

    for (j=0;j<N;j++)

    state[i][j]=0;

}

void backtrack(int num)    /*以行作为判断点*/ 

{

    int row,earse;

    if ( num==N )

    {

        count++;

        showAnswer();

    }

    else

    {

            for (row=0;row<N;row++)

       	    if ( isSafe(num,row) )  

	    {

		 for (earse=0;earse<N;earse++)  /*一行只能放一个皇后*/

		 state[num][earse]=0;  

		 state[num][row]=1;   /*1表示该点皇后被放置*/

		 backtrack(num+1);  /*该点安全，回溯*/

            }          

   }



}







void showAnswer(void)

{

    int i,j;

    printf("No.%ld\n",count);

    for (i=0;i<N;i++)

    {

        for (j=0;j<N;j++)

        {

	    if(state[i][j]==0) printf("%3s",".");

	    if(state[i][j]==1) printf("%3s","Q");



        }

        printf("\n");

    }

}



/*

*判断该点是否安全

*/



int isSafe(int num,int row)

{

    int i,j;

    for (i=0;i<num;i++)   

    {

        for(j=0;j<N;j++)

        if( state[i][j]==1)     

        if ( abs(i-num)==abs(j-row)||j==row  ) return 0;  

    }

    return 1;

}

xuexuankr 2009-06-04

打赏
举报

王晓东写的那本有详细的代码，这里就不copy了，但是这样讨论八皇后也没啥意义。
不过有个很有趣的地方是匈牙利算法里面的方法和八皇后的步骤有异曲同工之妙。

绿色夹克衫 2009-06-04

打赏
举报

mathe大牛在数学研发网上给了一个链接,我给转过来,大家看看吧!

这是结果
http://www.research.att.com/~njas/sequences/A075458

这是论文地址
http://www.combinatorics.org/Volume_8/PDF/v8i1r29.pdf

fire_woods 2009-06-04

打赏
举报



#define QUEENS	(8)

int upperlim = (1<<QUEENS) - 1;

int sum = 0;

void test(int row, int ld, int rd)

{

	int pos, p;

	if(row != upperlim)

	{

		pos = upperlim & (~(row|ld|rd));

		while(pos != 0)

		{

			p = pos & (-pos);

			pos = pos - p;

			test(row+p, (ld+p)<<1, (rd+p)>>1);

		}

	}

	else

	{

		sum++;

	}

}



//test(0, 0, 0);