n后问题的所有可行解.cpp

回溯算法的一些题目的源代码

// 找出n后问题的所有可行解

#include <stdio.h>
int N, q[20];

bool Collide(int k1, int j1);
void PrintQueen(int k1);

void nQueen()
{
	int i=0, j=0, k=0;  //k解的组数
	while(i<N)
	{
		for(; j<N; j++)
			if(Collide(i, j)==0)
			{
				q[i]=j;
				break;
			}
		if(j==N)
		{
			if(i==0) break;
			j=q[--i]+1;
			q[i]=-1;
		}
		else
			if(i==N-1)
			{
				++k;
				PrintQueen(k);
				if(i==0) break;
				j=q[--i]+1;
				q[i]=-1;
			}
			else
			{
				++i;
				j=0;
			}
	}
}

void main()
{
	printf("\nQueens n = ");
	scanf("%d", &N);
	if(N<4) N=4;
	if(N>20) N=20;
	nQueen();
	printf("\n\n");
}

bool Collide(int k1, int j1)
{
	for(int i=0; i<k1; ++i)
	if(q[i]==j1 || i+q[i]==k1+j1 || i-q[i]==k1-j1) return 1;
	return 0;
}

void PrintQueen(int k1)
{
	printf("\nQueen%d:\n  ", k1);
	for(int i=1; i<=N; ++i) printf("%2d", i);
	for(i=0; i<N; ++i)
	{
		printf("\n%2d", i+1);
		for(int j=0; j<N; ++j)
		{
			if(q[i]==j) printf("■");
			else printf("□");
		}
	}
}