Add support to solve 15-puzzle

[zy31415]

• Memory
  In order to solve any 15-puzzle, we need to solve the memory issue first. The total number of different configurations of 15-puzzles is 16! ~= 10^13. There is no way to store all of them in memory.
  A tool we can use in Java is mapDB, which provide file-based dictionary to store all possible states.
  https://github.com/jankotek/mapdb/

• Test and prototyping
  But before you using mapdb, make sure that you understand the problem. Test how dictionary uses memory in Java. Test how mapdb can help to solve this issue. Test that you current program indeed has the memory issue. Profile the memory growth of your current solve on 15-puzzle.

[zy31415]

I tested 15-puzzle using VisualVM.

After running the A* 15-puzzle solver for 1 hrs 20 min, I still haven't found the solution.

According to VisualVM profiler, the max heap size (4GB) has been reached. The used heap is lingering around 3.5 GB and slowly growing up. At this point, the program is running slowly, because (i guess )heap is running out of space and GC is not working probably (I don't know how to profile GC yet).

I need to learn more about profiling and the how GC works.

Of course, using filed based cache such as mapDB, perhaps will improve GC performance, but it will also introduce disk reading delay. The end result is hard to tell.

Based on this observation, I proposed that the main issue is perhaps not memory but the algorithm itself. The reason is that even if you have more heap size, you still need very long time to solve 15-puzzle if you don't change your algorithm. In other words, the simple Manhattan heuristic will fail 15-puzzle because it's not efficient enough.

[zy31415]

I can actually test program performance by explicit setting the max heap size in Intellij in the Run => Configuration dialog. For example, I can set:

-Xms100m -Xmx200m

And it takes the program 4 min 25 sec to fail on the error:

java.lang.OutOfMemoryError: GC overhead limit exceeded

After the used the used heap size reached 77% of the max heap size, the JVM started to spend ~12% of its CPU time on garbage collecting, which is a significant drag on the JVM performance.

Lesson learned from the experiment:

1. Leave enough heap space for your program. Otherwise, GC will ruin the performance.
2. Be especially cautious if your heap size will continuously grow when your program is running. Make sure that your program will end well before your heap size is used up. Otherwise, you need to figure a way to curtail your memory use (e.g. use disk space to replace memory).