【算法导论】八皇后问题的算法实现(C、MATLAB、Python版)

简介:         八皇后问题是一道经典的回溯问题。问题描述如下:皇后可以在横、竖、斜线上不限步数地吃掉其他棋子。如何将8个皇后放在棋盘上(有8*8个方格),使它们谁也不能被吃掉?         看到这个问题,最容易想到的就是遍历穷举法,不过仔细一想,思路虽然非常清晰,但是需要遍历次数太多,时间复杂度很高。
        八皇后问题是一道经典的回溯问题。问题描述如下:皇后可以在横、竖、斜线上不限步数地吃掉其他棋子。如何将8个皇后放在棋盘上(有8*8个方格),使它们谁也不能被吃掉?
        看到这个问题,最容易想到的就是遍历穷举法,不过仔细一想,思路虽然非常清晰,但是需要遍历次数太多,时间复杂度很高。那么,我们应该怎么办呢?下面给出算法思路:
        算法思想:首先尝试在第一行放置第一个皇后,然后在第二行放置第二个使之与前面的皇后不构成威胁,依此类推。如果发现不能放置下一个皇后,就回溯到上一步,试着将皇后放在其他的位置。最后,或者尝试完所有的可能或者找到解决方案。
        这种算法思想与中国的一句古话“不撞南墙不回头”类似:一路向前走,直到走到死胡同,然后往回走,回到上一个岔路口,重新选择一个方向,继续向前走,直到到达目的地。
        下面给出了该算法的具体实现,用C、MATLAB、PYTHON分别进行了实现,由于程序给出了比较详细的注释,因此就不对具体程序解释说明了。

C语言实现:

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

#define N 8//棋盘大小

int matrix[N][N];//存储皇后的位置,其实也可以用一维数组表示

void PrintQueen();//打印棋盘
void PlaceQueen(int row);//放置皇后
int Conflict(int row,int col);//检查当前皇后是否与之前的冲突

int main()
{
    PlaceQueen(0);
    return 0;
}

void PrintQueen()
{
    static int solutionNum=0;//看总共有多少种情况
    solutionNum+=1;
    int row,col;
    printf("第%d种方法:\n",solutionNum);
    for(row=0;row<N;row+=1)
    {
        for(col=0;col<N;col+=1)
        {
            if(matrix[row][col])
            {
                printf("* ");
            }
            else
            {
                printf("- ");
            }
        }
        printf("\n");
    }
    printf("\n");
}

int Conflict(int row,int col)
{
	for (int m = 0; m <row ; m++) 
	{  
        for (int n = 0; n <N; n++)
		{   
            if (matrix[m][n] == 1) //  每一行只有一个皇后  
			{  
                if ( n == col || abs(row - m) == abs(col - n) )   // 检查是否与之前的皇后冲突
                    return false;  
            }  
        }  
    }  
    return true;
}

void PlaceQueen(int row)
{
	if(row>=N)//已经放置了N个皇后
	{
		PrintQueen();
	}
	else
	{
		for(int col=0;col<N;col++)
		{
			matrix[row][col]=1;
			if(row==0||Conflict(row,col))
					PlaceQueen(row+1);//递归调用		
			matrix[row][col]=0;		
		}
		
	}
	
}

MATLAB实现

脚本文件Queen.m

 clear all
clc
 
global solutionNum;
solutionNum=0;%全局变量记录方法数
N=8;%皇后个数
matrix=zeros(N);%存储皇后位置信息
 
PlaceQueen(1,matrix,N)%调用放置方法


函数文件PlaceQueen.m

function PlaceQueen(row,matrix,N)%回溯法放置皇后
 
    if row>N
        PrintQueen(N,matrix);%打印棋盘
    else
        for col=1:N
            matrix(row,col)=1;
            if row==1||Conflict(row,col,N,matrix)%检测是否冲突
                PlaceQueen(row+1,matrix,N);
            end
            matrix(row,col)=0;
        end
    end
    
    %子函数:检测冲突
    function result=Conflict(row,col,N,matrix)%检测是否冲突
 
    result=1;
    for i=1:row-1
        for j=1:N
            if matrix(i,j)==1
                if ((j==col)||(abs(row-i)==abs(col-j)))%是否产生冲突:在同一直线,斜线上
                    result=0;
                    break;
                end
            end
        end
        if result==0
            break;
        end
    end
     
    %子函数:打印棋盘信息
function PrintQueen(N,matrix)
 
    global solutionNum; %定义全局变量,来累积方法数
    solutionNum=solutionNum+1;
    
    disp(['第',num2str(solutionNum),'种方法:'])
 
disp(matrix)

PYTHON实现:

def conflict(state,nextX):#冲突检测函数
    nextY=len(state)
    for i in range(nextY):
        if abs(state[i]-nextX) in (0,nextY-i):#检测是否在同一直线、斜线
            return True
    return False

def queens(num=8,state=()): #放置皇后,采用元组state来存储皇后的位置
    for pos in range(num):
        if not conflict(state,pos):
            if len(state)==num-1:
                yield (pos)
            else:
                for result in queens(num,state+(pos,)):
                    yield (pos,)+result



for solution in queens(8):
    print (solution)
    
print('总共的方法数为:',len(list(queens(8))))

运行结果分别如下:

1、C语言的运行结果:


2、MATLAB语言的运行结果:


3、PYTHON语言的运行结果:
 

扩展:

上面的程序中,改变N的值就可以解决N皇后的问题了, 但还可以 用分治法来解决N皇后的问题,具体参见文献 《N皇后问题解的构造和等价性分析》。下面的Matlab程序给出了一个简单的算法过程:
4皇后的一种放置方式:
     0     0     1     0
     1     0     0     0
     0     0     0     1
     0     1     0     0
根据4皇后的放置方式可以推导出16皇后的一种放置方式:
     0     0     0     0     0     0     0     0     0     0     1     0     0     0     0     0
     0     0     0     0     0     0     0     0     1     0     0     0     0     0     0     0
     0     0     0     0     0     0     0     0     0     0     0     1     0     0     0     0
     0     0     0     0     0     0     0     0     0     1     0     0     0     0     0     0
     0     0     1     0     0     0     0     0     0     0     0     0     0     0     0     0
     1     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0
     0     0     0     1     0     0     0     0     0     0     0     0     0     0     0     0
     0     1     0     0     0     0     0     0     0     0     0     0     0     0     0     0
     0     0     0     0     0     0     0     0     0     0     0     0     0     0     1     0
     0     0     0     0     0     0     0     0     0     0     0     0     1     0     0     0
     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     1
     0     0     0     0     0     0     0     0     0     0     0     0     0     1     0     0
     0     0     0     0     0     0     1     0     0     0     0     0     0     0     0     0
     0     0     0     0     1     0     0     0     0     0     0     0     0     0     0     0
     0     0     0     0     0     0     0     1     0     0     0     0     0     0     0     0
     0     0     0     0     0     1     0     0     0     0     0     0     0     0     0     0
依次类推,可以得到4的幂次皇后的一种放置方式,不过 值得注意的是2、3、8、9、14、15、26、27、38、39这10个N值不能采用这种分治法。
由4皇后直接推出16皇后的Matlab实现如下:
clear all
clc
 
a4=[  0     0     1     0
     1     0     0     0
     0     0     0     1
     0     1     0     0]
 [asize bsize]=size(a4);
 
 a16=zeros(asize^2,bsize^2);
 [rowIndex,colIndex]=find(a4);
 
 for i=1:length(rowIndex)
     a16((1+asize*(rowIndex(i)-1)):asize*rowIndex(i),(1+asize*(colIndex(i)-1)):asize*colIndex(i))=a4;
 end
 a16


运行结果如下:



原文:http://blog.csdn.net/tengweitw/article/details/44648249
作者:nineheadedbird










目录
相关文章
|
1天前
|
传感器 算法
基于GA遗传算法的多机无源定位系统GDOP优化matlab仿真
本项目基于遗传算法(GA)优化多机无源定位系统的GDOP,使用MATLAB2022A进行仿真。通过遗传算法的选择、交叉和变异操作,迭代优化传感器配置,最小化GDOP值,提高定位精度。仿真输出包括GDOP优化结果、遗传算法收敛曲线及三维空间坐标点分布图。核心程序实现了染色体编码、适应度评估、遗传操作等关键步骤,最终展示优化后的传感器布局及其性能。
|
1天前
|
算法 Serverless 数据处理
从集思录可转债数据探秘:Python与C++实现的移动平均算法应用
本文探讨了如何利用移动平均算法分析集思录提供的可转债数据,帮助投资者把握价格趋势。通过Python和C++两种编程语言实现简单移动平均(SMA),展示了数据处理的具体方法。Python代码借助`pandas`库轻松计算5日SMA,而C++代码则通过高效的数据处理展示了SMA的计算过程。集思录平台提供了详尽且及时的可转债数据,助力投资者结合算法与社区讨论,做出更明智的投资决策。掌握这些工具和技术,有助于在复杂多变的金融市场中挖掘更多价值。
22 12
|
2天前
|
机器学习/深度学习 算法 安全
基于深度学习的路面裂缝检测算法matlab仿真
本项目基于YOLOv2算法实现高效的路面裂缝检测,使用Matlab 2022a开发。完整程序运行效果无水印,核心代码配有详细中文注释及操作视频。通过深度学习技术,将目标检测转化为回归问题,直接预测裂缝位置和类别,大幅提升检测效率与准确性。适用于实时检测任务,确保道路安全维护。 简介涵盖了算法理论、数据集准备、网络训练及检测过程,采用Darknet-19卷积神经网络结构,结合随机梯度下降算法进行训练。
|
3天前
|
算法 数据可视化 数据安全/隐私保护
一级倒立摆平衡控制系统MATLAB仿真,可显示倒立摆平衡动画,对比极点配置,线性二次型,PID,PI及PD五种算法
本课题基于MATLAB对一级倒立摆控制系统进行升级仿真,增加了PI、PD控制器,并对比了极点配置、线性二次型、PID、PI及PD五种算法的控制效果。通过GUI界面显示倒立摆动画和控制输出曲线,展示了不同控制器在偏转角和小车位移变化上的性能差异。理论部分介绍了倒立摆系统的力学模型,包括小车和杆的动力学方程。核心程序实现了不同控制算法的选择与仿真结果的可视化。
31 15
|
3天前
|
算法
基于SOA海鸥优化算法的三维曲面最高点搜索matlab仿真
本程序基于海鸥优化算法(SOA)进行三维曲面最高点搜索的MATLAB仿真,输出收敛曲线和搜索结果。使用MATLAB2022A版本运行,核心代码实现种群初始化、适应度计算、交叉变异等操作。SOA模拟海鸥觅食行为,通过搜索飞行、跟随飞行和掠食飞行三种策略高效探索解空间,找到全局最优解。
|
4天前
|
算法 数据安全/隐私保护 计算机视觉
基于FPGA的图像双线性插值算法verilog实现,包括tb测试文件和MATLAB辅助验证
本项目展示了256×256图像通过双线性插值放大至512×512的效果,无水印展示。使用Matlab 2022a和Vivado 2019.2开发,提供完整代码及详细中文注释、操作视频。核心程序实现图像缩放,并在Matlab中验证效果。双线性插值算法通过FPGA高效实现图像缩放,确保质量。
|
5天前
|
机器学习/深度学习 数据采集 算法
基于GWO灰狼优化的CNN-GRU-SAM网络时间序列回归预测算法matlab仿真
本项目基于MATLAB2022a,展示了时间序列预测算法的运行效果(无水印)。核心程序包含详细中文注释和操作视频。算法采用CNN-GRU-SAM网络,结合灰狼优化(GWO),通过卷积层提取局部特征、GRU处理长期依赖、自注意力机制捕捉全局特征,最终实现复杂非线性时间序列的高效预测。
|
5天前
|
传感器 算法 物联网
基于粒子群算法的网络最优节点部署优化matlab仿真
本项目基于粒子群优化(PSO)算法,实现WSN网络节点的最优部署,以最大化节点覆盖范围。使用MATLAB2022A进行开发与测试,展示了优化后的节点分布及其覆盖范围。核心代码通过定义目标函数和约束条件,利用PSO算法迭代搜索最佳节点位置,并绘制优化结果图。PSO算法灵感源于鸟群觅食行为,适用于连续和离散空间的优化问题,在通信网络、物联网等领域有广泛应用。该算法通过模拟粒子群体智慧,高效逼近最优解,提升网络性能。
|
7天前
|
监控 算法 安全
内网桌面监控软件深度解析:基于 Python 实现的 K-Means 算法研究
内网桌面监控软件通过实时监测员工操作,保障企业信息安全并提升效率。本文深入探讨K-Means聚类算法在该软件中的应用,解析其原理与实现。K-Means通过迭代更新簇中心,将数据划分为K个簇类,适用于行为分析、异常检测、资源优化及安全威胁识别等场景。文中提供了Python代码示例,展示如何实现K-Means算法,并模拟内网监控数据进行聚类分析。
28 10
|
25天前
|
存储 算法 安全
控制局域网上网软件之 Python 字典树算法解析
控制局域网上网软件在现代网络管理中至关重要,用于控制设备的上网行为和访问权限。本文聚焦于字典树(Trie Tree)算法的应用,详细阐述其原理、优势及实现。通过字典树,软件能高效进行关键词匹配和过滤,提升系统性能。文中还提供了Python代码示例,展示了字典树在网址过滤和关键词屏蔽中的具体应用,为局域网的安全和管理提供有力支持。
50 17

热门文章

最新文章

推荐镜像

更多