Fifteen puzzle

[Keiji]

Playing Cogs got me wanting a few techniques.

Given the grid

ABC
DEF

(where F is blank)

I want to swap the AB pair and the DE pair simultaneously (swapping only one pair is impossible due to parity).

The best way to do this that I can see is EBA DFCA DEBCF.

To swap the AE pair and BC pair simultaneously, my solution is EBCFEB ADEB CFDA BEF

Any better ways to do these? Any advice on how to swap an arbitrary pair of pairs in an arbitrary shaped grid?

I'll probably add more tasks to this post as I find them...

[Mrrl]

I want to swap the AB pair and the DE pair simultaneously (swapping only one pair is impossible due to parity).

The best way to do this that I can see is EBA DFCA DEBCF.

This one is the shortest

To swap the AE pair and BC pair simultaneously, my solution is EBCFEB ADEB CFDA BEF

Any better ways to do these?

You can save one movement: CBEF CADEBCF DABEF

[Keiji]

Thanks!

[quickfur]

Ooooh the Fifteen puzzle!

I actually submitted an IOCCC entry based on generalizing the puzzle to 3D (and it actually won, believe or not... unfortunately it was submitted anonymously because I didn't expect it to win, so I don't get credit for it, har har, such is the irony of life).

I was going to generalize it to 4D, but while playing the the 3D version I discovered that the 3D-ness of the puzzle doesn't add any significant level of interest in it, so I gave it up.

[Mrrl]

It's interesting. If we take tesseract, place 7 cubic pieces on its cells, and paint the puzzle in 16 colors (1 per vertex)... what will it be? For other kind of polytopes it will be difficult because of odd order of ridges: how will we move cell of 120-cell to empty position? Reflect it? May be, some periodic pattern on {4,3,5} can give good sliding puzzle...

[quickfur]

It's interesting. If we take tesseract, place 7 cubic pieces on its cells, and paint the puzzle in 16 colors (1 per vertex)... what will it be? For other kind of polytopes it will be difficult because of odd order of ridges: how will we move cell of 120-cell to empty position? Reflect it? May be, some periodic pattern on {4,3,5} can give good sliding puzzle...

Well, duoprisms will give you a good sliding puzzle if you project the cells into curved surface of a duocylinder. There will be no way to exchange cells between rings, though, because of the orientation change that requires a rotation that will intersect many other cells. The resulting puzzle may not be very interesting.

[SharkRetriver]

Hi, I should have come here earlier.
I enjoy the 15 puzzle a lot.
http://www.youtube.com/watch?v=3DPh2DDmNv0

Does anyone know if there's a (free) 3D or 4D version of the puzzle?
Actually, I might as well try coding one for a challenge ^_~
As for the duocylinder, that for some reason reminds me of this:
http://www.jaapsch.net/puzzles/tower.htm
great, now I want to code that as well. This will only take at least a month T_T

Lastly, what's a {4,3,5}? Some sort of honeycomb?

[quickfur]

Hi, I should have come here earlier.
I enjoy the 15 puzzle a lot.
http://www.youtube.com/watch?v=3DPh2DDmNv0

Does anyone know if there's a (free) 3D or 4D version of the puzzle?

The one I wrote supports both 2D and 3D. Unfortunately it's only in text mode, and probably only works on Linux/*nix. It supports arbitrary dimensions (AxBxC for any positive A, B, C). It generates an impossible puzzle 50% of the time just to hook you. Perhaps I should port it to Java or something, with some actual graphics, so that normal people can play it.

It's not significantly more interesting than the original 15 puzzle, though. Once you know how to move stuff around in the 15 puzzle, it's trivial to extend it to 3D. The extra dimension actually makes it easier to shuffle things around, rather than harder.

To make things more interesting would require irregularly-shaped pieces (i.e. your general block-shuffling puzzle). In fact, this makes it a lot more interesting. Interesting as in, a LOT harder... NP-hard just in 2D, from what I last heard. In 3D and higher it may be even worse, perhaps PSPACE-complete or something crazy like that.

[SharkRetriver]

Alright. I guess I should think up some ideas for this thread lol.
I once coded a 15-puzzle in VB (youtube tutorial lololol) but yeah, it generated impossible puzzles 50% of the time.

[quickfur]

Alright. I guess I should think up some ideas for this thread lol.
I once coded a 15-puzzle in VB (youtube tutorial lololol) but yeah, it generated impossible puzzles 50% of the time.

It's not hard to fix that, though. You just have to scan the generated puzzle to find its parity, and if it's odd, it's unsolvable, so just swap any two pieces and it will become solvable.

[Mrrl]

You can do as we usually do with twisty puzzles: take solved position and make 1000000 random moves. Resulting position will be solvable.

And {4,3,5} is one of fours honeycombs in Hyperbolic space with finite cells and vertices: http://en.wikipedia.org/wiki/Order-5_cubic_honeycomb

[quickfur]

You can do as we usually do with twisty puzzles: take solved position and make 1000000 random moves. Resulting position will be solvable. [...]

Actually, for fifteen-puzzle-style block-shuffling puzzles, an alternative method is to pick a random number R between 0 and n!/2 where n the number of positions on the board, then find the R'th even permutation of the sorted array from 0 to (n-1) according to lexicographic order. Interpret this array as the row-major representation of the board, and you have a solvable puzzle.

Enumerating even permutations lexicographically is quite easy. It only takes O(R*n) time and O(1) space to generate the puzzle, and by picking the index of the even permutation randomly, you guarantee that every possible configuration of the puzzle is chosen with equal probability.