前言

很早之前写过一个拼图的小游戏，逻辑不复杂，于是想实现下自动复原。网上有挺多关于拼图游戏自动复原的文章，被称为 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\* 算法 ，是一个很经典路径规划算法，有兴趣可以了解一下。

在线体验

Game Github