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.
