八数码问题c语言,八数码问题的可解性

八数码问题c语言,八数码问题的可解性对于给定八数码棋局的初始状态,我们的目标是通过交换空格与其相邻棋子使棋盘达到目标状态。其中,游戏规则是只能交换空格与其上下左右四个方向的相邻棋子。假设棋局目标状态为如下形式:(A、B、C、D、E、F、G、H表示棋子)ABCDEFGH而初始状态就是A、B、C、D、E、F、G、H这八个棋子在这九个棋格上的任意分布。并且我们对棋盘中每个棋格进行如下形式的编号:12345…

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

对于给定八数码棋局的初始状态,我们的目标是通过交换空格与其相邻棋子使棋盘达到目标状态。

其中,游戏规则是只能交换空格与其上下左右四个方向的相邻棋子。

假设棋局目标状态为如下形式:(A、B、C、D、E、F、G、H表示棋子)

A  B  C

D  E  F

G  H

而初始状态就是A、B、C、D、E、F、G、H这八个棋子在这九个棋格上的任意分布。

并且我们对棋盘中每个棋格进行如下形式的编号:

1  2  3

4  5  6

7  8  9

那么,对于一个任意的棋局状态,我们可以取得这八个棋子(A、B、C、D、E、F、G、H)的一个数列:棋子按照棋格的编号依次进行排列,记为p=c[1]c[2]c[3]c[4]c[5]c[6]c[7]c[8](即A、B、C、D、E、F、G、H的一个排列)。

在分析之前,先引进逆序和逆序数的概念:对于棋子数列中任何一个棋子c[i](1≤i≤8),如果有j>i且c[j]

现在,我们对一个任意的棋局状态p=c[1]c[2]c[3]c[4]c[5]c[6]c[7]c[8]进行分析:

引理1:如果交换任何两个相邻的棋子,那么棋子数列的逆序数将发生奇偶性互变(奇偶性互变是指由奇数变为偶数,或由偶数变为奇数,下同)。

其证明很简单,假设交换的是c[i]和c[i+1],那么对于c[j](1≤j≤i-1或i+2≤j≤8)的逆序数并不改变。若交换之前 c[i]c[i+1],那么交换之后,c[i]的逆序数减1,而c[i+1]的逆序数不变。所以,引理1成立。

引理2:如果棋子数列经过n次相邻棋子交换后,若n为偶数,则数列逆序数奇偶性不变;若n为奇数,则数列逆序数将发生奇偶性互变。

其证明可以由引理1简单推出。

引理3:在满足上述约定的八数码问题中,空格与相邻棋子的交换不会改变棋局中棋子数列的逆序数的奇偶性。

证明:显然空格与左右棋子交换不会改变棋子数列的逆序数(因为数列并没有改变)。现在考虑空格与上下棋子交换的情况:若空格与上方的棋子交换(假设交换是可行的),将得到一个新数列。若假设交换棋子为c[i]=X,那么原数列p=c[1]…X c[i+1]c[i+2]…c[8]将变为新数列q=c[1]…c[i+1]c[i+2]X …c[8](注意:在棋盘中,上下相邻的两棋格之间隔有两个棋格)。由原数列p到新数列q的转变可以通过如下方式加以解释:用X与c[i+1]、 c[i+2]先后进行两次相邻交换而完成状态转变。所以根据引理2知,由p状态到q状态并不会改变改变棋子数列的逆序数的奇偶性。同理可证空格与下方棋子交换也不会改变棋子数列的逆序数的奇偶性。所以,空格与相邻棋子的交换不会改变棋局中棋子数列的逆序数的奇偶性。

定理1

(1)当初始状态棋局的棋子数列的逆序数是奇数时,八数码问题无解;

(2)当初始状态棋局的棋子数列的逆序数是偶数时,八数码问题有解。

证明:由引理3知,按照八数码问题的游戏规则,在游戏过程中,棋局的棋子数列的逆序数的奇偶性不会发生变化。而上面规定的目标状态没有逆序存在,所以目标状态下棋局的逆序数为偶数(实际为0)。显然,可能的初始状态棋局的棋子数列的逆序数可能为奇数,也可能为偶数(因为把一个初始状态中任意相邻两个棋子交换,得到的新的状态作为初始状态,它们的奇偶性相反)。所以,对于任意一个初始状态,若其棋局的棋子数列的逆序数为奇数,则永远也不可能达到目标状态,即八数码问题无解;若其棋局的棋子数列的逆序数为偶数,(接下来如何证明)。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/158892.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • 多重共线性检验之方差膨胀因子VIF[通俗易懂]

    多重共线性检验之方差膨胀因子VIF[通俗易懂]过程1、构造每一个自变量与其余自变量的线性回归模型,例如,数据集中含有p个自变量,则第一个自变量与其余自变量的线性组合可以表示为2、根据如上线性回归模型得到相应的判决系数R2R^2R2,进而计算第一个自变量的方差膨胀因子VIF:importpandasaspdimportnumpyasnpfromsklearnimportmodel_selectionimportstatsmodels.apiassnfromstatsmodels.stats.outlier

  • axios的post请求参数格式

    axios的post请求参数格式axios的post请求参数格式默认格式Content-Type:application/json;charset=UTF-8 axios({method:’post’,url:”,data:{ param1:”, param2:” }}}).the…

  • 【Nginx】磁盘文件写入飞地发

    【Nginx】磁盘文件写入飞地发

  • Mysql实现同时交换两个表的表名

    Mysql实现同时交换两个表的表名转载自不服输的南瓜的Mysql实现同时交换两个表的表名表重命名有两种方式,所以交换两表名也有两种方式:方法一:locktablest1write,t2write;altertablet1renametot3;altertablet2renametot1;altertablet3renametot2;unlocktables;方法二:renametablet1tot3,t2tot1,t2tot3;…

  • 微信小程序的拍照功能「建议收藏」

    作者:刘旭濠撰写时间:2019年04月14日一开始就想弄个微信的小程序玩玩然后想了想最后就决定了,就弄个微信小程序的拍照功能,然后就上网查询了一些资料,在微信社区文档里有很多功能可以使用,然后我就尝试的找了一下关于拍照的资料,然后整理出来文档和网上的一些资料,在微信的API还有更多的资料和其他好玩的玩意代码如下://定时器拍照setTime:function(){  lett…

  • JAX-WS SOA杂谈

    JAX-WS SOA杂谈[b][size=medium]代码优先[/size][color=blue]先编写类,通过注解定义wsdl的各项属性,基于类来生成wsdl文件[/color][size=medium]契约优先[/size][color=blue]先制定标准,与其它系统一起定义一个统一的标准,实现系统之间数据传输的规范性,即先有wsdl再有类[/color][size=me…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号