Great puzzle!

tails · Post by **tails** » Mon Aug 31, 2009 2:08 am

Not only because the hex board looks beautiful :-)

At first glance, this puzzle looks easy, and it is acturally easy under level 100 or so. But it's getting harder around level 140. I thought it would be hard if the board got very large, but suprisingly it's getting hard while it keeps smaller than the size of level 0 :-)

Furthermore, it's a great aspect of this puzzle that we can't simply apply well-known algorithms when we make solvers. It would take forever with DFS even to solve low levels. My simple solver took less than 1 second for each of low levels, but it got almost useless above level 100. It seems that the key is how to implement human intuition.

I never imagined the hex board had such possibilities. It' really fresh! And I never imagined JavaScript had such capabilities :-)

Post by **adum** » Mon Aug 31, 2009 5:22 pm

glad you like it! =)

it's been a long time since i put up a new puzzle, so i thought i'd release one and try something a little fresh at the same time. a hex board is a little different, but the nature of the puzzle is really a new beast. as you say, classical brute force algorithms aren't going to get very far!

i honestly have no idea myself on how to tackle this one, so it will be very interesting to see where people go with it...

therethinker · Post by **therethinker** » Mon Sep 07, 2009 9:05 pm

Very awesome puzzle.

Hex board is fun, yet a PITA to work with (in a good way

) As tails said, its amazing how well this puzzle scales.

How are you generating the puzzles? I was doing some by hand and noticed a few (around level 30, when they were harder) that consisted of only 1 snake and took 2 moves to solve. I guess it averages out, though.

Props to the first person that uses Javascript to solve it

Post by **adum** » Wed Sep 09, 2009 5:21 pm

for generating the puzzles, there are a bunch of factors to play with, such as board size, number of worms, num colors, worm length, spaces left over, spaces blocked, etc. i don't know which will turn out to be hardest, so i try a lot of variations of all these factors at each board size. some will be harder than others...

good luck with your solver! =)

therethinker · Post by **therethinker** » Thu Sep 10, 2009 1:45 am

Also, does everyone have the same problems?
There really shouldn't be an issue of sharing answers since solvers/code could be shared too...

Post by **adum** » Fri Sep 11, 2009 12:01 am

yes, everyone sees the same problems for this puzzle.

prop · Post by **prop** » Thu Oct 29, 2009 6:30 am

Wow it's very intriguing puzzle!

level 60-65 were the best I think(Now I'm solving lv.74, so I know just a little of them).

Anyway I like to solving it w/o brain though

plus lv 73 was not THAT horrible. i think lv 7 was the most horrible

dangermouse · Post by **dangermouse** » Wed Aug 29, 2012 1:58 pm

lvl 73 is horrible! i had a bad start with this puzzle, i tried to implement it as a iterative DFS but had some bug in the implementation and had to give up. I tried to do it iterative knowing that the recursion depth of this thing is awesome. I then implemented it as recursive DFS with weighted moves on shortest paths and still can't solve level 73...

one good thing i am using is: to debug the code i inject into a html level template my current board as javascript variable, and then look at the result in a browser as it would be a level on hacker.org. This probably works with other puzzles as well, but i never tried it before.

and still i have some ideas, but its' really an awesome puzzle

Hippo · Post by **Hippo** » Mon Oct 27, 2014 10:19 am

I used to play easy levels by hand till I got to level where it become hard.
This gives me feeling of the game ... I am now above 100 and still not having troubles to solve it manually ... According to what was said, I have to do next about 60 levels?

In any case, it's fun to pull them so

.

BTW: The comp is ususally solving other puzzles meanwhile ...

Seems 165 is good enough to start codding ...

... hmmm still not, ... solved, but so far no code.
I expect (at least for start) I would implement iterative deepening with only one puzzle dependent trick ... I would code cyclic worm as one state regarding the search (may be with simple heuristic guess of required steps to finish).

Hippo · Post by **Hippo** » Fri Jun 05, 2015 2:23 pm

Hmm, my code is running now, but seems IDA* needs better heuristics than I have.
It went rather smoothly (often under 1s, once above 1minute) to level 73, when it stands for several minutes ... either I have in code more bugs than I have expected or the method does not work that great.

level 79 was not solved overnight, seems solving (one of several) puzzles with more different colors than the original one could improve heuristcs lower bounds navigation a lot ... I should concentrate on this.

Hippo · Post by **Hippo** » Fri Jun 12, 2015 6:05 am

So artifical coloring color components helped with level 79, but level 81 looks hard for IDA*
(I already use statistics of ida subgraph sizes to have better controll on deepening).

I am starting to think about checkpoints adaptation of IDA* (I have never heard about such algorithm).

The situation when I solve level faster manually than IDA* is motivating.

Artifical colors and checkpoints are helpfull, but even with them I have not solved several levels with it.
For some levels splitting components could be helpfull, but I don't know how to speed it at all.

Let us see how far it will go ...
wow! level 201 ... my heuristics navigation said ... one step missing immediately, but the step was not found overnight. Seems I should concentrate on better heuristics navigation.

OK, better heuristics helped with 201, but levels 161, 165, 173, 175, 178, 181, 192, and 196 were not solved quickly enough with it so seems I should work on it more.

Levels 161,165 solved with use of single worm exact solution heuristics as lower bounds (but some debugging is needed). OK after debugging all these levels solved.

Level 103 would need color exact solution heuristics lower bounds (it will be implemented in near future).

Grrr, I have solved 211 faster by hand again

, and 222, 225, 228, 236 as well.

Finally I have implemented heuristics switching by time allocation.
Current version solved 211 ans 222 in reasonable time, so I hope I will go further soon.

... and level 298, 326 were again easy for brain and much time consuming for my code

.
Oops ... back to debugging with color heuristics...

Ohh, my solver fails on 298 even when I remove all worms except team 2. When I recolor worm of length 6 (and 6 squares), it finds solution quickly. Seems sometimes splitting of color components will be must.

Hmm, I have not coded color components splitting, but I have helped my solver in some levels by adding additional colors to the task. ... approaching level 400.

OK, it's definitely must to implement color component splitting ... for levels above 450. There is probbaly no need to find all solutions. In most cases any solution would work.

Hippo · Post by **Hippo** » Tue Jul 21, 2015 12:57 pm

I have added color complement splitting and it didnot help much.

Free space economy ... When one have local solution blocking free space on the edge...making se real steps to move free space to the middle what could be undone easily. But

... no free space economy yet, I had to change the time management strategy for the checkpoints to search ... original strategy to search each to the same depth failed, so if the search exceeds some time T I go for another checkpoint ... of course T must me slowly increased (until a new checkpoint is found).

Roughly ... I use for each sum of worm loop lengths ... the heuristically nearest position as checkpoint.

I still use 3 different heuristics and either component splitting (randomized) or not (5 algorithms randomly chosen). Each try runs for given time (starting at 90seconds) and time for tries is slowly increased.

... combinatorial complexity of levels as 587 of too many worms of same length ... kills all these startegies ... as I start for each of variations how to distribute worms ... I should switch to chosing only much limited amount of them (probably selecting by the heuristics function).

So I had to limit the starting positions by sampling...

I often "cheat" by solving level by hand as it is clearly simple ...

Hippo · Post by **Hippo** » Sat Aug 08, 2015 7:20 am

Really bad performance of the algorithm on trivial level 607 (i hope) persuided me to extend set of 'basic/macro´ moves to allow removing small subworm and adding subworm of same length what is applicable on looped worms. I will start on length 1 extension. I hope it would be suffitient.

My solver is still extremely slow on several levels ... still on levels about 660 I am often much faster when I solve the puzzle manualy ... dividing the solution to unblocking phase, moving near the target phase and final arranging would be helpful in several levels (sometimes direct arranging without unblocking is must).
The "free space economy" was not still codded ... may be this is still the bottleneck.

Level 698 is a nice joke.

Hippo · Post by **Hippo** » Sun Aug 30, 2015 10:04 pm

Big performance improvement was achieved by remembering position with longest total loop length as starting position for algorithm restart. So a later search is invoked from positions with worms more untangled.

This much more corresponds to human solution with entangling worms first than trying to put worms to places.

Hippo · Post by **Hippo** » Mon Sep 07, 2015 6:01 pm

Oh on level 847 I have noticed the task is not constant ... the same appeared probably earlier ... and I was surprised why my solver was moving worms from nonexisting positions ... to let the comp solve the puzzle and to look at it occassionally could be bad decisiton.