当前位置：网站首页>C语言实现N皇后问题

C语言实现N皇后问题

2022-07-02 11:53:00 【ALuoJi】

回溯算法实现N皇后问题

完整代码实现

#include<stdio.h>
#include<malloc.h>
#include<math.h>

#define true 1
#define false 0

int num=0;

int place(int* paraSolution,int paraT)
{
    
	for(int j=1;j<paraT;j++)
	{
    
		if((abs(paraT-j)==abs(paraSolution[j]-paraSolution[paraT]))||(paraSolution[j]==paraSolution[paraT]))
		{
    
			return false;
		}
	}
	return true;
}

void backtracking(int* paraSolution, int paraN, int paraT){
    
	int i;
    if (paraT > paraN){
    
        for (i = 1; i <= paraN; i ++)
            printf("%d ", paraSolution[i]);
			num++;
		printf("\r\n");
    }else{
    
        for (i = 1; i <= paraN; i ++){
    
            paraSolution[paraT] = i;
            if (place(paraSolution, paraT))
                backtracking(paraSolution, paraN, paraT + 1);
        }
    }
}

void nQueue(int paraN)
{
    
	int i;
	int* solution=(int*)malloc(sizeof(int)*(paraN+1));
	for(i=0;i<=paraN;i++)
	solution[i]=0;

	backtracking(solution,paraN,1);
}

int main()
{
    
	nQueue(5);
	printf("The num is %d",num);
	return 0;
}