queen8.cpp

八皇后问题的一种高效递归解法

#include <iostream.h>
#include <stdio.h>
#include <string.h>
#define N 12
#define M N*2-1
bool rows[N], marka[M], markb[M];
int result[N], total;

void Placed(int r,int c,int count)
{
	rows[r]=1;
	result[count]=r;
	marka[r+c]=1;
	markb[r-c+N-1]=1;
}//在r，c处放置皇后

void Replaced(int r,int c)
{
	rows[r]=0;
	marka[r+c]=0;
	markb[r-c+N-1]=0;
}//取消在r，c处放置的皇后

bool valid(int r,int c)
{
	return !(rows[r]||marka[r+c]||markb[r-c+N-1]);
}//判断r，c处是否可以放置皇后

void Squeen(int c,int count)
{
	if(count>=N  )
		{
			printf("%2d:     ",total+1);
			for(int i=0;i<N;i++)
				printf("%2d",result[i]+1);
			printf("\n");	
			total++;
		}
	else
		for(int i=0;i<N;i++)
			if(valid(i,c) )
			{
				Placed(i,c,count);
				Squeen(c+1,count+1);
				Replaced(i,c);
			}
}//放置皇后递归程序

int main()
{
	char ext;
	printf("NUMBER   COL\n##*******");
	for(int i=0;i<N;printf("%d*",i+1),i++);
	printf("********\n\n");
	Squeen(0,0);
	printf("\nPress \"Enter\" key to exit the program\n");
	scanf(&ext);
	return 0;
}//main end