iOS 滑块拼图游戏（Puzzle8）

客官°小女子只卖身不卖艺 2022-05-30 03:42 243阅读 0赞

> 代码地址如下：  
> [http://www.demodashi.com/demo/11505.html][http_www.demodashi.com_demo_11505.html]

### 一、准备工作 ###

> 先了解一个定义和定理

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

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

### 二、项目结构 ###

![项目结构][hQtVTPuJiwYksonBUoE.png]

### 三、实现过程 ###

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

##### 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`状态

图1  
![eogVmKGyowY6UjpQ6X6.png][]

图2  
![wVr5tog2D7tDeIBv9Q9.png][]

如何计算`图3`的逆序数

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

图3  
![1lS69zGNHPGchBfS2Rt.png][]

判断`图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;
            }
        }
    }

###### 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];
            }
        }
    }

###### 3、滑块移动逻辑 ######

> 点击空白块周围数字块，数字块移到空白块区域（其实就是空白块和数字块交换）

图4  
![图4][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、另一种打乱拼图的方法 ######

> 思路：将`图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;
    }

### 四、其他细节功能 ###

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

> 具体请下载demo查看

### 五、实现效果 ###

效果图  
!效果图

### 六、参考 ###

1、[不可还原拼图][Link 1]  
2、[回忆经典，讲述滑块游戏背后的数学故事][Link 2]  
3、[吴昊品游戏核心算法 Round 17 —— 吴昊教你玩拼图游戏（15 puzzle）][Round 17 _ _15 puzzle]

iOS 滑块拼图游戏（Puzzle8）

> 代码地址如下：  
> [http://www.demodashi.com/demo/11505.html][http_www.demodashi.com_demo_11505.html]
> 
> 注：本文著作权归作者，由demo大师发表，拒绝转载，转载需要作者授权

[http_www.demodashi.com_demo_11505.html]: http://www.demodashi.com/demo/11505.html
[hQtVTPuJiwYksonBUoE.png]: /images/20220530/7c481385dc6848a6ac978eed00fb4e99.png
[eogVmKGyowY6UjpQ6X6.png]: /images/20220530/f3e9b8935145433b87c46ea563e2ac6f.png
[wVr5tog2D7tDeIBv9Q9.png]: /images/20220530/54bf4084b0854fb4b29799fb272bf6b5.png
[1lS69zGNHPGchBfS2Rt.png]: /images/20220530/84d61d6b893d43b0a29062dbf9beafb1.png
[4]: /images/20220530/fa54b58f80364f8789b90a569b1eede3.png
[Link 1]: https://baike.baidu.com/item/%E4%B8%8D%E5%8F%AF%E8%BF%98%E5%8E%9F%E7%9A%84%E6%8B%BC%E5%9B%BE
[Link 2]: http://www.guokr.com/article/54088/
[Round 17 _ _15 puzzle]: http://www.cnblogs.com/tuanzang/archive/2013/04/05/3001003.html