[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 no-computers from this puzzle, this answer initially treats it as a computer-puzzle.
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 no-computers 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 no-computers 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.
