iT邦幫忙

0

c語言遞迴問題,N-queens on a M*M chessboard(M>N)

不明 2021-09-08 22:58:07494 瀏覽

小弟目前正被一題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;
				}
			}
		}
	}
}
你這寫法跟遞迴有關嗎?
只有獻上八個字
「越級打怪,自己搞定」

2 個回答

0
小魚
iT邦大師 1 級 ‧ 2021-09-09 06:45:41

看起來像是leetcode,
有來源網址嗎?

0
海綿寶寶
iT邦大神 1 級 ‧ 2021-09-09 10:20:01

N-Queen 我不會
我來更正一下英文的部份

不是 rock(石頭)
Rook(城堡)

希望能夠節省一些高手們猜
「石頭 跟 皇后到底跟有什麼關係」的時間
/images/emoticon/emoticon06.gif

車不就不用判斷斜向的, 多一個判斷role (Q or R).
先把 N-queens problem 玩一遍吧
https://rosettacode.org/wiki/N-queens_problem#C

是呀
所以我才說他是「越級打怪」

這位大大同時寫了 Queen 和 Rook 的版本
可惜是分開的,不是一起放在棋盤上
/images/emoticon/emoticon08.gif

我要發表回答

立即登入回答