八数码问题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)


相关推荐

  • pycharm 注释多行代码[通俗易懂]

    pycharm 注释多行代码[通俗易懂]pycharm注释多行代码:选中要注释的代码块,按ctrl+/

  • jeesite集成cas认证[通俗易懂]

    jeesite集成cas认证[通俗易懂]cas和shiro集成,很好的解决了登录及权限问题。本人最近第一次使用,框架使用的是jeesite开源框架,本身已经集成了shiro,现在将cas集成到项目中。折腾了三天,终于把cas集成到jeesite中。现将集成过程写下,供朋友参考。本项目集成cas的同时还留有登录入口,此时需要多种认证方式,步骤6、7的设置就是针对这个功能的,如不需要可直接跳过。1、添加cas的maven依赖。

  • 对xml文件头内容的理解xmlns xmlns:xsi xsi:schemaLocation

    对xml文件头内容的理解xmlns xmlns:xsi xsi:schemaLocation

  • 新浪股票接口获取历史数据

    新浪股票接口获取历史数据这两天做了一个调用新浪股票接口获取实时以及历史股票数据的应用,因为新浪没有公开关于其接口的官方文档,所以通过各种百度差了很多关于新浪股票接口的使用,不过大家基本都是转载或者直接复制,对于实时数据的获取讲的很详细,但是缺少获取历史数据的方法。关于实时数据的获取大家可以看这篇博客:实时股票数据接口 经过不懈的努力终于再这篇博文中找到了关于新浪股票历史数据的获取方式腾讯股票接口、和讯网股票接口、新浪股票…

  • Apache中 RewriteCond 规则参数介绍[通俗易懂]

    Apache中 RewriteCond 规则参数介绍[通俗易懂]Apache中RewriteCond语句对于我来说一直是个难点,多次试图去把它搞明白,都没有结果,这次我终于算大概知道它的意思了。RewriteCond就像我们程序中的if语句一样,表示如果符合某个或某几个条件则执行RewriteCond下面紧邻的RewriteRule语句,这就是RewriteCond最原始、基础的功能,为了方便理解,下面来看看几个例子。RewriteEngineonRewriteCond%{HTTP_USER_AGENT}^Mozilla\/5\.0.*Rew…

  • xfire框架内部基本结构解析

    xfire框架内部基本结构解析1概述xfire是webservice的一个实现框架,是apache旗下CXF的前身,是一个比较被广泛使用的webservice框架,网上有很多关于如何使用xfire或cxf的helloworld

发表回复

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

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