title: 5x5 Sliding Puzzle Fast & Low-Move Solution
body: <p>I am trying to find a way to programmatically solve a 24-piece sliding puzzle in a reasonable amount of time and moves. Here is an example of the solved state in the puzzle I am describing: </p>
  
  <p><img src="https://vignette.wikia.nocookie.net/runescape2/images/0/06/Solved.png/revision/latest?cb=20111128220731" alt="5x5 Solved Sliding Puzzle"></p>
  
  <p>I have already found that the IDA* algorithm works fairly well to accomplish this for a 15-puzzle (4x4 grid). The IDA* algorithm is able to find the lowest number of moves for any 4x4 sliding puzzle in a very reasonable amount of time. I ran an adaptation of <a href="https://rosettacode.org/wiki/15_puzzle_solver#Iterative_Depth_A.2A" rel="nofollow noreferrer">this</a> code to test 4x4 sliding puzzles and was able to significantly reduce runtime further by using PyPy. Unfortunately, when this code is adapted for 5x5 sliding puzzles it runs horribly slow. I ran it for over an hour and eventually just gave up on seeing it finish, whereas it ran for only a few seconds on 4x4 grids. I understand this is because the number of nodes that need to searched goes up exponentially as the grid increases. However, I am not looking to find the optimal solution to a 5x5 sliding puzzle, only a solution that is close to optimal. For example, if the optimal solution for a given puzzle was 120 moves, then I would be satisfied with any solution that is under 150 moves and can be found in a few minutes.</p>
  
  <p>Are there any specific algorithms that might accomplish this?</p>