8
$\begingroup$

We've already removed the magic from a 3x3 magic square. Recently, one of our 4x4 magic squares was scrambled in an earthquake and I need your help to reactivate it's magic:

Screenshot of a 4 by 4 grid. The top row contains the numbers 8, 6, 7 and 16. The second row contains the numbers 1, 4, 3 and 10. The third row contains the numbers 9, 13, 2 14. The final row contains the numbers 11, 12, 5 and 15.

Objective

Your objective is simple, rearrange the square so that it becomes a valid 4x4 magic square once more:

Screenshot of a valid 4 by 4 grid. The top row contains the numbers 1, 15, 14 and 4. The second row contains the numbers 10, 11, 8 and 5. The third row contains the numbers 7, 6, 9 and 12. The final row contains the numbers 16, 2, 3 and 13.

How to Play

To rearrange the tiles, you'll need to swap them, one by one into their correct positions. For example, the $8$ tile can be swapped with the $1$ tile to effectively place the $1$ tile in a correct position:

Screenshot of the top two rows of the scrambled grid with the 8 and 1 tiles swapped. The top row contains the numbers 1, 6, 7 and 16. The second contains the numbers 8, 4, 3 and 10.

However, be very careful on which tiles you swap as there are two important rules to swapping tiles:

  1. Each tile can only be swapped the number of times its face represents.
  2. When swapping tiles, the lower face value is deducted from the higher face value's remaining moves.

For clarity, let's use the $8$ tile as an example. At the start, it can be moved 8 times before it becomes locked into place. Swapping it with the $1$ tile reduces the number of times it can be moved going forward to 7. To clarify the second rule, imagine that we now swap the 8 tile with the $4$ tile:

Screenshot of the top two rows of the scrambled grid with the 8 and 1 tiles swapped. The top row contains the numbers 1, 6, 7 and 16. The second contains the numbers 4, 8, 3 and 10.

Two things happen here; the $4$ tile now has 3 moves remaining, as does the $8$ tile. Now, assume you want to swap the $8$ tile with the $6$ tile; in this scenario you can't because $8$ doesn't have 6 moves remaining, it only has 3 because you swapped with the $1$ and $4$ tiles already.

Movement Restrictions

Tiles can be swapped if they are adjacent to each other. Reactivating magic squares is a much more tedious process than deactivating them; as such, outside tiles are not considered adjacent. Diagonal movements are not allowed. As an example, the $4$ tile can be swapped with the $6$, $1$, $3$ and $13$ tiles initially, but no others:

Screenshot of a 4 by 4 grid. The top row contains the numbers 8, 6, 7 and 16. The second row contains the numbers 1, 4, 3 and 10. The third row contains the numbers 9, 13, 2 14. The final row contains the numbers 11, 12, 5 and 15. In this grid, the 6, 1, 3 and 13 tiles are highlighted with a green hue, while the 4 tile is highlighted with a blue hue.

Yes, I've created an interactive version of this puzzle. It will be available to the public (linked here) after this puzzle has an accepted answer.

Clarifications

Does it have to become the magic square you showed? Or is any 4x4 magic square acceptable?

Any valid magic square is acceptable, though answers that don’t use the provided square should explain why they used a different square.

Suppose we're in a position where $8_3$ is next to $4_4$. Is it true to say that "both have moves remaining so they can be swapped" (which would result in all of 8's moves being used and possibly a debt/negative balance afterwards) or "$8_3$ cannot afford to pay the extra penalty, so cannot move at all"?

$8_3$ cannot afford to pay the extra penalty, so you cannot move at all.

Hints

The initial configuration should not be able to be rearranged into the provided valid magic square. This is due to the second row in particular. Instead, you'll need to determine if a new magic square can accommodate the initial configuration, based on known limitations. For example, the $1$ tile only gets 1 move, so it can only be in 1 of 4 positions in the completed grid. From here, think about which location it's most likely to be in based on how magic squares are calculated and work from there.

The question is phrased carefully.


Can you reactivate this 4x4 magic square?

$\endgroup$
11
  • 1
    $\begingroup$ Does it have to become the magic square you showed? Or is any 4x4 magic square acceptable? $\endgroup$
    – Dr Xorile
    Sep 30 at 3:29
  • 1
    $\begingroup$ Suppose we're in a position where $8_3$ is next to $4_4$. Is it true to say that "both have moves remaining so they can be swapped" (which would result in all of $8$'s moves being used and possibly a debt/negative balance afterwards) or "$8_3$ cannot afford to pay the extra penalty, so cannot move at all"? $\endgroup$
    – Steve
    Sep 30 at 13:02
  • 1
    $\begingroup$ Following the removal of the no-computers restriction, I set the computer working on this. The main thing I've found so far is that a non-optimised undirected brute-force breadth-first search is far less effective than on the practice problem. Will leave it running, but I'll probably need to work more on optimisations later to get much past "Starting on working set #101, which has 1317995 members... [37473124 already in later working sets]", and the process soon after reaches the available 7GB of ram usage and becomes memory bound rather than CPU bound. $\endgroup$
    – Steve
    Oct 1 at 11:58
  • 1
    $\begingroup$ @taco it's a very crude algorithm at present - find all possible moves from the starting state, and report if any of them are a magic square, and with a very inefficient check for whether it's a magic square (see IsMagic() function on the source code now posted to the other puzzle for just how inefficient that part of the current implementation is - the code essentially implements the general definition of a magic square - I initially mis-estimated the search space and hadn't been expecting to need further optimisation). $\endgroup$
    – Steve
    Oct 1 at 13:28
  • 3
    $\begingroup$ A further thought - the game seems reversible... so rather than starting at the given grid and trying to find a magic square, one could start with a full list of magic squares, filter out the ones which "obviously" cannot become the given square (e.g. low numbers must move too far), and then consider only moves which "help" to get towards the target state. Google tells me there are 880 4x4 magic squares, but maybe about 80% can be trivially eliminated due to positions of the low numbers. $\endgroup$
    – Steve
    Oct 7 at 14:21
3
$\begingroup$

[I previously deleted this answer, as the method was flawed, so the conclusion was not sound. I believe the bugs in my program are now fixed]

Following the removal of the tag from this puzzle, this answer initially treats it as a .

In summary (TL;DR), my current answer to the question "Can you reactivate this 4x4 magic square?" is

No.
It is not possible using the rules given. Unfortunately the damage to this magic square is beyond the possibility of repairing it with this method.
The obvious secondary question is "why not". This probably needs some better insight into the problem to answer properly, and some intermediate lemmas that can be used to simplify the problem to a point where heavy use of computing resources is not necessary...
but at present my only answer to the "why not" question is "Computer says no!".

To the more specific question of whether it is possible to restore the magic as the given magic square, this is now proven impossible in one of the later spoiler blocks following "first stage of a proof".

The approach taken was to adapt the program I used for my supplementary answer to the "practice" problem. This immediately ran into problems because when there are 16 squares with moves totalling 136, the search space is considerably larger than 9 squares with with moves totalling 45 - the fan-out of exponentially increasing numbers of states is much larger, and the program ground to a halt when its storage exceeded the available memory on the computer.

There were several rounds of bugfixes and optimisations; the first version was, from the second move onwards, generating disallowed moves between "outside" tiles which wrapped around in the 3x3 puzzle but not in this one, making an impossibly large search space. The second version disabled these moves but also incorrectly disabled all swaps within the last row and last column, making the search space much smaller than intended, and that was the point when I first posted this answer, using this version of the program, and its output to conclude that:

that no magic square could be made by swapping tiles according to the specified rules. Initially I assumed this was another bug, so tried generating starting states from which a known magic square could be reached within a small number of swaps. The program correctly found those magic squares. [This initial conclusion was not sound, as mentioned above I subsequently DID find another bug in the program, leading to this answer being deleted for a few days...]

Following up from the hint given, and combined with that initial conclusion, I'd originally continued thinking as follows,

"The initial configuration should not be able to be rearranged into the provided valid magic square."
...
"The question is phrased carefully."
it is apparent that it doesn't state the initial configuration can be re-arranged into ANY valid magic square, and indeed the question title asks "Can you...?" and doesn't directly state that a solution path exists.

My further hypothesis was that a property of the grid that remains invariant under the "swapping" mechanism - perhaps analogous to a parity check - is shared between all valid magic squares, but the starting state initialises this incorrectly. If so, it's possible that the complicated rule set is a red herring, and that any number of swaps of any adjacent cells would still be unable to "restore the magic". So that in order to be able to solve this puzzle manually, one should look for a property that remains invariant after the swapping operation, such as a form of parity check on the grid. My hunch was that the puzzle is looking for a "proof of impossibility" rather than following the typical format of this site of having a puzzle with a known solution.

However, when I considered how the same game played on a 2x2 grid might play out, following the Teakettle Principle by then taking my complicated program, and modifying it to

allow infinite swaps by not decrementing the available moves, to run on a 2x2 grid and to output all states encountered, all 24 theoretically possible 2x2 grids were generated by swaps, calling into doubt this entire "parity" argument... if infinite swaps allow any 2x2 grid to be converted into any other 2x2 grid, then the same would apply to larger grids too.

It was also when doing this modification that I found the implementation bug in the second version, and after fixing this, I went through several rounds of compression functions to allow more and more results to be worked on, finally disabling the path-to-solution that was taking more than half the memory, so that it would merely focus on "proof of existence".

Several optimisations later, I had a version of the program which compresses each state to 96 bits to focus just on proof-of-existence. [source code] [output], which showed

after more than 24 hours runtime that the problem space was too big for this approach, even with sufficient compression to be working on rather more than half a billion states at a time, it ran out of memory, having only fully processed states where at least 72 "moves" remained within the grid (each swap uses between 2 and 16 "moves").
Further thoughts occurred such as writing out batches of intermediate state to disk, then merging them on re-loading, so that only a single working set needed to stay in memory at a time. That sounded rather more effort than I wanted to use, and might have increased run time to several days where I needed the computer for other stuff...

To take this further, as mentioned in a comment on the question, I realised that

the game is reversible. If after a sequence of valid moves, one were to then "recharge" all the tiles to their full capacity of moves, the sequence of moves can then be reversed, and after replaying this reverse sequence, the original starting state will be restored. Each tile swaps with exactly the same tiles it did with the forwards sequence, so will use exactly the same number of moves.

With this observation, I then

wrote a program that first generates all possible magic squares, feeds those as starting states into the first generation, and then tracks which legal positions have all tiles "within range" of the correct position in the single target state (the initial given position for this puzzle), and then processes only the states that pass this simple heuristic.
Although this starts with a lot more states, most of them get pruned from the working sets at each iteration, so the memory requirement should be less. Needless to say, the first version didn't work, running out of memory again, but finally after checking whether a state was "within range" before adding to the future working set (meaning duplicate effort but lower memory usage), I had a version which ran to completion. The source code and output for this are also available.

This shows that

The original conclusion did in fact appear to be correct - there is no path from the given starting state to any of the 880 valid 4x4 magic squares, including all 8 reflections and rotations of each.
However it's still no closer to demonstrating "why" other than that a needlessly complicated program said so.

This finally puts me back

where I thought I was at time of initially posting this answer: having a somewhat unsatisfactory "computer proof" of non-existence that implicitly relies on having a bug-free program... so if there are unknown errors in my program/approach, there may yet be a solution that my program missed due to such bugs.

but in any case a much more elegant solution than throwing a computer at it would be far preferable in my opinion - the puzzle originally was originally tagged which clearly means I've missed something fundamental with this computer-generated search for techniques to reduce the search space to get it within human capabilities...

Thoughts towards solving it "properly"

The only hint given so far includes this:

For example, the 1 tile only gets 1 move, so it can only be in 1 of 4 positions in the completed grid. From here, think about which location it's most likely to be in based on how magic squares are calculated and work from there.

Taking that into account, I did the following initial analysis:

Adjust the final version of the program I was using to add diagnostic output telling me where it found each number in the magic squares that weren't trivially eliminated. This provided the following output, suggesting very little restriction on the positions of the other numbers (and even when filtering the tallied states to fix the '1' in one of the possible 4 positions, most choices of position for most other numbers couldn't be trivially eliminated, save that high numbers more often share a row, column or diagonal with the '1' and low numbers more often don't):

 Frequency of finding value 1 in each position:
   410,     0,     0,     0
   357,   232,     0,     0
   335,     0,     0,     0
     0,     0,     0,     0
 Frequency of finding value 2 in each position:
     0,     0,   139,     0
     0,    62,   132,   102
    59,   132,    62,   159
     0,   152,   205,   130
 Frequency of finding value 3 in each position:
    16,    76,   113,   159
    12,    42,   115,    91
    49,   119,    44,   130
     0,   128,   155,    85
 Frequency of finding value 4 in each position:
    80,    81,    78,   129
    50,    53,   127,    69
    48,   137,    37,    71
   120,    84,    77,    93
 Frequency of finding value 5 in each position:
 ...
 Rejected 5706 members as incompatible with target state

This suggests to me that

there's no particular reason to favour any one of the 4 possible positions for the '1' over any other. Each has hundreds of possible magic squares that a simple heuristic suggests are compatible with the starting state.
It is thus totally unclear what "think about which location it's most likely to be in based on how magic squares are calculated" was getting at, as there's no obvious reason to prefer any of the 4 positions over the others, and with 7040 possible magic squares (including reflections and rotations), of which 5706 are trivially eliminated, and which can include every possible position on the grid of every number 4 and larger, there doesn't seem to be a lot to work on. The '2', '3', and '4' tiles all being centrally located are particularly annoying, as this minimises the portion of the grid that they cannot reach. It might be instructive to work through a few cases manually to find additional restrictions on the magic squares to reduce the residual list below 1334 possible magic squares, but I'm at a total loss as to how one could even have made a start on the originally-intended solving path.

After further consideration, it's possible to rank the magic squares

by how many half-swaps would be needed to "restore the magic" if each tile could move the minimum distance between its jumbled state and the magic square. In particular, after adding some further diagnostic output, I got the following:

At least 22 half-swaps required for
  1₁ | G₊ | B₊ | 6₆
 ----+----+----+----
  D₊ | 4₄ | 7₇ | A₊
 ----+----+----+----
  8₈ | 9₉ | E₊ | 3₃
 ----+----+----+----
  C₊ | 5₅ | 2₂ | F₊

 At least 24 half-swaps required for
  B₊ | 6₆ | 7₇ | A₊
 ----+----+----+----
  1₁ | G₊ | D₊ | 4₄
 ----+----+----+----
  E₊ | 3₃ | 2₂ | F₊
 ----+----+----+----
  8₈ | 9₉ | C₊ | 5₅

 At least 26 half-swaps required for
 [14 possible magic squares which have '1' in R1C1 or R2C1]

A better-directed (possibly manual) search might prefer those magic squares to the one given in the question, because the equivalent diagnostics for the given magic square are:

At least 48 half-swaps required for
  1₁ | F₊ | E₊ | 4₄
 ----+----+----+----
  A₊ | B₊ | 8₈ | 5₅
 ----+----+----+----
  7₇ | 6₆ | 9₉ | C₊
 ----+----+----+----
  G₊ | 2₂ | 3₃ | D₊

Which would seem to give the first stage of a proof

of impossibility of reaching that particular grid, which can continue as follows...
Each swap between tiles $k$ and $j$ where $k<j$ uses up $k+1$ "moves", and each tile $k$ can only be involved at least $k$ times.
48 half-swaps might conceivably be arranged with 24 swaps (where every swap moves both tiles towards their target position), and these might conceivably all involve the lowest numbered tiles.
so we can have 1 swap involving the '1' tile that uses up 2 moves, 2 swaps that use 3 moves, 3 swaps that use 4 moves, 4 swaps that use 5 moves, 5 swaps that use 6 moves, and 6 swaps that use 7 moves for a total of 21 swaps costing 112 moves. To get to 24 swaps, we'd need 3 more swaps involving the '7' tile, costing 8 moves each for a total of 136.
This is exactly equal to the total number of moves present on the starting grid, so in order for there to be a solution that finishes on that particular magic square, every move would need to move both tiles towards their target, with the smaller tile no larger than '7' and the larger tile no smaller than '7'.
Observing the right hand column, this is impossible, because 16, 10, 14, 15 must all swap "out" of the right hand column, but to do so must swap with a tile 7 or lower moving towards its destination to avoid breaking the budget of 136 moves. However, only two tiles lower than 7 are moving into that column, the 4 and 5.
Therefore there is no possible solution of any sequence of swaps to reach the given magic square.

Taking this specific proof into account,

the "move budget" seems likely to be a major factor in a more complete proof. The 22 or 24 half-moves for the "nearest" and "second-nearest" magic squares to the starting state certainly can't be ruled out with a similarly simple argument. The heuristic in the program assumed that a tile can be moved $n$ places using $n$ moves, which is only the case if it is the lower tile involved in the swap, or if it is swapping with the '1' (which can only occur once for any tile). In particular, the '16' tile will always be the larger tile involved in the swap, so uses up its score very quickly... indeed, an alternative proof of impossibility for the given magic square is that the '16' tile cannot reach the opposite corner, as it involves 6 swaps, and each swap costs the value of the tile it swaps with... even swapping with the lowest numbers would cost $1+2+3+4+5 = 15$ for 5 moves. Tiles of lower value can make 6 moves, but effectively "steal" part of the move budget from other tiles, as they must be the lower tile involved in at least some swaps.
For a next step, I'd probably look more closely at the two magic squares shown above, which require only 22 or 24 half-swaps. If there was yet another bug in my program, so that I was wrong about there being no solution, those would be the most likely candidates... and if it's impossible for any magic square, demonstrating why it's impossible for those specific ones which require the smallest net movement of tiles would seem likely to inform why it's impossible in the general case.

$\endgroup$
1
  • $\begingroup$ Just a quick note that I didn't start the "next step" referred to in the final spoiler block - I have many other tasks this week, so although I'll certainly revisit this problem if a full solution isn't posted in the meantime, it probably won't be for a while. $\endgroup$
    – Steve
    Oct 18 at 15:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.