Eight tiles, one gap
The 8-puzzle is a 3×3 frame with eight numbered tiles and one gap: slide tiles into the gap until they read 1–8 in order. It's small enough to solve exactly and big enough to be interesting — 181,440 reachable arrangements — so it has been AI's favourite test of search and heuristics since the 1960s.
Today you'll solve it with the A* search you wrote: generate the moves, design an admissible heuristic, detect the half of all boards that can never be solved, and return the shortest solution — up to 31 moves, the hardest any 8-puzzle needs.
8 6 7 1 2 3 2 5 4 → 4 5 6 3 _ 1 7 8 _
Boards as strings
Store a board as a 9-character string read row by row, with 0 for the gap. Strings compare and hash easily, so A*'s best-cost Map works out of the box. To find the moves, locate the gap at index z — its row is Math.floor(z / 3), its column z % 3 — and swap it with each neighbour that stays inside the grid. A corner gap has 2 moves, an edge 3, the centre 4.
const z = board.indexOf("0");
const r = Math.floor(z / 3), c = z % 3;
for (const [dr, dc] of [[-1, 0], [1, 0], [0, -1], [0, 1]]) {
const nr = r + dr, nc = c + dc;
if (nr < 0 || nr > 2 || nc < 0 || nc > 2) continue;
// swap positions z and nr * 3 + nc
}