# Harmonic Analysis and Resynthesis of Sliding-Tile Puzzle Heuristics

### Harmonic Analysis and Resynthesis of Sliding-Tile Puzzle Heuristics

#### University of York (United Kingdom)

##### University of York (United Kingdom)

Combinatorial optimization problems such as the Travelling Salesman Problem,
Quadratic Assignment Problem and Sliding-Tile Puzzle have structure that can
be described algebraically and exploited to improve search quality. In
particular, heuristic functions for these problems can be described in terms
of symmetric groups. By employing techniques from the emerging field of
algebraic machine learning, we investigate the harmonic decomposition of
popular sliding-tile puzzle heuristics via the extension of the Fourier
Transform to noncommutative groups. The Fourier-space representation for
these heuristics can then be manipulated by multiplication with a real-
valued weight vector. By performing such a reweighting and then taking the
inverse transform, we obtain a `filtered' version of the original heuristic.
Taking the 8-puzzle as a case study, we demonstrate that heuristic accuracy
is related to harmonic spectral density and further that the heuristic
functions given by the Hamming and Manhattan distance metrics on puzzle
state can be transformed into significantly better heuristics by performing
a search in the weight space.