仅仅是一个拼图的游戏？不，它可以自己复原。
前言
很早之前写过一个拼图的小游戏，逻辑不复杂，于是想实现下自动复原。网上有挺多关于拼图游戏自动复原的文章，被称为 8数码 难题。
路径规划
假设我们有一个二维平面，一只蚂蚁处于位置 2 ，想要吃到位置 8 的食物。用我们的肉眼很容易规划出路径 2-5-8。但是想要代码去寻找路径，不使用算法的情况下，只能使用暴力枚举，从起点开始按照上左下右的顺序探查每一条可以走通的路径，因此可能会找出这样的路径 2-3-6-9-8。
// x0 x1 x2
// y0 [1, 2, 3],
// y1 [4, 5, 6],
// y2 [7, 8, 9],
代码设计的再聪明点，我们可以计算每走一步，是否离终点更近，并以此作为评分，使用评分最好的一步。比如由 2 开始，依据上左下右的遍历方向，往右走的话，3 的坐标为 y0, x2，8 的坐标为 y2, x1，纵向需要走 Math.abs(0 - 2) 步，横向为 Math.abs(2 - 1) 步，共走 3 步。而往下 ，计算 Math.abs(1 - 2) + Math.abs(1 - 1)，只走 1 步，步数越小越靠近终点，往下走最优。
这和拼图有什么关系？
一个乱序的拼图是这样的
// x0 x1 x2
// y0 [3, 5, 1],
// y1 [2, 4, 6],
// y2 [8, 7, 9],
除了 9 和 6 以外，其他的数字都不在原位，而且只能移动 9 去交换位置，直到把所有的数字都复原成下面这个视图。
// x0 x1 x2
// y0 [1, 2, 3],
// y1 [4, 5, 6],
// y2 [7, 8, 9],
数字 9 可以去往上下左右任何一个可移动的方向，移动后的视图越来越贴近复原后的视图就证明这个移动方向越对，依此逻辑我们可以先写一个评分机制。
// arr 是一个 [ [ 3, 5, 1 ], [ 2, 4, 6 ], [ 8, 7, 9 ] ] 的二维数组
function computedCurrentViewScore(arr) {
const score = arr.reduce((score, line, y) => {
return line.reduce((score, num, x) => {
const [realY, realX] = getNumPosition(num)
// 当前数字所处的位置距离正确的位置有多远，越小距离越近
return score + Math.abs(y - realY) + Math.abs(x - realX)
}, score)
}, 0)
return score
}
// 得到数字正确的位置，比如，传入 1 返回 [0,0],传入2返回 [0,1]
function getNumPosition(num) {
return [Math.floor(!(num % 3) ? num / 3 - 1 : num / 3), (num - 1) % 3]
}
用距离做评分，评分越小越优质。
比如上面的乱序视图，将和 8 置换及和 6 置换后的视图计算评分，存入到 views 数组，按照分数由大到小排序，选取评分最好的视图当做下一步，不断找到正确的视图。
同时我们也需要一个黑名单数组 blackList 来存储已经出现的视图。如果遇到重复的视图，移动轨迹和评分都是一样的，再走一遍没有意义，所以需要把出现过的视图存入黑名单，如果这个视图已经在黑名单中，就不加到 views 数组里。
把视图存储为一个对象，在对象里记录我们需要的信息。
// 初始视图
const initView = {
data: JSON.parse(JSON.stringify(arr)), // 视图的二维数组
parent: null, // 初始视图没有父视图
id: arr.flat().join(""), // 拍平二维的字符串，如 "123456789"
score: 0, // 分数，初始视图分数最低
step: 1, // 步数
emptyPos: [2, 2], // 9 当前所在的位置
}
按照上面的逻辑我们开始写代码
function recoveryPuzzle(arr) {
const initView = {
data: JSON.parse(JSON.stringify(arr)), // 视图的二维数组
parent: null, // 初始视图没有父视图
id: arr.flat().join(""), // 拍平二维的字符串，如 "123456789"
score: 0, // 分数，初始视图分数最低
step: 1, // 步数
emptyPos: [2, 2], // 9 当前所在的位置
}
const views = [initView]
const blackList = new Set()
// 找到的正确视图
let endView = null
while (endView === null && views.length) {
// 最末尾即评分最好的视图
const bestView = views.pop()
blackList.add(bestView.id)
// 9要置换的位置 置换后的视图二维数组
const [nextEmptyPositions, nextViewDatas] = getNextViewData(
bestView.data,
bestView.emptyPos
)
// 遍历置换后的视图，计算评分
while (nextViewDatas.length) {
const data = nextViewDatas.pop()
const nextEmptyPos = nextEmptyPositions.pop()
const id = data.flat().join("")
// blackList 里面包含此视图就跳过
if (blackList.has(id)) {
continue
}
const score = computedCurrentViewScore(data)
const step = bestView.step + 1
const nextView = {
data,
parent: bestView, // 用来逐级往上寻找步骤
id,
score: score * 2 + step, // 评分 + 步骤，步骤越少也代表着越好，但是增加评分的权重
step,
emptyPos: nextEmptyPos,
}
if (id === "123456789") {
// 找到正确的视图了，结束
endView = nextView
break
} else {
// 加到 views 里排序
views.push(nextView)
}
}
// 拿到视图后由大到小排序，最末尾的是最好的
views.sort((a, b) => b.score - a.score)
}
return endView
}
// 获取下一个视图的二维数组，以及空格即 9 的位置
function getNextViewData(arr, [originEmptyY, originEmptyX]) {
const emptyPositions = [
[originEmptyY + 1, originEmptyX],
[originEmptyY - 1, originEmptyX],
[originEmptyY, originEmptyX + 1],
[originEmptyY, originEmptyX - 1],
].filter((item) => typeof arr[item[0]]?.[item[1]] === "number")
return [
emptyPositions,
emptyPositions.map(([y, x]) => {
const copy = JSON.parse(JSON.stringify(arr))
const newItem = copy[y][x]
copy[y][x] = 9
copy[originEmptyY][originEmptyX] = newItem
return copy
}),
]
}
// 获取数字正确的位置
function getNumPosition(num) {
return [Math.floor(!(num % 3) ? num / 3 - 1 : num / 3), (num - 1) % 3]
}
// 计算评分
function computedCurrentViewScore(arr) {
const score = arr.reduce((score, line, y) => {
return line.reduce((score, num, x) => {
const [realY, realX] = getNumPosition(num)
return score + Math.abs(y - realY) + Math.abs(x - realX)
}, score)
}, 0)
return score
}
// 判断这个拼图能不能复原
function solvability(arr) {
if (!arr || arr.join("") === "12345678") return true
let a = 0
arr.forEach((item, index) => {
for (var i = index + 1, len = arr.length; i < len; i++) {
if (item > arr[i]) {
a++
}
}
})
return a % 2 !== 0
}
// 创建一个拼图二维数组
function genNewJigsaw() {
let arr = null
while (solvability(arr)) {
arr = "12345678"
.split("")
.sort(() => Math.random() - 0.5)
.map(Number)
}
arr.push(9)
return [arr.slice(0, 3), arr.slice(3, 6), arr.slice(6, 9)]
}
let arr = genNewJigsaw()
console.log("乱序视图", arr)
const endView = recoveryPuzzle(arr)
console.log(endView)
按照上面的代码就可以将一个乱序的拼图完美复原，并且可以用尽可能少的循环找到正确视图，其实这个很依赖评分机制，在上面使用了 score * 2 + step 的机制，这个机制并不是完美的，可以随意的增加 score 或 step 的权重。
A* 算法
拼图问题的解决其实也源于 A\* 算法 ，是一个很经典路径规划算法，有兴趣可以了解一下。