效果圖&DEMO
一舌涨、準備工作
先了解一個定義和定理
定義：在一個1,2,...,n的排列中计呈，如果一對數的前后位置與大小順序相反周霉，即前面的數大于后面的數姚炕，那么它們就稱為一個逆序族壳。一個排列中逆序的總數就稱為這個排列的逆序數这橙。逆序數為偶數的排列稱為偶排列陡厘；逆序數為奇數的排列稱為奇排列。如2431中铅协，21，43摊沉，41狐史，31是逆序，逆序數是4说墨，為偶排列骏全。——這是北大《高等代數》上的定義尼斧。
定理：交換一個排列中的兩個數姜贡，則排列的奇偶性發(fā)生改變。
二棺棵、實現過程
以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烛恤，是隨機打亂的拼圖通過移動（空白塊與相鄰數字塊位置交換）要還原到的拼圖狀態(tài)
②圖2母怜，是隨機打亂的拼圖狀態(tài)
③圖3，是將圖2中的空白塊通過若干次移動（空白塊與相鄰數字塊位置交換）后空白塊到拼圖右下角的拼圖狀態(tài)缚柏，用來計算判斷打亂的拼圖是否可以還原
④ 空白塊處相當于數字8
⑤ 我們的目的是把打亂拼圖如圖2通過移動（空白塊與相鄰數字塊位置交換）還原到圖1狀態(tài)
⑥ 不是每個隨機打亂的拼圖都能還原到圖1狀態(tài)（根據定義和定理有50%概率隨機打亂的拼圖不能還原）
⑦ 根據定義和定理苹熏，圖1的逆序數為0，為偶排列币喧。所以只有圖3也為偶排列轨域，圖2才有可能還原到圖1狀態(tài)
如何計算圖3的逆序數
① 先計算
圖2的逆序數
② 再計算圖2到圖3變換步數
③ 將兩者相加即得圖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;
}
}
}
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自点、滑塊移動邏輯
點擊空白塊周圍數字塊，數字塊移到空白塊區(qū)域（其實就是空白塊和數字塊交換）
① 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;
}
三塘淑、其他細節(jié)功能
1、難度選擇 3*3（低）蚂斤， 4*4（中）存捺， 5*5（高）
2、自定義圖片拼圖（相機和相冊）
3曙蒸、圖片拼圖提示
4捌治、步數統(tǒng)計
5、最佳記錄
6纽窟、移動提示音設置
具體請下載demo查看
四肖油、參考
1、不可還原拼圖
2师倔、回憶經典构韵，講述滑塊游戲背后的數學故事
3、吳昊品游戲核心算法 Round 17 —— 吳昊教你玩拼圖游戲（15 puzzle）
