C语言【微项目12】—N皇后问题[放置N个皇后在棋盘](采用回溯法-递归方式实现)【2021-12-19】

C语言【微项目12】—N皇后问题[放置N个皇后在棋盘](采用回溯法-递归方式实现)【2021-12-19】


【TDTX】
【C99】
【注1】本文实现了回溯点的提示,以及实现了返回到第N层的提示!
【注2】只输出了求解与输出了探测得到的第一个解,其余解也可以轻易得到!

一、nhhhsdg.c

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

int co = 0;//已经正确放置皇后的个数记录 

int SetQueenLoaction(int* s,int n,int i)
{
	int flag = 1;
	
	
	if(co == n)
	{
		return 1;
	}

	
	int j = 0;
	int status = 0;

	for(j = 0;j < n;j++)
	{
		for(int k = 0;k < i;k++)
		{
			if(j == s[k] || (abs(i-k) == abs(j - s[k])) )
			{
				//printf("不能用:i = %d,j = %d\n",i,j);
				flag = 0;
				break;
			}
		}
		if(flag == 1)
		{
			s[i] = j;
			status = 1;
			printf("能放置:i = %d,j = %d\n",i,j);
			co++;
			if(SetQueenLoaction(s,n,i+1) == 0)
			{
				//这里是回溯触发点 
				s[i] = -1;
				status = 0;
				co--;
				printf("<在此第%d层(i:%d)触发回溯!回溯到第%d(i:%d)层>\n",i+1+1,i+1,i+1,i);
			}
			else
			{
				return 1;
			}
		}
		else
		{
			flag = 1;
		}
	}
	if(status == 0)
	{
		return 0;
	}
}

int main()
{
	int n = 0;
	puts("输入皇后个数:");
	scanf("%d",&n);
	int s[n];//s[i] = m,表示皇后放在第i行第m列 
	
	for(int i = 0;i < n;i++)
	{
		s[i] = -1;
	}
	puts("<----------计算过程(可看回溯演化)---------->"); 
	SetQueenLoaction(s,n,0);
	puts("<----------计算完成(可看回溯演化)---------->\n"); 
	
	puts("输出最终结果(采用一维数组展示):"); 
	for(int i = 0;i < n;i++)
	{
		printf("%d ",s[i]);
	}

	puts("\n输出最终结果(采用二维棋盘维展示):"); 
	for(int i = 0;i < n;i++)
	{
		for(int j = 0;j < n;j++)
		{
			if(s[i] == j)
			{
				printf("# ");
			} 
			else
			{
				printf("x ");
			}
		}
		puts("");

	}

	return 0;
}

二、 运行结果示例

2.1 3皇后

C语言【微项目12】—N皇后问题[放置N个皇后在棋盘](采用回溯法-递归方式实现)【2021-12-19】

2.2 4皇后

C语言【微项目12】—N皇后问题[放置N个皇后在棋盘](采用回溯法-递归方式实现)【2021-12-19】

2.3 8皇后

C语言【微项目12】—N皇后问题[放置N个皇后在棋盘](采用回溯法-递归方式实现)【2021-12-19】
C语言【微项目12】—N皇后问题[放置N个皇后在棋盘](采用回溯法-递归方式实现)【2021-12-19】
C语言【微项目12】—N皇后问题[放置N个皇后在棋盘](采用回溯法-递归方式实现)【2021-12-19】
C语言【微项目12】—N皇后问题[放置N个皇后在棋盘](采用回溯法-递归方式实现)【2021-12-19】


------------------------------------------------------第十二次发项目类文章有点激动啊!-----------------------------------------------------
-----------------------------------------------------【C语言—微项目—自编练习】----------------------------------------------------------
----------------------------------------------------------------【TDTX】--------------------------------------------------------------------------

上一篇:C语言【微项目12】—N皇后问题[放置N个皇后在棋盘](采用回溯法-递归方式实现)


下一篇:STM32基本定时器做万能遥控器