unforum

[chimera245]

Hmmm,

I wonder if the program would work better if you considered it to be a ray plane collision type thing.

You could use simple vector calculations to solve it then.

You'd still have the same number of permutations, but you wouldn't have to iterate through ship movements.

Essentially each block is a model in it's own Model Space coordinates. For each combination apply the appropriate Transformations (for the position of the block in the sequence) and Rotations (to apply North). This gives you the arrangement of islands and ships in world space.

Then project rays from the ships positions to see which islands they intersect with. You don't have to 'move' the ships. If the ray doesn't interset with an island - the model is invalid. If all the ships first rays intersect, record the islands, and repeat with next direction. Stop when a ray does not intersect. Rinse Repeat.

The reason why I suggest this approach is there is a whole bunch of accelerated mathematical functions and tricks to do this, and a whole bunch of programmers used to writing this stuff.

This is how graphics are displayed in 3D games. I have a little experience in it myself, but there will be others out there with a lot more . . .

[UKver2.0]

Um, will the final layout be in the same pattern as it is in on the card? i.e.
XX
XXXX
XXXX
XXXX
XX

or is it completely up in the air?

XX
XXXX
XXX
XXXX
XXX

or does it have to be square/rectangle?

XXXX
XXXX
XXXX
XXXX

Sorry for the DQ, but I just started looking at this one. Oh and, are we making any assumptions about what end is up? Seeing as the in the original there was no question as to NESW?

[chimera245]

OK - braindumping here what I mean.

Each square of the puzzle can be considered to be a little area of space, with it's own local coordinates. Let us assume that the two varying coordinates are in the X and Y directions.

We put the origin in the middle of the centre square, and the centres of each of the other squares are 1 unit +/- in the X or Y direction from them.

Looking like this:

-1,1 0,1 1,1
-1,0 0,0 1,0
-1,-1 0,-1 1,-1

Also in these little local areas, there may be a box (an island), centred in one of the box centers, e.g. at 1,1.

So you have 16 little local models arranged like this.

Now for computing the solve. Each combination involves moving these local spaces to a different place in World Space. This involves the application of a Translation Matrix to move it to the appropriate place, and a Rotation Matrix to orient it North.

Apply all these transformations to your set of worlds and you have a transformed set of coordinates for all the islands and the ship's original positions.

The matrices to do these moves BTW can be pre stored so they don't need to be calculated on the fly.

Once you have mapped all the squares to their positions, you start with each ship.

Let us say the North arbitrarily represents going positively in the Y direction. So - if the ship is due to move North, it can be considered to be moving in a Vector of [0,1] from it's position in World Space. You can quickly test to see if that Vector intersects with the transformed coordinates of an island. If it does, transform the coordinate of the ship to the new island (recording what you have done), and repeat for all the other ships. If the Vector does not intersect - then the combination is not valid.

A client could be written that did this fairly quickly. You could leverage built in Matrix functions of graphics languages such as OpenGL for that maths, the Vector collision stuff is much simpler than you usually using because of the simplistic nature of the coordinate systems.

Am I completely off base here?

[SteveC]

Aren't you suggesting storing 16! (permutations) * 12^2 (island/sea positions) + 4 (boat positions) bytes before starting to analyse here?

Or at least 16! * 16 + 4 referencing the cards..?

Or does it not matter if you make them on the fly, if so, is the core of your argument that there are some funky matrix maths tricks you can do to gain speed?

[chimera245]

What you need to store for this algorithm is:

1) You store 1 transformation for each final position (not combination), i.e. if assume a symetrical 4 x 4 grid you have 16 transformation matrices
2) Assuming you have to rotate to north you have 4 rotational matrices
3) You store the 16 world maps

That store is a trivial amount of information.

Regardless of how you are solving this, you cannot store the 16 * 4 * 16! pieces of information you need to represent the combinations permanently (it is a ridiculous amount of data no matter how you look at it) but you can store where you are at.

If you assume that if each permutation is represented by 16 bytes (1 byte for each map piece representing it's translation/rotation combination) and that the permutations increase in a known sequence you can store a 'bieing done' or 'last done' value which is monotonically increasing as combinations are rejected.

I *think* the advantages of this method are:

A) that the application of the permutations is simply matrix multiplication with standard stored matrices, using functions which have been designed to do this fast (graphics accelerator functions)
B) the testing of the paths is limited to simple ray tracing checks

Can anyone see any flaws in my arguments?

[Stratman]

I can see from the link that Cast Adrift 1 was a 3x3 grid.
Can anyone explain why in this case people seem to be assuming this is to be a 4x4 grid? I just can't see any reason to change it - surely the grid is as laid out on the card?
If you are going to change it...why a 4x4 square? Why not a cross? A pyramid? Whatever shape you can make? If the assumption is based on Cast Adrift 1 being 3x3 - then we have exactly that here - a 3x3 grid but with extra squares added to make it more difficult.
About the only thing from Cast Adrift 1 that seems of real relevance is the fact the north was the obvious direction and none of the tiles were rotated. (Looking at the link thread that appears to be the case...I wasn't there so correct me if I am wrong).

[SteveC]

Stratman, 4x4 grid because there are 16 "blocks" - that's 4x4.

Square because we're being optimistic.

[xorsyst]

Hmm, this seems tricky

[UKver2.0]

Re: Hmm, this seems tricky

[xorsyst]

No, I assumed north was always up (just 20,000,000,000 combinations). Allowing rotations would give even more answers

X

[Curlytek]

Re: Hmm, this seems tricky

[c1023]

Re: Hmm, this seems tricky

[SteveC]

At a guess, xorsyst is running a solver that just looks at the solve ship, not the others...?

To clarify for everyone, the solution is a board where every ship can complete their journey - the answer is the list of islands that one of them visits...

If anyone can help with a small issue I have, I'm trying to work out a way to create all the permutations of {0,1,2,3...12,13,14,15} in such a way that I can predictably know a range to ignore because of the "impossible" locations for each tile (first row, last row, first column etc..)

I can create one that's pretty non-sequential, but that is a bit crap for knowing which to exclude easily (have to search each combo to exclude them). It also seems pretty wasteful as can have to do up to 7 swaps per permutation.

[Gibbet]

Here for the purposes of completeness is my effort at a solver.

Slower and more random it may be, but it is nice and colourful and provides details about the best solutions as it processes.

Should be able to find solutions close to the solve that might just require swapping a couple of tiles as well.

The best I have achieved after a couple of hours is 2 ships correctly plotted and 34/42 of the required island transisitions accounted for.

However it is a random process at the moment so if anyone does actually fancy letting it run; there is no guarentee it will EVER find the solution.

But you could get lucky and find it before some of the more systematic solvers

If such a miracle occurs, each ship will be x/x, and "Best So Far" will read 42.

Clicking Show/Hide overlays the best map found so far.

If nothing the pretty ships may induce a heightend state of being/(migrane) that will allow you to solve some other cards.

[SteveC]

Check for me?