[Community Puzzle] 11-puzzle

https://www.codingame.com/training/hard/11-puzzle

Send your feedback or ask for help here!

Created by @_CG_Maxime,validated by @amurushkin,@Bibou and @helgui.
If you have any issues, feel free to ping them.

The final result showed me 33% while my own test shows me 66%, I can always solve 25 in less than 1s and 20 in less than 100ms, so I think it’s a bit confusing !!!

I’m not spoiling anything saying one of the tags of this puzzle is A*. You can also check out the following puzzle:

In 1 word “Lovely”. Would have given it 6 * if I could. My solution in C# takes upto 320 ms for the last 2 test cases to get it done in the “35” and “38” moves. I tried with a smaller search space and did get a solution for the last 2 in test cases under 100ms but it takes 40 and 39 moves to win.

1 Like

I know the puzzles ranking can be tricky, but it still surprises me sometimes.
Here for example, 11-PUZZLE is in the hard section. 516 have started, 72 have finished, community success rate: 14%
Now there is another puzzle, SLIDING PUZZLE, which is in the very hard section. 481 have started, 181 have finished, community success rate: 38%
As the theme looks pretty similar, I copied my 11-PUZZLE’s code, made very light adjustments… and it works.
I would say one of the two is not in the right category, isn’t it?

Agree. The reason for the higher success rate in the “very hard” problem may be because it does not require A*. Regular pathfinding works fine there.

There is an excellent free Algorithm course by Princeton University on Coursera. (https://www.coursera.org/learn/algorithms-part1).
The coding assignment for Part 1 Week 4 is almost the same as this 11-puzzle and the Sliding Puzzle on CG, with an additional twist of having to detect also the unsolvable puzzle inputs. The assignment spec and faq pages provide several useful implementation and speed-improving tips.

1 Like

My generic solution (working for any board size, just as in the Sliding Puzzle) was too slow for 11-puzzle ide test cases “35” & “38”, although passed the validators 100%.

I rewrote it using a more compact board representation of a single 64-bit integer (loosing some genericity, yet fine for 4*3 boards), leaving the A-star still to use objects created on the fly. Result: test “35” pass, test “38” still failing…

Then I turned off PHP’s garbage collection, and now test “38” is solved in 0.96sec (Phew…)
It turned out, that at test “35” (having 78196 iterations in A* for me) the system is spending 20% of its total processing time collecting garbage…

EDIT: checking with an additional HashMap if a board was already visited saved ~45% on iterations and 25% on total time for test “38”. (originally I checked only the immediate previous board).