小弟目前正被一題N-queens的延伸題型困擾,題目要求將N個queens與M個rooks按規則排在一個(M+N)×(M+N)的棋盤上並算出所有可能的方法。
規則為:1.同一行,列或45度斜線只能存在最多一個queens。
2.同一行,列只能存在最多一個rooks。
3.rook與queen不能同時存在於同一格內。
以下是我所寫的程式碼,我的想法是先在placeQ這個function中將queens排好,之後再呼叫placeR在原有已排好的queens基礎上再將rooks排好。經過試驗後發現當queen的數目設為0時答案為正確的,但只要queen的數目大於0時答案會比正確答案大許多,甚至有時程式需要非常久的時間才能跑出答案,我猜測可能是placeQ呼叫太多次placeR或vaildQ出錯所導致的,但想不到解決方法或者其他可以算出答案的方法。希望各位大大能夠幫助我指出錯誤或者能提供別的想法。

#include <stdio.h>
#include <stdlib.h>
int Qcol[101]={0};
int Rcol[101]={0};
static int answer=0;

int vaildQ(int row,int col);
void placeQ(int col,int num_queens,int M,int N);
int vaildR(int row,int col);
void placeR(int col,int num_rooks,int M,int N);

int main()
{
	int M,N;
	scanf("%d %d",&M,&N);
	placeQ(1,0,M,N);
	printf("%d\n",answer);
	system("pause");
}

int vaildQ(int row,int col)
{
	int i;
	for(i=0;i<col;i++)
	{
		if(Qcol[i]==row||row-Qcol[i]==col-i||col-i==Qcol[i]-row)
			return 0;
	}
	return 1;
}
void placeQ(int col,int num_queens,int M,int N)
{
	int i,j;
	if(num_queens==M)
	{		
		placeR(1,0,M,N);
	}
	else
	{
		for(i=col;i<=M+N;i++)
		{
			for(j=1;j<=M+N;j++)
			{
				if(vaildQ(i,j))
				{
					Qcol[j]=i;
					placeQ(j+1,num_queens+1,M,N);
					Qcol[j]=0;
				}
			}
		}
	}
}

int vaildR(int row,int col)
{
	int i;
	for(i=0;i<col;i++)
	{
		if(Rcol[i]==row)
		{
			return 0;
		}
	}
	if(Qcol[col]==row)
		return 0;

	return 1;
}
void placeR(int col,int num_rooks,int M,int N)
{
	int i,j;
	if(num_rooks==N)
	{
		answer++;
	}
	else
	{
		for(j=col;j<=M+N;j++)
		{
			for(i=1;i<=M+N;i++)
			{
				if(vaildR(i,j))
				{
					Rcol[j]=i;
					placeR(j+1,num_rooks+1,M,N);
					Rcol[j]=0;
				}
			}
		}
	}
}