The X-Y heuristic decompose the problem into two one-dimensional problems where the "space" can swap with any tile in an adjacent row/column. The heuristic function adds the number of steps from the two sub-problems.

The heuristic function: computes the minimum number of column-adjacent blank swaps to get all tiles in their destination column + the minimum number of row adjacent blank swaps to get all tiles in their destination row.

This heuristic is admissible. This is a more accurate version of the Manhattan Distance heuristic, and is better than the Linear Conflict heuristic for the 8-Puzzle with IDA* when pre-computing. Without pre-computing, the heuristic is less effective than the Linear Conflict heuristic, but better than N-Maxswap heuristic and better than no heuristic at all (breadth-first search).

Related Problems:N-PuzzleType:heuristic functionThe X-Y heuristic decompose the problem into two one-dimensional problems where the "space" can swap with any tile in an adjacent row/column. The heuristic function adds the number of steps from the two sub-problems.

The heuristic function:computes the minimum number of column-adjacent blank swaps to get all tiles in their destination column + the minimum number of row adjacent blank swaps to get all tiles in their destination row.This heuristic is admissible. This is a more accurate version of the Manhattan Distance heuristic, and is better than the Linear Conflict heuristic for the 8-Puzzle with IDA* when pre-computing. Without pre-computing, the heuristic is less effective than the Linear Conflict heuristic, but better than N-Maxswap heuristic and better than no heuristic at all (breadth-first search).