# [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?

1 Like

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).

Same experience here, my algorithm was barely enough to solve 35 in time, and failed 38. But when I submitted to save my progress, all validators passed 100%.

Edit : finally passed all tests properly. I based my algorithm on a version of Iterative deepening A* :

1 Like

[Python] Hi, Iâ€™m working on this one atm, and Iâ€™m kinda stuckâ€¦
Iâ€™m using an IDA*, which has greatly improved my first A* tries, but I still canâ€™t manage to pass the 35 and 38 tests.
On my computer, it takes an average of
5 â†’ 74 us
10 â†’ 173 us
15 â†’ 2.4 ms
20 â†’ 10.7 ms
25 â†’ 47.8 ms
30 â†’ 221 ms
35 â†’ 20 s !!
38 â†’ 34 s

I canâ€™t get why such a big increase between 30 and 35â€¦ The code not being too complicated, I feel like the bottleneck could be the point before trying a new grid you check if itâ€™s already in the path stack. But I donâ€™t know exactly how to verify this assumption. My grids are coded as a simple list, and copies done with g[:].

Any advice or insight would be great Thanks !

You can try using PriorityQueue from queue library to see if it helps.

Thank you for your answer.
However, I read the spec and canâ€™t really see how it could help here. In IDA*, the stack is the path, and I need to keep this order. Perhaps I didnâ€™t see sth

Thatâ€™s what I used in my solution

And didnâ€™t you do sth like a RBFS ? Thatâ€™s what Iâ€™m working on, and here I think I see how to use it

See if this helps: http://csc.columbusstate.edu/woolbright/c1302as5.htm

1 Like

Wellâ€¦ Thank you it worked
But to be honest, it worked when submitted but still didnâ€™t with the 35 and 38 tests
Well, itâ€™s done, thatâ€™s the most important

1 Like