unforum

[c1023]

SteveC:

Here is your map:

[ahdok]

Gibbet, your solver appears to lie.

http://www.srcf.ucam.org/~dtb26/gibbet.png

boat B starts by going north. It sails of the end of the world into everfalling oblivion doom, rather than visiting nine islands. (Note, pretty much every "best score" I've had also lies.)



it's still hypnotic though.

[arnezami]

Ok. I've build a different kind of solver. Its recursive based and it begins with 1 boat (I've chosen boat C because it has the most complex path) in the middle of a fictive 7x7 map and adds tiles to complete the path of the boat (so its not shuffling 16 tiles each time). If it reaches a "dead-end" (or in our case: if the map becomes too big) it backtracks and tries different tiles. If the path of a boat is completed it adds more boats to the map etc.

Anyway. I've found several/dozens of solutions for a 4x4 map (without even reaching 1% or so of my search space).

Here are two examples: (please verify)



(don't worry about the missing tile btw: you can add it, but its not needed)



As I said: there are MANY solutions. And thats puzzling. Our assumptions must be wrong. Maybe we need to stick to the map layout on the card or maybe there are other restrictions.

I don't have time atm. But I plan to run my program with the restriction of the map shape (like on the card).

Maybe other suggestions?

Greetz,

arnezami

PS. Could somebody please check if the card directions are EXACTLY right? I don't own the card... Thanks!

[Stratman]

I am still of the opinion you have to work on the grid as it appears on the card. As far as I can see there is nothing on the card to suggest changing the layout and if Mind Candy had wanted to set a 4x4 grid - there is plenty of room on the card for them to have done just that.
Surely this puzzle is tough enough without having to 'guess' a new layout before you even start?
However, I do not have the skills to program a solver and I think getting a solve on a trial and error approach to this would be nothing short of miraculous!
So arnezami can you modify your solver to try the grid as printed? I think that is the right approach.

[UKver2.0]

[Asib]

er guys the presumtion is that the card tiles face north

However the background picture could be a clue to direction


The sun at the top of the card casts no shadows e/w on the clouds
so its midday
in the northern hemisphere that means the sun is directly south so the tiles are upside down!

Could be in Australia tho

[SteveC]

OK, I've found a solution through brute force pretty early on, so I guess it's correct that we need to maintain the "odd" shape..

FWIW, not tested it, could someone check

12, 0,11, 7,
2, 3, 9,10,
4, 5, 8, 1,
6,13,14,15

I think it's a "solution"..

I'll re-code tomorrow for the specific shape - gonna be a lot slower too because I'm doing a lot of very simple boolean comparisons at the moment - integer comparisions will slow it down a lot I think.... though who knows the optimisations computers use?!

[UKver2.0]

[SteveC]

Looking at it again, I can actually do the card shape with not much slow down - include my optimisations and I'm back to being able to search the space in a few months (or issue lots of clients that break that up lots)

Will get onto that as soon as I can... Who knows when that is though..

..edit..

well, not long after - that was easy - my client is now keeping the card shape.. 9 deep so far (eg, managed to sail B and failed immediately on A.)

[ahdok]

[SteveC]

Well, I've run an "original shaped" grid for 12 hours now - it's gone through 11 billion combos and managed a deepest grid of 37 steps (or so...?)

It's:

00:10:-1:-1
05:12:03:04:
11:02:08:09:
06:01:07:13:
14:15:-1:-1

So, fingers crossed for enormous luck on this - still got about 1.5 years to complete the space

[arnezami]

I've changed my solver to only allow the "special shape" for solutions.

It helps. But only a bit. It reduced the amount of solutions by about a factor of 10. But there are still more than 100 solutions (after doing approx 86% of the entire search space).

Here are two examples:


and another one:



So all in all it seems we need another restriction OR try all 100+ solutions.

I've attached all discovered solutions so far (106) in a zip file.

Any ideas? I'm currently thinking about changing North (basicly rotating the compass).

arnezami

PS. For clarification: my search space is way smaller than in the shuffle-method (which is 16! roughly 10^13). My solver literally generates all possible paths for boat C within our oddly shaped map. Those are in fact a little over 280 million paths for C (far less than 10^13). It only takes half an hour of cpu time to generate them. For each generated path for boat C (and its corresponding partial map) it then goes on adding boats. The nice thing is that most tries will very quickly fail because the parial map needed for the path of C reduces options radically for added boats therefore speeding up the search enormously.
Right now I force it to only try adding boats in a fixed order. Sometimes this is not possible (if a partial map is generated that doesn't contain the starting point of the next boat) which is why it "only" covers 86% of the search space (it skips trying to add boats for 14% of all generated paths for C). I'm probably going to raise this but right now we already have too many solutions...

[Stratman]

Checked the above two and they certainly work out.
The only thing I can think now is that the boats are not allowed to revisit islands - although obviously it doesn't say that.
I can only assume another correction will be coming from Mind Candy - but if they are going to allow the solves (like in Weighs and Means) they are going to have to allow for hundreds of possible correct solutions by the sound of it!
Well done on those solvers programs!

[ahdok]

you could try telling it to skip a boat it can't add, then try adding it later (on the grounds that you'll probably have the other boats already in your system.) that'll cut down the number of lost solutions, although, of course we still have too many. (Once all boats are added that can be, you could add a bit of code that throws in the new boat tile in one of the available gaps, and checks it, then if it fails, moves that tile to each remaining space.) - but I'm guessing it's fiddly compared to what you have already.

[arnezami]

Ok.

I may have got the solution...

I've been rotating! And the effects are significant. Right now I've tried 90, 180 and 270 degrees rotation. To cut to the chase: when rotating with 90 degrees there are only 3 solutions (!!) for all four boats (with >99% search space coverage).

With 270 degrees rotation there are 63 solutions, with 0 degrees (original) its now 254 solutions (with 99.6% coverage) and with 180 degrees its 117 solutions.

So IF rotation was required/intended there are 3 very possible solutions. Technically the solver gives 6 solutions but the first 4 are equivalent to each other (the path of B doesn't change). So its only 3 solutions that are available when rotating the directions of the ships with 90 degrees (in other words: if a ship normally went north it now goes east on the map). For easier reading/verifying I've rotated the picture counter-clockwise below.

Here are the three solutions (for 90 degree rotation):



I'm quite tired atm. Maybe somebody else can figure out the exact island numbers B goes through. And try these solutions. Be aware of the rotation though.