A* Search does not finish [8 Puzzle Solver]

Question

I am creating an A* search method for my programming task. My issue is that an A* search method is supposed to find the lowest cost path and always find the goal state. However, my code does not solve the problem for certain puzzles. For example, for the puzzle:

  *=====*
  ||103||
  ||426||
  ||758||
  *=====*

The required goal state is reached, however for a puzzle with more tiles out of place. For example for the puzzle:

  *=====*
  ||104||
  ||326||
  ||758||
  *=====*

The following error is produced:

    Step: 3073
    *=====*
    ||016||
    ||342||
    ||758||
    *=====*
Exception in thread "main" java.lang.StackOverflowError
at sun.nio.cs.UTF_8$Encoder.encodeLoop(UTF_8.java:680)
at java.nio.charset.CharsetEncoder.encode(CharsetEncoder.java:579)
at sun.nio.cs.StreamEncoder.implWrite(StreamEncoder.java:271)
at sun.nio.cs.StreamEncoder.write(StreamEncoder.java:125)
at java.io.OutputStreamWriter.write(OutputStreamWriter.java:207)
at java.io.BufferedWriter.flushBuffer(BufferedWriter.java:129)
at java.io.PrintStream.write(PrintStream.java:526)
at java.io.PrintStream.print(PrintStream.java:669)
at java.io.PrintStream.println(PrintStream.java:806)

My code can be found here: http://pastebin.com/rwq3cTAq

See http://stackoverflow.com/questions/4734108/what-is-the-maximum-depth-of-the-java-call-stack — irrelephant, Dec 02 '14 at 21:02
Please do not link to external resources, the code relevant to this problem specifically should be posted directly here. — tnw, Dec 02 '14 at 21:16
@EyalSchneider I have updated this post with the rest of my files, I think there might be something wrong with my formula - http://pastebin.com/rwq3cTAq — user3624883, Dec 03 '14 at 17:39
1. The code is *still* at an external site. 2. You haven't included the complete stack trace - what is shown does not tell at which part of *your* code the execution was when the exception was thrown. — kiheru, Dec 03 '14 at 17:49

score 0 · Answer 1 · answered Dec 03 '14 at 22:18

You are ignoring solvability issues in your solution. The second configuration in your post is not solvable, and your A* algorithm enters an infinite recursion, resulting in a StackOverflowError.

Solvability of this puzzle can be easily determined by examining the permutation parity and the distance of the 0 tile from its target position. See this link for details.

A* Search does not finish [8 Puzzle Solver]

1 Answers1