解决难题（最佳解决方案）

Question

我有一个 3x3 的数字拼图如下：

3 | 5 | 2
7 | 8 | 9
1 | 6 | 4

作为解决方案：

1 | 2 | 3
4 | 5 | 6
7 | 8 | 9

规则是我只能在"pieces"附近移动，直到我得到解决方案。

我对此的看法是计算偏移量，然后运行将其转化为 "fancy" 算法以获得有效的解决方案。但是，我只能想到使用暴力破解并检查程序执行的步骤数量以找到最有效的步骤。

偏移我的意思是：

(2,  0) | (0,  1) | (-1,  0)
(0,  1) | (0,  1) | ( 0,  1)
(0, -2) | (1, -1) | (-2, -1)

笛卡尔坐标系中 x 和 y 的偏移量。我得到了以下计算偏移量的信息，但没有想到 "fancy algorithm".

https://ideone.com/0RP83x

是否有一种有效的方法可以在不使用暴力的情况下获得最少移动的解决方案？

Answer 1

可以将网格视为节点（图形的一部分）。

让我们写网格

abc
def
ghi

单行abcdefghi.

您从节点 352789164 开始，您想要到达节点 123456789。

节点的邻居是您可以通过应用交换到达的所有节点。例如 123456789 有邻居

[
  213456789, 132456789,
  123546789, 123465789,
  123456879, 123456798,
  423156789, 153426789,
  126453789, 123756489,
  123486759, 123459786
]

然后您可以申请 A*，方法是提供：

d(nodeA, nodeB) = weight(nodeA, nodeB) = 1（所有交换费用为 1）
h(node) = 获得解决方案所需的最少交换次数。

要获得最小值 h，请考虑计算错位的数字。

如果您有偶数个错位的数字，您至少需要 "half of it" 次交换
如果您错位的数字为奇数，则为 half + 1（例如，目标 123 的 312 需要 2 次交换）

下面是我从

复制粘贴代码的 js 示例

function h (node) {
  const s = ''+node
  let misplaced = 0
  for(let i = 0; i < s.length; ++i) {
    if (parseInt(s[i]) != i+1) {
      misplaced++
    }
  }
  if (misplaced % 2 === 0) {
    return misplaced / 2
  }
  return Math.ceil(misplaced / 2)
}

function d (a, b) {
  return 1
}

const swaps = (_ => {
  const arr = [[1,2],[2,3],[4,5],[5,6],[7,8],[8,9],[1,4],[2,5],[3,6],[4,7],[5,8],[6,9]]
  function makePermFunc([a,b]) {
    a--
    b--
    return function (node) {
      const s = (''+node)
      const da = parseInt(s[a])
      const db = parseInt(s[b])
      const powa = 9 - a - 1
      const powb = 9 - b - 1
      node -= da * 10**powa
      node -= db * 10**powb
      node += da * 10**powb
      node += db * 10**powa
      return node
    }
  }
  const funcs = arr.map(makePermFunc)

  return node => funcs.map(f => f(node))
})();

//https://en.wikipedia.org/wiki/A*_search_algorithm
function reconstruct_path (cameFrom, current) {
  const total_path = [current]
  while(cameFrom.has(current)) {
    current = cameFrom.get(current)
    total_path.unshift(current)
  }
  return total_path
}


// A* finds a path from start to goal.
// h is the heuristic function. h(n) estimates the cost to reach goal from node n.
function A_Star(start, goal, h) {
  // The set of discovered nodes that may need to be (re-)expanded.
  // Initially, only the start node is known.
  const openSet = new Set([start])

  // For node n, cameFrom[n] is the node immediately preceding it on the cheapest path from start to n currently known.
  const cameFrom = new Map()

  // For node n, gScore[n] is the cost of the cheapest path from start to n currently known.
  const gScore = new Map()
  gScore.set(start, 0)

  // For node n, fScore[n] := gScore[n] + h(n).
  const fScore = new Map()
  fScore.set(start, h(start))

  while (openSet.size) {
    //current := the node in openSet having the lowest fScore[] value
    let current
    let bestScore = Number.MAX_SAFE_INTEGER
    for (let node of openSet) {
      const score = fScore.get(node)
      if (score < bestScore) {
        bestScore = score
        current = node
      }
    }
    
    if (current == goal) {
      return reconstruct_path(cameFrom, current)
    }
    openSet.delete(current)
    swaps(current).forEach(neighbor => {
      // d(current,neighbor) is the weight of the edge from current to neighbor
      // tentative_gScore is the distance from start to the neighbor through current
      const tentative_gScore = gScore.get(current) + d(current, neighbor)
      if (!gScore.has(neighbor) || tentative_gScore < gScore.get(neighbor)) {
        // This path to neighbor is better than any previous one. Record it!
        cameFrom.set(neighbor, current)
        gScore.set(neighbor, tentative_gScore)
        fScore.set(neighbor, gScore.get(neighbor) + h(neighbor))
        if (!openSet.has(neighbor)){
          openSet.add(neighbor)
        }
      }
    })
  }
  // Open set is empty but goal was never reached
  return false
}

console.log(A_Star(352789164, 123456789, h).map(x=>(''+x).split(/(...)/).filter(x=>x).join('\n')).join('\n----\n'))
console.log('a more basic one: ', A_Star(123654987, 123456789, h))

解决难题（最佳解决方案）

Resolving a puzzle (optimal solution)

c++

algorithm

a-star

heuristics