Resolving a puzzle (optimal solution)

I have a puzzle 3x3 of numbers as follow:

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

Being the solution:

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

The rule is that I can only move nearby "pieces" until I get the solution.

My take on this was to calculate the offset and then run it into a "fancy" algorithm for an efficient solution. However, I can only think of using bruteforce and checking the amount of steps the program did to find the most efficient one.

In offset I mean:

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

Which are the offsets of x and y in a cartesian plan. I got the following which does calculate the offset, but no thoughts on the "fancy algorithm".

https://ideone.com/0RP83x

Is there a efficient way to get the least movements for the solution without using bruteforce ?

Solution

It is possible to consider the grid as a node (part of a graph).

Let's write the grid

abc
def
ghi

as a single line abcdefghi.

You start with node 352789164 and you want to reach node 123456789.

The neighbours of a node are all the nodes you can reach by applying swaps. e.g 123456789 has for neighbours

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

Then you can apply A*, by supplying:

d(nodeA, nodeB) = weight(nodeA, nodeB) = 1 (all swaps cost 1)
h(node) = minimal number of swaps needed to get to solution.

To have the minimal h, consider counting the misplaced digits.

If you have an even number of misplaced digits, you need at minimum "half of it" swaps
If you have an odd number of misplaced digits, then half + 1 (e.g 312 for goal 123 needs 2 swaps)

Below example in js where I copy pasted code from wiki

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))