Any hints?

[camel]

Porting my "early out heuristic" solver to c++ allowed me to do lvl 32 to 36 ... but now the search space is exploding. Even with said heuristics I can't possibly solve the level ...

Any hints on how to approach this puzzle? I have been working on this for a few days every year and I feel that I am missing something fundamental?

Basically I am using a recursive approach. I sort the pieces by the number of fields they can toggle (or "inc" as in increase by 1/++) and ignore branches of combination of tiles which lead to a board which can't possibly be toggled to all-zero by the remaining tiles.

I have been thinking about representing the entire puzzle as a mathematical problem but ultimately failed.

Code: Select all

Board Size: 56 Depth: 2 Number of Pieces: 16 Number of total combinations: 8.45731e+020

[camel]

Got to level 40 using my solver. I just found out about another approach on a different forum but it looks very similar to mine ... it just seems to represent the board and pieces smarter than having zero filled vectors like I do currently ... investigating ...

I just tested my solver with level 97 from http://www.neopets.com/medieval/shapeshifter.phtml ... and those levels are a joke. The inc power of all pieces combined is often only 4-5 off the solution. I can solve that level in 3 seconds ... so apparently their solvers are as good as mine. Bugger.

I converted a level 97 into the hacker.org format ... just so you can test your solver. Huge board, many tiles ... but only takes like 3 seconds to solve using the early out strategy based on the inc (as in ++) power of the tiles.

Code: Select all

my $doc='<param name="board" value="0040040400000,4434244404040,4433242322330,0040443314340,0000004010244,0004043442044,0003434302334,0444334004030,4403334004444,0333400404334,0040044440404,0040004444000,0434000403440,0404000444000"><param name="depth" value="5"><param name="pieces" value=".X.X,XX.X,.XXX,XX.. XXX ..X,XXX,X.. XXX,X..,X.. X,X,X X.X,XXX X..,XX.,.XX XX,XX XX X.X,XXX,X.X .XXX,..X.,XXX. X.X,XXX X..,XXX,..X X XX.X,X..X,XXXX,..X. XX.,.XX X.X,XXX,X.X XX.,.XX X.X,X.X,XXX XXX,X.X,XXX .X..,XX.X,.XXX ...X,X.XX,X.X.,XXX.,X.X. XXX,X.X X.X,XXX XXXX,X...,X... X..,XX.,.XX .XX.,XX..,.XXX XXX.,..XX,XXX.,.X.."><input type="text" name="gotolevel" size="3" value="9999" />';

Solved in 3 seconds ...

Code: Select all

k: 2 Stack: 43 18 48 - - - - - - - - - - - - - - - - - - - - - - - - - b: 00400404000004434244400000443324233334000404433104000000000021244000000444204400044443
023340440444004030440434400444403334004043340040044440404004000444400004340004034400404000444000 +: 000000000000000000000000000000000000000000000000000000000000
11010000000001001000000000111100000000000100000000000000000000000000000000000000000000000000000000000000000000000000000000 r: 0040040400000443424440000044332423
3334000404433104000000000032204000000440200400044443134440440444004130440434400444403334004043340040044440404004000444400004340004034400404000444000 nfp/rfp: 14
1/131
k: 2 Stack: 43 18 49 - - - - - - - - - - - - - - - - - - - - - - - - - b: 00400404000004434244400000443324233334000404433104000000000021244000000444204400044443
023340440444004030440434400444403334004043340040044440404004000444400004340004034400404000444000 +: 000000000000000000000000000000000000000000000000000000000000
01101000000000100100000000011110000000000010000000000000000000000000000000000000000000000000000000000000000000000000000000 r: 0040040400000443424440000044332423
3334000404433104000000000022340000000444304000044443034400440444004040440434400444403334004043340040044440404004000444400004340004034400404000444000 nfp/rfp: 131/131
Solution found!
k: 27 Stack: 43 18 49 36 30 64 64 98 5 13 70 28 13 53 11 17 97 2 133 139 106 99 69 115 141 132 109 14 b: 0000000000000040000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 +: 00000000000000100000000000000
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 r: 000
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
0000000000000000000 nfp/rfp: 0/0
solution based on original piece order: 18,141,13,53,132,11,17,99,109,64,64,97,2,14,49,69,98,115,5,30,13,43,133,139,28,106,70,36

[camel]

So my solver is as fast as their fastest and I am still looking for hints on how to get past level 40 ...

[Hckr]

For me its always helpful to think about variations of the problem. Maybe for you to

[camel]

Wow ... someone else still active? )

What do you mean? Like similar puzzles with different rules?

[contagious]

Its really hard to give a hint to someone that is further in the puzzle

Well maybe i can share some of my thoughts.(Even though i haven't implemented anything more than a simple brute force.)

- threading (its sensible to use it in these kind of problems)
- custom n-base number system (maybe it will work or maybe it will provide an additional overhead)
- maybe there is a better heuristic you can use. (a greedy approach)

[Hckr]

Wow ... someone else still active?

Yes, as long as there are unsolved puzzles

Currently i'm also working on Modulo and hoping to get my ideas implemented soon.

What do you mean? Like similar puzzles with different rules?

Yes, changing some rules can help. But even slightly different setups could possibly give you new insights.
In Modulo you could for instance vary the board or number of shapes. But of course the hint is a general one, not specific to Modulo.

[camel]

Upgrading to a 64bit compiler helped a lot ... thinking about using a high memory aws instance ... my 8gig are not enough for my solver

[camel]

Its really hard to give a hint to someone that is further in the puzzle :D

Well maybe i can share some of my thoughts.(Even though i haven't implemented anything more than a simple brute force.)

- threading (its sensible to use it in these kind of problems)
- custom n-base number system (maybe it will work or maybe it will provide an additional overhead)
- maybe there is a better heuristic you can use. (a greedy approach)

- I am using threading in all 3 of my solver's components already. :-) I have written 2 programs to precompute board states and the final one uses a recursive approach.

- I thought about this many times but converting the representations will slow down the entire thing more than it helps. I have not yet tried it though. It would definitely reduce memory consumption to use a hex system (the value space of 10-base 64bit Ints isn't sufficient for depth^(8*8) boards?)

Also I am thinking about representing all valid board states after having used n-pieces as a tree or even multiple trees. Like 1 tree for every starting_tile<->solution_power<->solution_length index/combination. Clearly you know the inc/++ power, the amount of tiles that aren't yet zeros and the starting tile for every "H1"* board state and can do lookups in the right tree much faster that way.

*) See http://en.wikipedia.org/wiki/Meet-in-the-middle_attack

Thus far everything I tried (and I have tried a lot) was slower than just representing every board state as a single string. Precomputing all valid board states for the largest 5-6 tiles generates billions of combinations of course. The trick is to do it tile by tile (breadth first) and to apply the modulo operator before moving on. This way you can rule out millions of duplicate solution paths a recursive approach would all need to explore.

-) I can't think of any heuristics that would actually improve my solver. Computing islands that can't be solved with overlapping tiles (i.e. an "E" shaped and an "I" shaped piece can solve 3 islands with 2 tiles) and stuff slows the entire thing down by a few magnitudes. Also the early outs for the last x<depth pieces (only 3 piece left but one tile still needs 4 incs) are pointless to compute because my lookup tables are already ruling them out.

In the lower levels the most powerful heuristic is probably "remaining inc/++ power" based. My solver runs through those levels just using that heuristic.

Once I am satisfied with the speed of my lookup table creation I will move on to a 200gig memory aws instance ... it's only 3$ an hour ... ;-)

p.s.: "Luck" also plays a HUGE role. At the very same level you can get a board which will hit the "inc/++ power" based heuristic after placing piece 3-4 (start with the largest pieces fist of course) and thus resulting in not having to explore 2/3 of the entire search space. Even if you got a lookup table for 5-6-7 pieces this will speed things up a 1000 times. I can tell how hard a level will be to solve after testing the recursive (stage 3) solver without lookup tables for like 5 minutes. Just compare the performance of your solver with various boards for the same level.

I hope that I will solve lvl 44 next week but ultimately my goal is to have a solver that will also be able to solve the harder levels. It's still not that performant. Took 5 minutes to compute 100mil board states and like 8gig of memory ... damn STL ... :-///

Code: Select all

C:\Users\camel\Documents\Visual Studio 2013\Projects\ConsoleApplication1\x64\Release>test2.exe
BoardWidth=8 BoardHeight=8 BoardSize=64
Board:
1 0 0 0 1 0 0 0 1 0 2 0 2 1 1 0 0 0 1 1 1 1 1 0 1 1 1 1 1 0 2 2 0 1 2 0 1 0 2 0 0 1 0 1 1 0 0 0 2 2 1 0 0 1 0 1 0 2 2 0 0 1 2 0
Remaining Flip Power Lookup Table (nfp):
0 4 8 12 16 21 27 35 43 52 61 71 82 93 105 118 132 147 163 179
Board size=64 Depth=3 Initial needed flip power (nfp)=59 Number of pieces=19 Number of theoretical total combinations=1.97337e+026
Piece to number of moves (p2nom): 16 16 16 12 20 20 20 16 25 24 20 30 24 35 35 42 42 42 40

Processing k=18
Processed boardStates/Total boardStates 0/1 Resulting boardStates 0
Added piece 18 to 1 boardStates - resulting in 40 resultingBoardStates.
Duplicates=0
Processing k=17
Processed boardStates/Total boardStates 0/40 Resulting boardStates 0
Added piece 17 to 40 boardStates - resulting in 1680 resultingBoardStates.
Duplicates=0
Processing k=16
Processed boardStates/Total boardStates 0/1680 Resulting boardStates 0
Added piece 16 to 1680 boardStates - resulting in 70560 resultingBoardStates.
Duplicates=0
Processing k=15
Processed boardStates/Total boardStates 0/70560 Resulting boardStates 0
Added piece 15 to 70560 boardStates - resulting in 2962560 resultingBoardStates.
Duplicates=960
Processing k=14 (k==lookupTableSize. Those boardStates will be inversed.)
Processed boardStates/Total boardStates 0/2962560 Resulting boardStates 0
Processed boardStates/Total boardStates 100000/2962560 Resulting boardStates 3499994
Processed boardStates/Total boardStates 200000/2962560 Resulting boardStates 6999994
Processed boardStates/Total boardStates 300000/2962560 Resulting boardStates 10499967
Processed boardStates/Total boardStates 400000/2962560 Resulting boardStates 13999903
Processed boardStates/Total boardStates 500000/2962560 Resulting boardStates 17499838
Processed boardStates/Total boardStates 600000/2962560 Resulting boardStates 20999825
Processed boardStates/Total boardStates 700000/2962560 Resulting boardStates 24499817
Processed boardStates/Total boardStates 800000/2962560 Resulting boardStates 27999725
Processed boardStates/Total boardStates 900000/2962560 Resulting boardStates 31499649
Processed boardStates/Total boardStates 1000000/2962560 Resulting boardStates 34999574
Processed boardStates/Total boardStates 1100000/2962560 Resulting boardStates 38499552
Processed boardStates/Total boardStates 1200000/2962560 Resulting boardStates 41999470
Processed boardStates/Total boardStates 1300000/2962560 Resulting boardStates 45499431
Processed boardStates/Total boardStates 1400000/2962560 Resulting boardStates 48999414
Processed boardStates/Total boardStates 1500000/2962560 Resulting boardStates 52499398
Processed boardStates/Total boardStates 1600000/2962560 Resulting boardStates 55999397
Processed boardStates/Total boardStates 1700000/2962560 Resulting boardStates 59499291
Processed boardStates/Total boardStates 1800000/2962560 Resulting boardStates 62999264
Processed boardStates/Total boardStates 1900000/2962560 Resulting boardStates 66499174
Processed boardStates/Total boardStates 2000000/2962560 Resulting boardStates 69999164
Processed boardStates/Total boardStates 2100000/2962560 Resulting boardStates 73499077
Processed boardStates/Total boardStates 2200000/2962560 Resulting boardStates 76999060
Processed boardStates/Total boardStates 2300000/2962560 Resulting boardStates 80498981
Processed boardStates/Total boardStates 2400000/2962560 Resulting boardStates 83998956
Processed boardStates/Total boardStates 2500000/2962560 Resulting boardStates 87498918
Processed boardStates/Total boardStates 2600000/2962560 Resulting boardStates 90998890
Processed boardStates/Total boardStates 2700000/2962560 Resulting boardStates 94498884
Processed boardStates/Total boardStates 2800000/2962560 Resulting boardStates 97998883
Processed boardStates/Total boardStates 2900000/2962560 Resulting boardStates 101498858
Added piece 14 to 2962560 boardStates - resulting in 103688457 resultingBoardStates.
Duplicates=1143

[camel]

Now I got 100mil precomputed valid boardStates for piece 15-19, my memory is full and the lookup table is pointless ... derp ... ) Literally a standstill. Maybe a tree is the better choice? Also partial lookup tables (only considering every n-th tile of the board) that span more pieces seem to work way better ...

Code: Select all

k: 0 Stack: 0 - - - - - - - - - - - - - - - - - - b: 1000100010202110001111101111102201201020010110002210010102200120 +: 3 8 9 10 11 16 17 18 19 20 24 26 27 34
35 36  r: 1001100021012110112221102122102201012020010110002210010102200120 nfp/rfp: 61/163
goodStates=0 badStates=0
k: 1 Stack: 0 0 - - - - - - - - - - - - - - - - - b: 1001100021012110112221102122102201012020010110002210010102200120 +: 0 1 2 3 9 10 11 12 16 17 18 19 20 24 25
 32  r: 2112100022120110220001100222102211012020010110002210010102200120 nfp/rfp: 57/147
goodStates=0 badStates=0
k: 2 Stack: 0 0 0 - - - - - - - - - - - - - - - - b: 2112100022120110220001100222102211012020010110002210010102200120 +: 2 3 9 10 11 16 17 18 19 20 26 27 28 34
35  r: 2120100020200110001111100200202211122020010110002210010102200120 nfp/rfp: 54/132
goodStates=0 badStates=0

[eulerscheZahl]

I resigned, as I could not solve #44 in about 10 hours. But it seems that I have a completely different tactic than you have: my solver has less than 300 lines of code (C#, with web-interaction), uses nearly no memory (except storing the board for all steps of recursive function) and as I saw at Level97 of neopets.com, it has problems with large fields (stoped it after 1 or 2 minutes), while I can solve small fields very fast (level 42 in less than a minute in a virtual machine).

Code: Select all

<param name="depth" value="3">
<param name="board" value="1200202,1010101,0021122,2122121,2002222">
<param name="pieces" value="XXX,XXX ...X,.XXX,XX.. XXX,XX.,.XX X..X,XXXX,.X.. ..X.,XXXX XXX,..X X.X,XXX .X.,.X.,.XX,XX. XXXX,.X.. X.,XX,.X ..X,XXX,..X XX,XX XXXX,...X X.,X.,XX,X. .XX,..X,XXX ..X,.XX,XX.,.X. XXX,X.X XXXX,XX..,X...">

The only trick I used is not to loop over the stones, like it is done when playing by hand

[camel]

What do you mean by saying that you are not loop over stones?

My previous solver did not use much memory as well. It just did depth-first recursion with an early out based on the inc power (i.e. how many tiles they can "++") the remaining tiles provide. I sort the tiles by size and start with the ones providing the most inc power ... i.e. the tiles with the most fields set to 1. This early out allows to solve that lvl97 in 3-4 sec because the entire board requires almost as many incs (++) as all the tiles provide. It's a very easy level because of this. Placing the first 3-4 tiles on wrong spots will result in a board which requires more incs than all the remaining tiles can provide. You limit the search space by like 99% ...

(See the "nfp/rfp: 131/131" part in the code listing above ... the remaining inc power is exactly the same which is actually required ... so there is almost no margin for error.

But this does only get you that far. Level 44 got a huge, huge search space and the early out tactic only removes like 10% or so of the search space because the levels here are much more harder than those on neopets. Tiles get flipped (not just inc'ed until tilepower%depth==0) multiple times (i.e. they will go over the zero state multiple times).

That's why I started working on a solver with a "meet in the middle" logic. I.e. given 20 tiles I precalculate all the valid board states which can be solved with the last 8 tiles (the smallest tiles). Then all I need to do is to combine the first 12 tiles (the largest ones) and I instantly know which combination of the first 12 tiles will can be completed with the remaining 8 tiles by looking up the validBoardStates hash. Unfortunately I have not come up with a small/performant enough data structure for the lookup hash but I have also been busy doing other stuff the last weeks. A good way also seems to be only to consider ever other tile when doing the lookup table.

Maybe you can explain your approach? Maybe it's something I have not yet thought of ...

[camel]

In the 2nd code listing in this post

http://www.hacker.org/forum/viewtopic.php?p=21536#21536

you see the process of creating the lookup table. I start with a board full of zeros (the solution board) and then add the last (the smallest) tile to it at every possible location. This results in 40 board states. Those are the only valid board states prior to adding piece 18 which are solveable. I continue with the 2nd last (2nd smallest) until piece 14 ... the last piece for my lookup table. This time I not only add the tile but "invert" the resulting board states so that I can just do simple hash lookups and see if any boardstate after the first 13 pieces were added can be solved by adding the last 5 pieces via the lookup table. Pretty straight forward concept. It saves A LOT of processing power as you only need to do recursion through 13 of the 18 tiles but it still would run around 12 days in total using 20 threads (lookup table is created within a single thread then gets shared between 20 threads and every one of those will place the first piece in one of the 20 different locations) which is not what I want. I want to solve lvl 44 in at most an hour.

As said I did not use lookup tables until level 44.

I don't really want to start writing a heuristic based on borders and corners and stuff ... that's probably not worth my time as it is too game specific. I rather stick with improving what I got and think about other approaches.

[camel]

I also thought about only working with half of the board. (Like only use the black tiles from a chess board.) Like using every other tile through the entire process. Then run the entire thing again for the other half of the tiles and combine the solutions.

But this would ruin the inc power early out heuristic totally as pieces would no longer provide a fixed number of incs but incs would vary with every possible offset of the piece.

A piece which incs 3 tiles in a row on the full board would inc 1 or 2 tiles if you only consider every other tile of the board depending on placement of said piece.

[eulerscheZahl]

Sorry for late response, I thought there would be an email notification, seems that I forgot to use the checkbox below the input field.

I also tried using lookup-tables up to about level 30, but then memory consumption increased quickly and it became slow after all of my 8GB RAM were used.
Then I decided to completely change my stradegy: I pick one field (in the corner) and calculate the number of stones needed to fix this single field (of course there are more solutions because 2=5=8=... mod 3 for example). Then I choose the needed number of stones out of them, that are able to reach that field (not every stone properly fits into the corner) and recursively fix the remaining fields without touching the previous ones.
Thats why my solver has problems solving the large field, although there aren't many possibilities with early outs.
But I had no idea, how to realise this for my way of solving.
I also tried selecting fields in an intelligent way (less stones fitting there), but selecting the next field was too slow, so my straight forward code was faster although trying more possibilities. Maybe I should select the first fields and do the rest one after the other, but I was too lazy to code it.