[Community Puzzle] 11-puzzle

Puzzles
#1

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.

#2

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 !!!

#4

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

#5

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
#6

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

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.

1 Like
#8

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
#9

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

#10

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
#11

[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 :slight_smile: Thanks !

#12

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

#13

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 :slight_smile:

#14

That’s what I used in my solution :slight_smile:

#15

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

#16

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

1 Like
#17

Well… Thank you it worked :slight_smile:
But to be honest, it worked when submitted but still didn’t with the 35 and 38 tests :smiley:
Well, it’s done, that’s the most important

1 Like