[bonanova]

A friend gives you the game of 15 squares that slide in a 4x4 container.

After a little manipulation, expert that you are, you solve the puzzle,

obtaining the following arrangement:

..1..2..3..4..

..5..6..7..8..

..9.10.11.12..

.13.14.15.__..

where __ shows the empty space. If you're unfamiliar with this puzzle,

you have two moves you could make from this position, namely slide 12 down

or slide 15 to the right. And so on. Note a move can be described by giving

the number on the square that is moved.

Here's the puzzle, in two parts.

1. Using only legal moves, can you make a 4x4 magic square?
   .
   In a magic square, numbers in each of 4 rows, 4 columns and
   2 diagonals sum to the same number.
   Count the empty space as zero.
   .
   Hint: not all configurations can be achieved.
   For example, two adjacent numbers cannot exchange positions.
   For example, you could not get the top row to be 2 1 3 4 with the
   other 3 rows unchanged. So if write out a magic square of 0 -15 on paper,
   there's a 50% chance it's not reachable from the above starting position.
   .
   
2. If your answer is yes, how can it be achieved with the fewest moves?
   The solution is the 4x4 array of numbers and the list of moves: e.g., 12, 8, 7, 6, ... etc.
   

Above all, have fun.

[Guest]

We need to get a picture of what we are trying to achieve .

Magic Number = 30

Range: 0-15

4X4 Magic Square possible formats :

12 01 02 15

11 06 05 08

07 10 09 04

00 13 14 03

12 02 01 15

11 05 06 08

07 09 10 04

00 14 13 03

Now how to get to one of these in the least moves

EDIT: Formatting

Edited October 3, 2008 by Ben Law

[bonanova]

We need to get a picture of what we are trying to achieve .

Magic Number = 30

Range: 0-15

4X4 Magic Square possible formats :

12 01 02 15

11 06 05 08

07 10 09 04

00 13 14 03

12 02 01 15

11 05 06 08

07 09 10 04

00 14 13 03

Now how to get to one of these in the least moves

EDIT: Formatting

That's step 1, now to get there.

[Guest]

i'm sorta confused :huh:

this has never been solved so i thought i'd reply

[bonanova]

i'm sorta confused :huh:

The puzzle just asks for the shortest sequence of moves from the "solved" position to any "magic square" position

[peace*out]

I think the 0 throughs the whole thing off

[bonanova]

I think the 0 throughs the whole thing off

It can be solved.

Count your moves, and post the lowest number.

[Guest]

Wow this is an old and unsolved riddle- the best kind! I have to go to work but I'm hosting, so I should have plenty of free time to work on this haha, expect an answer when I return! (Note: it might not be the correct answer )

[HoustonHokie]

Bonanova's signature keeps taunting me regarding this puzzle, so I had to do some research to see if I could understand some of the basics.

In order to figure out if a puzzle is solvable, you need to figure out the sum of the permutation inversion numbers in the puzzle. There are 15 of these numbers, corresponding to the 15 squares on the board. To calculate n_i, which is the permutation inversion number for a particular square, simply count how many smaller numbers appear "after" n, reading from left to right and up to down. In a solved board, every n_i = 0. N is the sum of n_i and is the number of permutation inversions for the board. If e is the row number of the empty square (row 1 at the top, row 4 at the bottom), then the sum N + e tells us whether the board is solvable. If N + e is even, the board is solvable. If odd, the board is impossible to solve. So, given a particular magic square configuration, this information should tell us whether it is indeed solvable.

Looking at the magic squares presented by BL earlier,

12 01 02 15

11 06 05 08

07 10 09 04

00 13 14 03

N + e = 11+0+0+11+8+3+2+3+2+3+2+1+1+1+0+4=48, so this magic square should be solvable.

12 02 01 15

11 05 06 08

07 09 10 04

00 14 13 03

N + e = 11+1+0+11+8+2+2+3+2+2+2+1+1+1+0+4=47, so this magic square should not be solvable.

Having established, therefore, that at least one magic square arrangement is solvable, the question now is how to get to one in the least amount of moves, and then, finally, to show the moves that lead from magic square to solved puzzle. Might require more research. Starting with how many magic squares are possible using 0-15. I don't know for sure, but I'm guessing that the one with the lowest N or lowest N + e will be the one we're looking for.

BTW, if you want more info on permutation inversion numbers, here's a good page: Wolfram site

[Prof. Templeton]

14 03 08 05

09 04 15 02

07 10 01 12

00 13 06 11

Hmmm, they all equal 30 so far.

[HoustonHokie]

14 03 08 05

09 04 15 02

07 10 01 12

00 13 06 11

Hmmm, they all equal 30 so far.

A property of magic squares is that the sums will always be the same - all the sums will equal 30 if the range is 0-15. The permutation inversion sum for that board is 53, so that board isn't solvable anyway.

[Prof. Templeton]

A property of magic squares is that the sums will always be the same - all the sums will equal 30 if the range is 0-15. The permutation inversion sum for that board is 53, so that board isn't solvable anyway.

I know. It was said "tongue in cheek".

Here's the numbers I get

13,2,6,3,5,2,0,1,2,2,2,2,2,0,0

Which equals 42. How did you come up with 53?

[HoustonHokie]

I know. It was said "tongue in cheek".

Here's the numbers I get

13,2,6,3,5,2,0,1,2,2,2,2,2,0,0

Which equals 42. How did you come up with 53?

It is solvable - I miscalculated. Although I would have said 46 by adding the row of the blank space.

[Prof. Templeton]

It is solvable - I miscalculated. Although I would have said 46 by adding the row of the blank space.

I wasn't too sure if that square should be included. Wolfram seemed to imply that it wasn't. Can we figure out how many "magic squares" are possible? Surely some would be easier to get to from the original set-up then others.

Edited February 12, 2009 by Prof. Templeton

[Prof. Templeton]

I counted the number of steps to go from a "solved" 15 puzzle to my magic square.

12,11,10,14,13,9,5,1,2,6,14,5,1,2,6,14,2,6,14,3 - That takes care of the first two numbers top left (14,3)

4,8,11,10,5,2,7,11,10,5,11,10,5,11,10,4,8,5 That does the top row (14,3,8,5)

11,10,2,1,9,13,1,7,6,9,7,6,4,11,10,12,15,2,11,10,12,15,2,11,10,12,15,2,11,10,12,

15,2 That does the next row (9,4,15,2)

12,10,1,13,7,6,13,7,6,13,7,6,13,7,10,1,6,13 And that finishes the bottom two rows (7,10,1,12 and xx,13,6,11)

For the top two rows I worked from left to right just because it seemed more intuitive, but for the bottom two rows I had to work from right to left because of where the empty space is.

I tried to think about where the numbers had to be so I wouldn't waste movements and it was done in 86 moves. The website that had the java version of the fifteen puzzle had a solve button (which is why I picked it so I didn't have to first solve the puzzle and then re-solve in the new magic square configuration) and you can watch it solve the puzzle. It went much to fast to record the numbers it was moving, but I did count the number of moves as it went along and it took it 136. I would have thought it more efficient. Here's the site I used. It took 20 moves just to get the first two numbers in the right spots, I think a configuration where the top row is closer to the original may yield less moves.

Edited February 12, 2009 by Prof. Templeton

[HoustonHokie]

I wasn't too sure if that square should be included. Wolfram seemed to imply that it wasn't. Can we figure out how many "magic squares" are possible? Surely some would be easier to get to from the original set-up then others.

I've seen different numbers for that. There are 324 pan-magic squares - of that I'm certain, but they are a subset of the total number of magic squares. For the total number, I've seen 924 and 4080, among other estimates.

[Prof. Templeton]

Actually here's my same magic square as above, but in

15,11,7,6,10,14,13,9,14,10,5,14,9,13,10,7,6,5,2,1,14,9,7,

2,1,3,4,8,5,4,8,5,12,15,11,6,2,1,4,2,15,12,2,15,1,10,13

[HoustonHokie]

I got a list of 924 magic squares and another list of the 324 pan-magic squares from a couple web sites, popped them into Excel, and had it calculate the inversion sum for all of them (by the way, I decided e works better if the bottom row is 0 and top is 3 - that way, a complete square is 0 instead of 4). The lowest even number I got was 46 (which I guess would be the optimal starting point??), but it only showed up on the pan-magic ones, so I'm think the list of 924 is somehow incomplete, and it's hard to search for a particular square to know how incomplete it is.

My thought on efficient solving is, given a particular starting point and inversion sum, choose your moves so that the inversion sum trends lower. In other words: every move has at least two possibilities and up to four (two to four squares that you can slide into the blank spot). Compare the inversion sum for all possibilities, and choose the lowest. You ought to be able to keep the sum equal or lower almost all the time, except possibly in the corners, where you don't really have a choice. I don't know what to do in case of a tie, except look at the next generation possibilities. I'll try that with one of the N = 46 squares and see what I get.

[HoustonHokie]

Well, I'm sure that the "steepest slope" method I proposed in my last post will eventually solve the puzzle. But it will not be efficient about it. After 72 moves, I'm giving up. The problem seems to be when the blank space is in the corner - you can't make any choice, and I kept getting into situations where the blank space was in a bottom corner and it would pull a low number down, forcing the inversion sum to rise. I got a sum as low as 8 by my 42nd move, but by my 72nd, I'm back up to 14, and I've been as high as 16. I've thought about removing the e term and seeing if that makes any difference (it might not put the extra weight on keeping the blank low on the board, which seems to be problematic). But I won't try again until later.

[Guest]

If it helps (and it probably doesn't), any slidy puzzle thing is solvable in 80 moves or less. Its late, but the wikipedia article seems to suggest that measures of dificulty for these puzzles include (i) the number of pieces that are out of place and (ii) the (manhattan) distance each piece is from its endpoint.