快捷搜索:

科学知识

当前位置:betway必威官网手机版 > 科学知识 > betway必威官网手机版价值100元的华容道无解性证

betway必威官网手机版价值100元的华容道无解性证

来源:http://www.abirdfarm.com 作者:betway必威官网手机版 时间:2019-11-15 01:18

华容道作为80后和部分90一代的启蒙玩具,其经典度和怀旧感不逊李雷和韩梅梅。

本文送给欠我100元的某小三。

  在前面,有说用各种搜索方法(后面还将给出网友整理的八数码问题的十重境界) 来解决8 PUZZLE和15 PUZZLE问题。实际上,由于拼图游戏的种类繁多,我们可以延拓到两种比较特殊的类型:(1)M*N PUZZLE(2)N PUZZLE,(1)中的M*N当然是任意的正整数,而(2)中的N,这里指代的是一个正整数的平方和减一所得到的值。

效果图&DEMO

先介绍八数码问题:

betway必威官网手机版 1

1. Intro

最近华容道很火,可惜曹操去世得早,不然也能蹭个何猷君的热搜。关于最强大脑里赌王儿子的表现,到底是一掷千金还是智力超群,借用含光君的一句话:“未知全貌,不予置评。”

最近同样很火的游戏,还有一个头脑王者,可惜前几天由于未可知的原因被封了。

离开了头脑王者的我,就像高考前遇到车祸的考生。

为了检验自我的智商是否一下跌落到倔强青铜,我坚定地戳开了华容道小程序,准备接受知识的洗礼。

可谁能想到,我第一道题,就遇到了滑铁卢。

betway必威官网手机版 2

图1

棋盘到达图1这个状态之后,我又瞎戳了个三五分钟,仍是无解。

出于程序员的自我修养,我开始考虑,这会不会是小程序的bug?

也就是说,编写小程序的人并不是从棋盘原始状态(图2)出发,按上下左右移动的规则打乱棋盘,而是 瞎几把 随机初始化棋盘?

betway必威官网手机版 3

图2

为了证明我的猜想,我去洗了个头,接着开启了头脑风暴。

  betway必威官网手机版 4

betway必威官网手机版 5

 

它号称“古老的中国游戏,与七巧板、九连环等中国传统益智玩具一起是中国难题的代表作”。实际上,据死理性派考据,华容道其实可不是什么传统中国游戏,它由英国人弗莱明发明,在上世纪30年代传入中国,是重排九宫的简化版。

2. 随意证明一发

要如何证明图1状态的华容道是无解的?

我的不知道严不严谨的证明是:逆向思维。即证明从图2的原始状态是无法通过上下左右平移到达图1的状态的。

1 2 3 4 5 6 7 8 9 10 13 14这几个数字都各就各位之后,我们只需要关注右下角的2x2的4个方格。

如图3所示,空格以0表示,在这个2x2的方块内,我们从原始状态出发,经过多次平移,11 12 15这三个数字只可能出现如下几种排列方式。因为不论怎么移动,这四个格子都相当于做了顺时针或逆时针的旋转,而不可能出现图1中1215两两交换的局面。

betway必威官网手机版 6

图3

但是我这个糙证明被不愿意透露姓名的小三同学否定了,原因是11 12 15可以借助其他位置(如10 14 7 8)改变顺序。

为了反驳这位同学的观念,我提出了牛宝宝猜想:即,当除右下角的2x2方格以外的所有数字都归位时,该2x2方格中的数字只能有图3中的几种状态;换言之,如果该2x2方格中出现了其他状态,则1 2 3 4 5 6 7 8 9 10 13 14这几个数字的位置必然是打乱的。

然而,由于缺乏强大的理论支撑,证明陷入僵局。

可是,作为图灵的后人,怎么能被这点困难打倒呢?这岂不是告诉世人,我就是倔强青铜,倔强青铜就是我。

为了证明我王者的实力,我打开了万能的谷歌,准备抄抄别人的答案。奇妙的是,关于这个问题竟然只有一些只言片语的解读。最终,经过我的不懈努力,终于让我catch到了一个关键字:逆序数。

  如图所示,这是一个8*5数码的问题,当然,用之前的范式就不好办了。但是,之前也有说明十五数码的唯一解定理,由此,我们可以提出N数码问题的唯一解。

效果图

我们首先从经典的八数码问题入手,即对于八数码问题的任意一个排列是否有解?有解的条件是什么?

重排九宫,又称八数字推盘(8-puzzle),是和华容道一样的滑块游戏(sliding puzzle)。今天死理性派就来讲述这个流行全球的游戏背后的数学故事。

3. 从逆序数的角度证明无解性

  N数码问题的唯一解

一、准备工作

先了解一个定义和定理

定义:在一个1,2,...,n的排列中,如果一对数的前后位置与大小顺序相反,即前面的数大于后面的数,那么它们就称为一个逆序。一个排列中逆序的总数就称为这个排列的逆序数。逆序数为偶数的排列称为偶排列;逆序数为奇数的排列称为奇排列。如2431中,21,43,41,31是逆序,逆序数是4,为偶排列。——这是北大《高等代数》上的定义。

定理:交换一个排列中的两个数,则排列的奇偶性发生改变。

 

betway必威官网手机版 7

3.1 逆序数

逆序数是什么?我相信大家和我一样,是懵逼的。
不过我相信,通过我下面的浅显易懂的解读之后,你会在半分钟之内决定关掉这个网页。

逆序数是什么,我相信任何一个修过线性代数,学过行列式的人,都不会记得的。像我就不记得逆序数就是一个排列中所有逆序的总数
没错,这就是一句废话。我们还是来看一个例子吧。

  逆序对?空白(blank)起始时所在的点的行距距离目标点的欧几里得距离(dis)?这是在N*N-1数码问题中当N为偶数的时候能成立,当N为奇数的 时候,条件需要更弱一些,也就是说,当N为奇数的时候,在逆序和保持奇偶性相同的情况下,就能保证问题是唯一可解的。基于这一点(定理的证明可以详见相关 资料,或者按照15数码解的存在性定理的证明方法给出证明),这里给出判定N数码问题是否有唯一解的判定程序(HDOJ 3600):

二、实现过程

以3*3拼图为例进行分析

我在网上搜了半天,找到一个十分简洁的结论。八数码问题原始状态如下:

 

逆序数计算

2 7 8 1 3这个排列中,如果标准次序是从小到大的话,那么逆序对有:`(2, 7)`, `(2, 8)`, (2, 1), `(2, 3)`, `(7, 8)`, (7, 1), (7, 3), (8, 1), (8, 3), `(1, 3)`,共5个,因此这个排列的逆序数就为5

如果你坚持过了半分钟,到了这,恭喜你,你已经知道了逆序数是啥了。不如再坚持半分钟,来看一下神奇的逆序数定理。

  

1、随机打乱拼图

1)初始化从0-8的数组initializeNums

NSMutableArray *initializeNums = [NSMutableArray array];//初始化0-n数字
for (int i = 0; i < _puzzleCount; i  ) {
    [initializeNums addObject:@(i)];
}

2)从initializeNums随机抽取数字add到数组randomNums,得到随机数组

NSMutableArray *randomNums = [NSMutableArray array];//随机数组
for (int i = 0; i < _puzzleCount; i  ) {   
    int randomNum = arc4random() % initializeNums.count;
    [randomNums addObject:initializeNums[randomNum]];
    [initializeNums removeObjectAtIndex:randomNum];   
}

3)判断拼图是否可还原

图1,通过移动要还原到的拼图状态
图2,随机打乱的拼图状态
图3,将图2中的空白块移动到拼图右下角的拼图状态,用来计算打乱的拼图是否可以还原
④ 空白块处相当于数字8
⑤ 我们的目的是把打乱拼图如图2通过移动(空白块与相邻数字块位置交换)还原到图1状态
⑥ 不是每个随机打乱的拼图都能还原到图1状态(根据定义定理有50%概率随机打乱的拼图不能还原)
⑦ 根据定义定理图1的逆序数为0,为偶排列。所以只有图3也为偶排列,图2才有可能还原到图1状态

betway必威官网手机版 8

图1

betway必威官网手机版 9

图2

如何计算图3的逆序数

① 先计算图2的逆序数
② 再计算图2图3变换步数
③ 将两者相加即得图3逆序数

betway必威官网手机版 10

图3

判断图2是否可还原代码:

//判断是否可还原拼图
inverCount = 0;
int curNum = 0;
int nextNum = 0;
for (int i = 0; i < _puzzleCount; i  ) {
    curNum = [randomNums[i] intValue];
    if (curNum == _puzzleCount - 1) {
        inverCount  = _difficulty - 1 - (i / _difficulty);
        inverCount  = _difficulty - 1 - (i % _difficulty);
    }
    for (int j = i   1; j < _puzzleCount; j  ) {
        nextNum = [randomNums[j] intValue];
        if (curNum > nextNum) {
            inverCount  ;
        }
    }

}
if (!(inverCount % 2)) {//对2求余,余0,逆序数为偶数,即偶排列;否则,为奇排列
    return randomNums;
}

获得随机可还原的数组randomNums

- (NSMutableArray *)getNewAvailableRandomNums {

    //随机数字
    int inverCount = 0;
    while (1) {
        NSMutableArray *initializeNums = [NSMutableArray array];//初始化0-n数字
        for (int i = 0; i < _puzzleCount; i  ) {
            [initializeNums addObject:@(i)];
        }

        NSMutableArray *randomNums = [NSMutableArray array];//随机数组
        for (int i = 0; i < _puzzleCount; i  ) {

            int randomNum = arc4random() % initializeNums.count;

            [randomNums addObject:initializeNums[randomNum]];

            [initializeNums removeObjectAtIndex:randomNum];

        }
        //判断是否可还原拼图
        inverCount = 0;
        int curNum = 0;
        int nextNum = 0;
        for (int i = 0; i < _puzzleCount; i  ) {
            curNum = [randomNums[i] intValue];
            if (curNum == _puzzleCount - 1) {
                inverCount  = _difficulty - 1 - (i / _difficulty);
                inverCount  = _difficulty - 1 - (i % _difficulty);
            }
            for (int j = i   1; j < _puzzleCount; j  ) {
                nextNum = [randomNums[j] intValue];
                if (curNum > nextNum) {
                    inverCount  ;
                }
            }

        }
        if (!(inverCount % 2)) {//对2求余,余0,逆序数为偶数,即偶排列;否则,为奇排列
            return randomNums;
        }

    }
}

 

所有的重排九宫都可解吗?

在一个带框的木板上放入标有1到8的八个方块,在有限的空间内,怎样让这八个方块各归其位呢?最简单的做法当然是把方块都倒出来,然后放回去。当然这样有些无厘头,而且没有技术含量。不过如果真的把八块方块全倒出来再乱放回去,这样的8-puzzle还一定能重新复原吗?恐怕一些人早就听说过,对一个任意乱排的8-puzzle只有一半的可能性能够解开。有的人凭数学直觉可能就说了,这恐怕是奇偶性的问题吧。没错,当面对一个任意状态的8-puzzle时,我们可以根据其方块的排列方式算出一个整数,凭这个数的奇偶性就能断言8-puzzle可不可解。

而如何计算出这个数呢?这就要把方块排列方式“化归”到一个抽象的数学对象上,这样一来游戏规则(每步所允许的走法)就“化归”成了这个数学对象的某个属性,比如说奇偶不变性。所谓“化归”,是指在解决问题的过程中,数学家往往不是直接解决问题,而是对问题进行变形、转化,直到把它化归为某个(些)已解决,或容易解决的问题。

关于“化归法”有这样一个生动的解释,假设你能够用一个空水壶烧一壶热水。那如果所有条件不变,只是水壶中已有足够的水,该怎么办呢?通常人们会去进行下一个步骤。而数学家不这样,他们会倒去壶中的水,并且声称他们已经把这个问题化归成先前面已解决的的问题了。这虽是一个略带揶揄味道的笑话,不过至少说出了化归的基本特征。

betway必威官网手机版 11

 

逆序数定理

逆序数定理1:一个排列中的任意两个元素对换,排列的奇偶性会改变。

Q1:什么是排列的奇偶性?

  • 逆序数为奇数的排列称为奇排列
  • 逆序数为偶数的排列称为偶排列

Q2:什么是元素对换?

  • 在排列中,将任意两个元素对调,其余元素不变的操作,叫做元素对换;
  • 将相邻两个元素对换,叫做相邻对换

Q3:定理1证明?
我估计你们也不想看,有兴趣的自己戳链接:证明

  1  #include<iostream>
  2 
  3  #include<algorithm>
  4 
  5  //利用string库来读入一个谜题
  6 
  7  #include<string>
  8 
betway必威官网手机版,  9  using namespace std;
 10 
 11  
 12 
 13  //假设问题的规模(N的最大值不超过300)
 14 
 15  const int N=300 10;
 16 
 17  
 18 
 19  int s[N*N],g[N*N];
 20 
 21  
 22 
 23  //利用宏定义一个函数
 24 
 25  #define _cp(a,b) ((a)<=(b))
 26 
 27  
 28 
 29  int _tmp[N*N];
 30 
 31  
 32 
 33  //考察这个问题对应的所有状态的逆序数之和
 34 
 35  int solve(int n,int *a)
 36 
 37  {
 38 
 39    int l=n>>1;
 40 
 41    int i,j,r=n-1;
 42 
 43    //如下是求两个状态逆序对的差值,不过,这段代码确实有些乱,暂时没有弄明白
 44 
 45    int ret=(r>1 ? (solve(l,a) solve(r,a l)):0);
 46 
 47    for(i=j=0;i<=l;_tmp[i j]=a[i],i )
 48 
 49    {
 50 
 51      for(ret =j;j<r&&(i==l||!_cp(a[i],a[l j]));_tmp[i j]=a[l j],j );                                   
 52 
 53    }   
betway必威官网手机版价值100元的华容道无解性证明,回忆经典。 54 
 55    memcpy(a,_tmp,sizeof(int)*n);
 56 
 57    return ret;
 58 
 59  }
 60 
 61  
 62 
 63  int main()
 64 
 65  {
 66 
 67    int n;
 68 
 69    //每次读入一个问题前,先读入问题的规模
 70 
 71    while(scanf("%d",&n)==1&&n)   
 72 
 73    {
 74 
 75      int num=0;
 76 
 77      bool flag=true;
 78 
 79      //读入整个问题
 80 
 81      for(int i=0;i<n*n;i )
 82 
 83      {
 84 
 85        scanf("%d",&g[i]);
 86 
 87        //这里可以找到那个空白方块的位置
 88 
 89        if(flag&&g[i]!=0) num ;
 90 
 91        if(g[i]==0) flag=false;       
 92 
 93      }                       
 94 
 95      int temp=solve(n*n,g);
 96 
 97      //不考虑空白位置的逆序数  
 98 
 99      temp-=num;   
100 
101      //如果n为偶数的话,需要加上空格所在的行距离目标空格的行的dis距离
102 
103      if(!(n&1))
104 
105      {
106 
107        temp =(n-1-(num/n));           
108 
109      }
110 
111      //如果奇偶相异,则不可达,否则,为可达
112 
113      if(temp&1) puts("NO");
114 
115      else puts("YES");
116 
117    }
118 
119    return 0;
120 
121  }

2、初始化拼图UI (九宫格)

代码:

- (void)customUI {
    CGFloat puzzleBgViewX = 0;
    CGFloat puzzleBgViewY = 64   20;
    CGFloat puzzleBgViewW = [UIScreen mainScreen].bounds.size.width;
    CGFloat puzzleBgViewH = puzzleBgViewW;

    _puzzleBgView = [[UIView alloc] initWithFrame:CGRectMake(puzzleBgViewX, puzzleBgViewY, puzzleBgViewW, puzzleBgViewH)];
    _puzzleBgView.backgroundColor = [UIColor lightGrayColor];
    [self.view addSubview:_puzzleBgView];

    CGFloat puzzleBtnX = 0;
    CGFloat puzzleBtnY = 0;
    CGFloat puzzleBtnW = puzzleBgViewW / _difficulty - kPuzzleBtnGap * 2;
    CGFloat puzzleBtnH = puzzleBtnW;

    for (int i = 0; i < _puzzleCount; i  ) {
        puzzleBtnX = i % _difficulty * (puzzleBtnW   kPuzzleBtnGap * 2)   kPuzzleBtnGap;
        puzzleBtnY = i / _difficulty * (puzzleBtnH   kPuzzleBtnGap * 2)   kPuzzleBtnGap;
        UIButton *puzzleBtn = [UIButton buttonWithType:UIButtonTypeCustom];
        puzzleBtn.frame = CGRectMake(puzzleBtnX, puzzleBtnY, puzzleBtnW, puzzleBtnH);
        puzzleBtn.tag = i;
        puzzleBtn.clipsToBounds = YES;
        [_puzzleBgView addSubview:puzzleBtn];

        int  puzzleValue = [self.randomNums[i] intValue];
        if (puzzleValue == _puzzleCount - 1) {
            puzzleBtn.backgroundColor = [UIColor clearColor];
            _maxPuzzleBtn = puzzleBtn;
        } else {
                [puzzleBtn setTitle:[NSString stringWithFormat:@"%d", puzzleValue   1] forState:UIControlStateNormal];
                puzzleBtn.backgroundColor = [UIColor colorWithRed:0x4A / 255.0 green:0xC2 / 255.0 blue:0xFB / 255.0 alpha:1];
            [puzzleBtn addTarget:self action:@selector(puzzleBtnAction:) forControlEvents:UIControlEventTouchUpInside];
        }
    }
}

1 2 3

注定无人能拿下的1000刀

前面已经说过,8-puzzle的各种可能的初始排法里面,只有一半的排列方式能被解开。19世纪90年代,自称是15-puzzle(即8-puzzle的4×4扩展版)的发明人的Sam Loyd 曾悬赏1000美金,征求能仅仅把14和15交换的方法,这也就是著名的重排十五问题。一千美金在当时非常吸引人,导致很多人不务正业成了“赏金猎人”。但是很遗憾,谁也没有拿走这它,或者可以这样说,其实谁也拿不走这一千美金。

betway必威官网手机版 12

 

3.2 逆序数证明无解性

再贴一下图,我们要证明的是下面这个状态的华容道是无解的。怎么利用逆序数定理来证明呢?

betway必威官网手机版 13

首先,我们把这个棋盘按行拉长成一个队列:
s1 = 1 2 3 4 5 6 7 8 9 10 11 15 13 14 12 16
空格用16表示。

显然 ,原始状态的队列为:
s0 = 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

把它们两都看成排列的话,利用我们刚刚学的知识,s1的逆序数为:(15, 13), (15, 14), (15, 12), (13, 12), (14, 12),共5个。而s0的逆序数为0个。

是时候甩出我们的华容道定理了。

  N*M问题的唯一解

3、滑块移动逻辑

点击空白块周围数字块,数字块移到空白块区域(其实就是空白块和数字块交换)

betway必威官网手机版 14

图4

index:数字块对应位置如图4
_difficulty : 拼图列数
③ 点击数字块依次判断其 是否有空白块
④ 找到空白块,将点击数字块与空白块位置交换,实现数字块移动效果

以数字块3(index = 4)为例分析

upIndex = index - _difficulty 判断是否在九宫格里&&其位置对应的值是否是8,即空白块。

upIndex >= 0 && [self.randomNums[upIndex] intValue] == _puzzleCount - 1

downIndex = index _difficulty 判断是否在九宫格里&&其位置对应的值是否是8,即空白块。

if (downIndex <= _puzzleCount - 1 && [self.randomNums[downIndex] intValue] == _puzzleCount - 1

leftIndex = index - 1 判断是否在九宫格里&&其位置对应的值是否是8,即空白块

index % _difficulty > 0 && [self.randomNums[leftIndex] intValue] == _puzzleCount - 1

rightIndex = index 1 判断是否在九宫格里&&其位置对应的值是否是8,即空白块

index % _difficulty < _difficulty - 1 && [self.randomNums[rightIndex] intValue] == _puzzleCount - 1

代码:

- (void)puzzleBtnAction:(UIButton *)puzzleBtn {
    NSInteger index = puzzleBtn.tag;

    //上
    NSInteger upIndex = index - _difficulty;
    if (upIndex >= 0 && [self.randomNums[upIndex] intValue] == _puzzleCount - 1) {

        CGPoint maxPuzzleBtnCenter = _maxPuzzleBtn.center;
        CGPoint puzzleBtnCenter = puzzleBtn.center;
        _maxPuzzleBtn.tag = index;
        puzzleBtn.tag = upIndex;
        self.randomNums[upIndex] = @([self.randomNums[index] intValue]);
        self.randomNums[index] = @(_puzzleCount - 1);
        [UIView animateWithDuration:0.35 animations:^{
            puzzleBtn.center = maxPuzzleBtnCenter;
            _maxPuzzleBtn.center = puzzleBtnCenter;
        }];

        [self isWin];

        return;

    }
    //下
    NSInteger downIndex = index   _difficulty;
    if (downIndex <= _puzzleCount - 1 && [self.randomNums[downIndex] intValue] == _puzzleCount - 1) {
        CGPoint maxPuzzleBtnCenter = _maxPuzzleBtn.center;
        CGPoint puzzleBtnCenter = puzzleBtn.center;
        _maxPuzzleBtn.tag = index;
        puzzleBtn.tag = downIndex;
        self.randomNums[downIndex] = @([self.randomNums[index] intValue]);
        self.randomNums[index] = @(_puzzleCount - 1);
        [UIView animateWithDuration:0.35 animations:^{
            puzzleBtn.center = maxPuzzleBtnCenter;
            _maxPuzzleBtn.center = puzzleBtnCenter;
        }];

        [self isWin];
        return;
    }
    //左
    NSInteger leftIndex = index - 1;
    if (index % _difficulty > 0 && [self.randomNums[leftIndex] intValue] == _puzzleCount - 1) {
        CGPoint maxPuzzleBtnCenter = _maxPuzzleBtn.center;
        CGPoint puzzleBtnCenter = puzzleBtn.center;
        _maxPuzzleBtn.tag = index;
        puzzleBtn.tag = leftIndex;
        self.randomNums[leftIndex] = @([self.randomNums[index] intValue]);
        self.randomNums[index] = @(_puzzleCount - 1);
        [UIView animateWithDuration:0.35 animations:^{
            puzzleBtn.center = maxPuzzleBtnCenter;
            _maxPuzzleBtn.center = puzzleBtnCenter;
        }];

        [self isWin];
        return;
    }
    //右
    NSInteger rightIndex = index   1;
    if (index % _difficulty < _difficulty - 1 && [self.randomNums[rightIndex] intValue] == _puzzleCount - 1) {
        CGPoint maxPuzzleBtnCenter = _maxPuzzleBtn.center;
        CGPoint puzzleBtnCenter = puzzleBtn.center;
        _maxPuzzleBtn.tag = index;
        puzzleBtn.tag = rightIndex;
        self.randomNums[rightIndex] = @([self.randomNums[index] intValue]);
        self.randomNums[index] = @(_puzzleCount - 1);
        [UIView animateWithDuration:0.35 animations:^{
            puzzleBtn.center = maxPuzzleBtnCenter;
            _maxPuzzleBtn.center = puzzleBtnCenter;
        }];

        [self isWin];
        return;
    }

}

4 5 6

滑块游戏可解性分析

其实早在1879年,Johnson 和 Story 两位数学家就证明了“重排十五”是不可解的。而他们使用的方法正是计算前文提到的那个整数——方块初始排列状态的逆序数。如果用数字9标识空白位置 ,那么下面这种情况方块的排序状态就可以记作 [2 3 1 4 5 6 7 8 9]。

betway必威官网手机版 15

容易看出[2,1],[3,1]是逆序的,即这里α=2(注意始终9表示空白方块,实际是不存在的,所以不在考察范围内)。逆序数在这里的实际意义是,如果上述这个状态的puzzle要回到自然状态[1 2 3 4 5 6 7 8 9],则需交换第二格和第三格,再交换第一格和第二格,共计步数为2。根据逆序数的奇偶性,Johnson 和 Story把方块的排列状态分为偶状态和奇状态。自然你也可以多余的随便交换别的两格再交换回来(在实际游戏过程中你确实可能出现这样的反复操作),不过我们只关心α的奇偶性。而奇妙之处正在于,遵循游戏规则的移动方式不可能改变方块排列状态的奇偶性!因为数字左右移动时状态对应的数列没有变化,故逆序数不变;而当数字从上往下(或者从下往上)移动时,例如方块 a i 下移时,相当于往后挪动了三个位置,即[ a 1 … a i a i 1 a i 2 … a 8 ]→[a 1 … a i 1 a i 2 a i … a 8 ],实际上就是 a i 与 a i 1 , a i 与 a i 2 依次进行邻换(数列中相邻两个数码相互交换),根据代数中的定理可知,一个数列经过偶数次的邻换,产生的新数列与原数列的逆序数奇偶性相同。因此重排九宫中,方块的移动不会改变其逆序数的奇偶性。说到这里问题就变得明了了,通过判断初始状态与目标状态的α值就能判定这个puzzle是否可解。而这个结论则可以推广到任意m×n型的滑块游戏中去。

回到重排十五问题,这个puzzle的初始状态[1 2 3 4 5 6 7 8 9 10 11 12 13 15 14 16]的逆序数是1([15 14]),与目标状态[1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16]的逆序数α=0奇偶性不同,所以必然不可解。

华容道定理第一弹

华容道定理1:按照游戏规则移动方块不会改变排列的逆序数奇偶性。

这是网上很多人提的一个证明思路。
下面我们来证明一下这个定理是错误的。【接受反驳】

证明:
根据逆序数定理,上下平移或左右平移,相当于交换了某个元素和空格元素的顺序,排列奇偶性会发生改变。

比如将图2原始状态中的12向下移动到15的右边,则s = 1 2 3 4 5 6 7 8 9 10 11 16 13 14 15 12,相当于交换了1216的位置,这时逆序数为7,而原始逆序数为0,奇偶性发生改变。

  在POJ的2893中,原问题被更进一步地扩展,但是,原理还是相同的,而且,我们可以得到更为本质化的结论:当N为完全平方模型的时候,似乎是由N来决 定原理的,而实际上,如果问题被延拓为N*M,我们可以发现,一个更为本质的结论,原问题的可解性实际上是由列数M来判定的,这样,由特殊推广到了一般, 证明如下(这里我们可以看出,行和列都起到了一定的作用,列的作用确定了空白方块是否要考虑,而在空白方块的位置需要考虑的情况下,行的作用又让它必须了解到底要增加多少(也就是行增量,欧几里得距离)):

*4、另一种打乱拼图的方法

思路:将图1经过有限次数随机移动达到打乱拼图的目的,这样打乱的拼图肯定是可还原的。

代码:

- (NSMutableArray *)getNewAvailableRandomNums2 {

   NSMutableArray *randomNums = [NSMutableArray array];//随机数组 - 初始化0-n数字
    for (int i = 0; i < _puzzleCount; i  ) {
        [randomNums addObject:@(i)];
    }

    int randCount = _puzzleCount * _puzzleCount;
    int randDirection = 0; //0 上 1 下 2 左 3 右
    BOOL aliableDirection = NO;
    int blankIndex = 8;
    int index = 0;
    while (randCount--) {

        aliableDirection = NO;
        randDirection = arc4random() % 4;
        while (1) {
            switch (randDirection) {
                case 0:

                    if (blankIndex / _difficulty > 0) {
                        index = blankIndex - _difficulty;
                        aliableDirection = YES;
                    }
                    break;
                   case 1:

                    if (blankIndex / _difficulty < _difficulty - 1) {
                        index = blankIndex   _difficulty;
                        aliableDirection = YES;
                    }
                    break;
                case 2:

                    if (blankIndex % _difficulty > 0) {
                        index = blankIndex - 1;
                        aliableDirection = YES;
                    }
                    break;
                case 3:

                    if (blankIndex % _difficulty < _difficulty - 1) {
                        index = blankIndex   1;
                        aliableDirection = YES;
                    }
                    break;
                default:
                    break;
            }
            if (aliableDirection == YES) {
                break;
            }
            randDirection = (randDirection   1) % 4;
        }

        randomNums[blankIndex] = @([randomNums[index] intValue]);
        randomNums[index] = @(8);
        blankIndex = index;

    }
    return randomNums;
}

7 8

8-puzzle的操作攻略

前面已经细述如何判断任意状态的滑块游戏的可解性。那当面对一个的确可解的重排九宫时,又怎样移动方块,排列出目标状态呢?

这里提供一个三角轮换法则。仍用9代表空白方格,当它和三个方格(比如abc)构成一个矩形时,三个方格的位置就可通过简单的操作任意互换,如图所示。

betway必威官网手机版 16

而8-puzzle里任何三个字块只要能组成一个三角形,它们的位置都可以互换,因为空白方格总是可以先移动到指定位置与这个三角形构成矩形,在执行完互换后再原路返回,而其他格子的位置不会有变。比如我们现在要轮换abe三个方块之间的位置:

betway必威官网手机版 17

这样一来,问题就化归为如何用这种三角形轮换来把8-puzzle解开了,这恐怕就不是什么难题了。

华容道定理第二弹

华容道定理2:若某状态的排列的逆序数加上空格元素行号和列号的奇偶性 ≠ 原始状态的排列的逆序数加上空格元素行号和列号的奇偶性,则该状态是无解的。

一句话证明:
空格元素和某个元素交换位置,则排列的逆序数的奇偶性就改变一次。交换后空格元素的行号或者列号会加1或减1,即行号,列号之和的奇偶性也改变一次。

要看完整证明,戳:完整证明

还是以刚刚的s = 1 2 3 4 5 6 7 8 9 10 11 16 13 14 15 12为例,此时该排列的逆序数加上空格元素行号和列号 = 7 3 4 = 14,仍为偶数。

而我们要证明无解的状态(图1)的排列 s' = 1 2 3 4 5 6 7 8 9 10 15 13 14 12 16,其逆序数加上空格元素行号和列号 = 5 4 4 = 13,为奇数,很明显,这是无解的啦。

得证。

  假设这个矩阵有3列,且逆序对总数设为N(这里不失一般性地假设a1<a2)

三、其他细节功能

1、难度选择 3*3(低), 4*4(中), 5*5(高)
2、自定义图片拼图(相机和相册)
3、图片拼图提示
4、步数统计
5、最佳记录
6、移动提示音设置

具体请下载demo查看

 

Source

  • 逆序数和对换
  • 知乎-求数字华容道到这一步就不会了,是因为我一开始出题错了吗?无解吗?
  • 知乎-数字华容道会出现无解的情况吗?
  • 拼图游戏可还原性算法分析

    (1)首先,对于可左右移动的数字,它左右移动是不会对逆序对总数产生影响;

四、参考

1、不可还原拼图
2、回忆经典,讲述滑块游戏背后的数学故事
3、吴昊品游戏核心算法 Round 17 —— 吴昊教你玩拼图游戏(15 puzzle)

为了方便讨论,我们把它写成一维的形式,并以0代替空格位置。那么表示如下:

    (2)若数字a0上下移动的话会移到它之前或之后的两个数字的位置,假设是向上移动,且这两个数字为a1,a2:(3个数字肯定是不同数字)

 

         若a0 < a1 < a2,则新的逆序对总数为N-2,

1 2 3 4 5 6 7 8 0

         若a1 < a0 < a2, 则新的逆序对总数为N - 1 1 = N,

 

         若a1 < a2 < a0, 则新的逆序对总数为N 2,

通过实验得知,以下状态是无解的(交换了前两个数字1 2):

       由此可见,数字的移动是不影响矩阵逆序对总数的奇偶性的,推广到列数为奇数的情况也是一样。那么若判定初始矩阵与目标矩阵的逆序对总数是否相同,即可判定问题是否可解,若同则可解,否则不可解。

 

      若列数为偶数的话,数字左右移动同理不影响,但是上下移动一次会改变一次逆序对总数的奇偶性,所以对于这种情况,我们可以计算初始矩阵0的位置到目标矩阵 0的位置的差值 S ,这样可以判定奇偶性被如何改变了。由于0最终是要到目标位置的,所以无论0在工程中如何移动,逆序对的奇偶性只和S有关。那有些人可能会想,我们怎么只 考虑0的上下移动,不考虑其他数字的上下移动,我们可以这样想,无论那个数字要移动都是要和0交换位置,也就是说无论那个数字的移动都是0的移动,所以在 这里我们就只分析0的上下移动即可。

2 1 3 4 5 6 7 8 0

  这里可以采用归并排序来解决逆序对的问题,代码如下(这里换一种方法,利用归并排序来求逆序对的总数之和):

 

  

八数码问题的有解无解的结论:

  1 #include<iostream>
  2 
  3  
  4 
  5  using namespace std;
  6 
  7  
  8 
  9  #define MAXN 1000005
 10 
 11  
 12 
 13  int cnt;
 14 
 15  int a[MAXN],c[MAXN];
 16 
 17  
 18 
 19  //利用归并排序来求逆序数
 20 
 21  void MergeSort(int l,int r)
 22 
 23  {
 24 
 25    int mid,i,j,tmp;
 26 
 27    //直到左右缝合为止
 28 
 29    if(r>l 1)
 30 
 31    {
 32 
 33      mid=(l r)/2;
 34 
 35      MergeSort(l,mid);
 36 
 37      MergeSort(mid,r);
 38 
 39      tmp=l;
 40 
 41      //找到所有的逆序对,这一段也暂时不是很明白
 42 
 43      for(i=l,j=mid;i<mid&&j<r;)
 44 
 45      {
 46 
 47        if(a[i]>a[j])
 48 
 49        {
 50 
 51          c[tmp ]=a[j ];
 52 
 53          cnt =mid-i;
 54 
 55        }
 56 
 57        else c[tmp ]=a[i ];
 58 
 59      }
 60 
 61      while(j<r)   c[tmp ]=a[j ];
 62 
 63      while(i<mid) c[tmp ]=a[i ];
 64 
 65      for(i=l;i<r; i)   a[i]=c[i];
 66 
 67    }
 68 
 69  }
 70 
 71  
 72 
 73  int main()
 74 
 75  {
 76 
 77    int n,m,pl;
 78 
 79    //读入问题的规模,以(0,0)结尾
 80 
 81    while(scanf("%d%d",&n,&m)!=EOF)
 82 
 83    {
 84 
 85      if(n == 0 || m == 0) break;
 86 
 87      //这个用来标记逆序对的和
 88 
 89      cnt = 0;
 90 
 91      //这个用来标明当前处理的方块的位置
 92 
 93      pl = 0;
 94 
 95      int x,loc0;
 96 
 97      for(int i = 0; i < n*m; i )
 98 
 99      {
100 
101        scanf("%d",&a[pl]);
102 
103        if(a[pl] == 0)
104 
105        {
106 
107          x = pl/m;
108 
109          loc0 = pl;
110 
111        }
112 
113        pl ;
114 
115      }
116 
117      MergeSort(0,pl);
118 
119      //扣除0的逆序数
120 
121      cnt -= loc0;
122 
123      int step = 0;
124 
125      //若列数为奇数,则数字的上下左右移动都不影响最终逆序对的总数
126 
127      if(m%2 == 1)
128 
129        step = 0;
130 
131      //若列数为偶数,左右移动不影响,但上下移动一次,会改变一次逆序对总数的奇偶性
132 
133      else
134 
135        step = n - 1 - x;
136 
137      //初始,结束状态的逆序对总数奇偶性一致,则问题可解
138 
139      if(step%2 == cnt % 2)
140 
141        printf("YESn");
142 
143      else
144 
145        printf("NOn");
146 
147    }
148 
149    return 0;
150 
151  }

 

  进一步推广,魔方,七巧板,华容道……

一个状态表示成一维的形式,求出除0之外所有数字的逆序数之和,也就是每个数字前面比它大的数字的个数的和,称为这个状态的逆序。

  betway必威官网手机版 18 

 

  如图,这是一个魔方,是由N*N*N个小立方体组成的。我们这里随意拿走一个小立方体,并假设整个结构没有被破坏。那么,这是一次更普遍的飞跃,由二维空间上升到了三维空间。但是,其解的唯一性定律还适用嘛?答案是肯定的,证明如下:

若两个状态的逆序奇偶性相同,则可相互到达,否则不可相互到达。

  魔方数码问题的解的唯一性定理

 

  考虑左右移动空格,逆序不变;同一层上下移动空格,跨过N-1个格子;上下层移动空格,跨过N^2-1个格子。

由于原始状态的逆序为0(偶数),则逆序为偶数的状态有解。

  当N为奇数时,N-1和N^2-1均为偶数,也就是任意移动空格逆序奇偶性不变。那么逆序奇偶性相同的两个状态可相互到达。

 

  当N为偶数时,N-1和N^2-1均为奇数,也就是令空格位置到目标状态空格位置的y z方向的距离之和,称为空格距离。若空格距离为偶数,两个逆序奇偶性相同的状态可相互到达;若空格距离为奇数,两个逆序奇偶性不同的状态可相互到达。

也就是说,逆序的奇偶将所有的状态分为了两个等价类,同一个等价类中的状态都可相互到达。

  七巧板

 

  更为一般性的拓展,我们可以考虑到其图形不一定是正方形或者是正方体,比如,我们国家民间的七巧板游戏,这些方块的形状都不是正方形,甚至彼此都不一定相 同,但是,经过一定的组合之后,却构成了一个比较好玩的游戏。但是,这个游戏并不是通过方块的滑动来实现的,而是放置,所以,在这一点上看,软件的实现比 较简单。

简要说明一下:当左右移动空格时,逆序不变。当上下移动空格时,相当于将一个数字向前(或向后)移动两格,跳过的这两个数字要么都比它大(小),逆序可能±2;要么一个较大一个较小,逆序不变。所以可得结论:只要是相互可达的两个状态,它们的逆序奇偶性相同。我想半天只能说明这个结论的必要性,详细的证明请参考后面的附件。

  betway必威官网手机版 19

 

  其实现并不复杂,只要给出固定的解,每一次比对是否将图形安装到固定的位置就可以了,如图所示,这是其中的一款游戏:

 

  betway必威官网手机版 20

>推广二维N×N的棋盘

  华容道

 

  更复杂的游戏,比如华容道的AI,就要考虑很多因素,因为,不同的方块形状是不一样的,不过,索性还有一定的规则可以追寻,其实现目前很多,我用的是一个中学老师的AI版本(他写成了一篇论文)。我之后会单独以一个Round来放送的。

我们先来看看4×4的情况,同样的思路,我们考虑移动空格时逆序的变化情况。

  betway必威官网手机版 21

 

 

1 2 3 4

 

5 6 7 8

---恢复内容结束---

9 A B C

D E F

 

我们用字母A~F代替数字10~15。同样地,当左右移动的时候,状态的逆序不改变。而当上下移动的时候,相当于一个数字跨过了另外三个格子,它的逆序可能±3或±1,逆序的奇偶性必然改变。那么又该如何

 

1 2 3 4

5 6 7 8

9 A B

C D E F

 

可以证明,以上状态是一个无解的状态(将C移到了第四行)。该状态的逆序为0,和原始状态相同,但是它的空格位置在第三行。若将空格移到第四行,必然使得它的逆序±1或±3,奇偶性必然改变。所以它是一个无解的状态。

 

然而以下状态就是一个有解的状态(交换了前两个数字1 2):

 

2 1 3 4

5 6 7 8

9 A B

C D E F

 

这个状态的逆序为1,和原始状态奇偶性不同,而空格位置在第三行。由于空格每从第三行移动到第四行,奇偶性改变。则该状态的可到达原始状态。

 

通过观察,得出以下结论:

 

N×N的棋盘,N为奇数时,与八数码问题相同。

 

N为偶数时,空格每上下移动一次,奇偶性改变。称空格位置所在的行到目标空格所在的行步数为空格的距离(不计左右距离),若两个状态的可相互到达,则有,两个状态的逆序奇偶性相同且空格距离为偶数,或者,逆序奇偶性不同且空格距离为奇数数。否则不能。

 

也就是说,当此表达式成立时,两个状态可相互到达:(状态1奇偶性==状态2奇偶性)==(空格距离%2==0)。

 

此结论只是由观察得知的,但是还没证明过,请高手指点。

 

另外再详细说明一下,无论N是奇数还是偶数,空格上下移动,相当于跨过N-1个格子。那么逆序的改变可能为一下值±N-1,±N-3,±N-5 …… ±N-2k-1。当N为奇数数时N-1为偶数,逆序改变可能为0;当N为偶数时N-1为奇数,逆序的改变不能为0,只能是奇数,所以没上下移动一次奇偶性必然改变。

 

 

>推广到三维N×N×N

 

其实,三维的结论和二维的结论是一样的。

 

考虑左右移动空格,逆序不变;同一层上下移动空格,跨过N-1个格子;上下层移动空格,跨过N^2-1个格子。

 

当N为奇数时,N-1和N^2-1均为偶数,也就是任意移动空格逆序奇偶性不变。那么逆序奇偶性相同的两个状态可相互到达。

 

当N为偶数时,N-1和N^2-1均为奇数,也就是令空格位置到目标状态空格位置的y z方向的距离之和,称为空格距离。若空格距离为偶数,两个逆序奇偶性相同的状态可相互到达;若空格距离为奇数,两个逆序奇偶性不同的状态可相互到达。

 

讨论到这里,题目问题也就解决了。

 

另外水木清华BBS论坛中有人提到:

 

8数码难题搜索时,有时候是无解的,8数码问题总共有9!种状态,如果用计算机一

个一个去搜索去判断哪些有解哪些误解,无疑要花费很长的时间,也没必要。作为一种

智力游戏,玩之余,我在想,能否通过事先的分析来判断哪些问题有解,哪些问题无解

呢?对于有解的问题,是否能通过一种固定的步骤来得到解?经过昨天晚上和今天的仔

细分析,我觉得我已经得到了这个问题的初步解答,下面我公布一下我得到的结果和证

明,抛砖引玉,如果大家发现其中有什么问题,欢迎来我宿舍一起讨论或者给我发Emai

l。

我的证明分好几个步骤,恳请大家能够耐心的看下去,我会尽量说得简洁一点。

 

一、我的结论

我们将九宫格按行排成一行共九个数(空格也占一个位置,在本文种,我用@表示空

格)。比如: 1 2 3 4 @ 5 => 1 2 3 4 @ 5 6 7 8 6 7 8 这样

,九宫格的每一种状态和上图的行之间是一一对应的。在代数上册我们学过逆序的概念

,也就是对于任意一对数,如果前面的数比后面的数大,则为一对逆序。对于一个序列

,我们定义其逆序奇偶性如下: 如果其中有奇数对逆序,称之逆序奇;如果其中有

偶数对逆序,称之为逆序偶。这样,对于1,2,...,n这n个数,其所有的排列可以分为

两类,逆序奇类和逆序偶类。相对应的,九宫图(除去空格)也有它的奇偶性,我们的定

理是:

所有的奇九宫图之间是可达的,所有的偶九宫图之间也是可达的,但奇九宫图和偶

九宫图之间互不可达。

 

二、问题的转化

为了证明上述定理,我想先对问题进行一下转化。我定义两种行序列的变换:一种

是空格@和相邻的数对换,一种是空格@和前后隔两个数的数之间的对换,前者对应着空

格在九宫图中的左右移动,后者对应着空格在九宫图中的上下移动。

 

引理一:在上述的两种对换下,序列的奇偶性不改变。 这个引理很容易证明。

首先,相邻的对换肯定不改变奇偶性;其次,隔两格的对换也不改变奇偶性,它相当于

三个数的轮换,我们可以自己列举一下几种情况验证一下。这就说明了奇九宫图和偶九

宫图之间是互不可达的。

 

引理二:转化后行序列在上面定义的两种对换下的任意操作,可以转换成九宫图中

空格的合法变化。 这个引理也是比较容易证明的。我们只要证明如下的几种状态之

间是互达的: a b c a b @ a b c a b c @ d e <=>

c d e d e f <=> d e @ f g h f g h @ g h f

g h 通过计算机搜索,可以发现上面两对状态之间的确是互达的。从而,我们可以

假定上面两种状态之间的转换可以用行序列中的两种邻对换来代替。

想提一点的是,九宫图之间的变换是可逆的。下面,到了问题的核心部分了。

 

引理三:所有的奇状态可以转换为 @ 1 2 3 4 5 6 7 8, 所有的偶状态

可以转换为 @ 2 1 3 4 5 6 7 8. 要证明这个引理,得分几个步骤。我的想法是先设

法把8移到最后一个,然后8保持不动(注意,我们这里的不动只是形式上不动,但不管怎

样,我们的每一个变换后,8还是保持在最后一个,余类似),再将7移到8之前,然后,

保持7和8不动,依次移动6,5,4,3,得到 * * * 3 4 5 6 7 8这里 * * *是 @ 1 2 的

一个排列。到这里,我想要得到前面的两种状态之一是显然的了。下面,我说明,上面

的想法是可以实现的。如下:

  1. 对于 a b c @ ,我们可以将其中的任意一个移到

最后,并且对变换仅限于这四个位置上。显然,对于a,c是一步就可以做到的。对于b,

步骤如下: a b c @ -> @ b c a -> b @ c a -> b c @ a -> b c a @ -> @ c a b

2. 先把要移到最后位置的那个数移到最后四个位置之一,然后再将空格移到最后一

个位置,用1的方法将待移动的数变换到最后一个位置。循环这样做即可。 引理三证

毕。

 

证完了这三个引理,定理的成立就是显然的了。首先,将奇偶性相同的两种状态都

变换到上述两种标准状态之一,然后对其一去逆变换即可。以上是我的所有证明,有些

地方在计算机上写起来不是太清楚。

 

 

ps:

 

 

#include <stdio.h>
int a[90010],b[90010],nxs;

void mergeSort(int first,int last)
{
    int mid,i;
    int begin,m,end;
    if(first 1<last)
    {
       mid=(first last)/2;       
       //merge(first,mid,last);
       begin=first;
       m=mid;
       i=first;
       mergeSort(first,mid);
       mergeSort(mid,last);
       while(begin<mid && m<end)
       {
          if(a[begin]<=a[m])
          {
              b[i  ]=a[begin  ];          
          }
          else 
          {
              b[i  ]=a[m  ];             
              //for(i=beginA;i<=mid;i  )
                  //printf("nixuyou:%d,%dn",a[i],a[beginB]);
              nxs =mid-begin;     
          }                    
       }                  
       while(begin<mid)
       {
          b[i  ]=a[begin  ];            
       }
       while(m<last)
       {
          b[i  ]=a[m  ];             
       }
       /*for(i=0;i<j;i  )
       {
          a[first i]=b[i];                
       }*/
       while(first<last)
       {
          a[first]=b[first  ];                 
       }     
    }
}


int main()
{
   int n,sum,i,iwz,hangshu,hangshucha,panduanshu,j,x;
   while(scanf("%d",&n)==1 && n)
   {
        sum=n*n;
        j=0;
        for(i=0;i<sum;i  )
        {
            scanf("%d",&x);
            if(x==0)
            {   
                iwz=i;
            }        
            else
            {
                a[j]=x;
                j  ;
            }
        }
        nxs=0;
        mergeSort(0,sum-1);
        //printf("nxs=%dn",nxs);    
        if(n%2==1) //n为奇数
        {
              if(nxs%2==0)
                   printf("YESn");
              else 
                   printf("NOn");         
        }
        else //n为偶数
        {
             hangshu=iwz/n;
             hangshucha=n-1-hangshu;
             //printf("hangshucha=%dn",hangshucha);
             panduanshu=nxs hangshucha;
             if(panduanshu%2==0)
                   printf("YESn");
              else 
                   printf("NOn");      
        }                        
   } 
   return 0;    
}

 

 

//题解:八数码问题,逆序数

//代码:

#include<stdio.h>

#define SIZE_N 90010

int ary[2][SIZE_N];
int sum,len;

void reverseNum(int l,int h,int idx)
{
    int i,j,k;
    int mid,idxt;

    idxt = 1 - idx;
    if(l == h) {
        ary[1][l] = ary[0][l];
        return ;
    }
    mid = (l   h) / 2;
    reverseNum(l, mid, idxt);
    reverseNum(mid 1, h, idxt);
    for(i = j = l,k = mid 1;i <= mid && k <= h;) {
        if(ary[idx][i] < ary[idx][k]) {
            ary[idxt][j  ] = ary[idx][i];
            sum  = k - mid - 1;
            i   ;
        }
        else {
            ary[idxt][j  ] = ary[idx][k];
            k   ;
        }
    }
    for(i;i <= mid;i   ) {
        ary[idxt][j  ] = ary[idx][i];
        sum  = h - mid;
    }
    for(k;k <= h;k   ) {
        ary[idxt][j  ] = ary[idx][k];
    }
}

int main()
{
    int n;
    int i;

    while(scanf("%d",&n),n != 0) {
        len = n * n;
        for(i = 0;i < len;i   ) {
            scanf("%d",&ary[0][i]);
            if(ary[0][i] == 0) {
                if(!(n & 1)) {
                    sum = (n - i / n - 1);
                }
                else {
                    sum = 0;
                }
                i --;
                len --;
            }
        }
        if(n == 1) {
            puts("YES");
            continue;
        }
        reverseNum(0, len-1, 0);
        if(sum & 1) {
            puts("NO");
        }
        else {
            puts("YES");
        }
    }
    return 0;
}

 

本文由betway必威官网手机版发布于科学知识,转载请注明出处:betway必威官网手机版价值100元的华容道无解性证

关键词: