queen.cpp

八皇后问题：用回溯算法做的

#include<stdio.h>
#define  N  8   // N为皇后个数，m为摆法计数
int m=1,a[N]; // a[i]存放第i个皇后放置的行号,
int ok(int i, int j) //检查(i,j)上能否放棋子
{ 
	int j1,ok1,i1;
	j1=j;
	i1=i;
	ok1=1;  //检查第i行上能否放棋子
	while( (j1>1) && ok1)
	{
		j1--;     
		ok1=a[j1]!=i ;
	}

	j1=j; i1=i;    //检查对角线上能否放棋子
	while( (j1>1)&&(i1>1)&&ok1) 
    {
		j1--;
		i1--; 
		ok1=a[j1]!=i1 ;
	} 

    j1=j; i1=i;     //检查另一对角线上能否放棋子
    while( (j1>1)&&(i1<N)&&ok1) 
    {
		j1--; 
		i1++;
		ok1=a[j1]!=i1 ;
	}
    return  ok1;
}

void  queen(int j) //从第j列开始逐个试探
{  
	if (j>N) 
    {
		printf("m=%d   ",m++);
	    for (int i=1;i<=N;i++) 
			printf("    %d",a[i]);
        printf("\n");
    }    
   else  
	   for(int i=1; i<=N;i++)
             if(ok(i,j))  //检查(i,j)上能否放棋子
             {
				 a[j]=i; //在(i,j)上放一个棋子
                 queen(j+1);
             } 
}

main()
{
	queen(1);
}