Skip to main content
Puzzling

You are not logged in. Your edit will be placed in a queue until it is peer reviewed.

We welcome edits that make the post easier to understand and more valuable for readers. Because community members review edits, please try to make the post substantially better than how you found it, for example, by fixing grammar or adding additional resources and hyperlinks.

11
  • 2
    $\begingroup$ Does it have to become the magic square you showed? Or is any 4x4 magic square acceptable? $\endgroup$
    – Dr Xorile
    Commented Sep 30, 2021 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
    Commented Sep 30, 2021 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
    Commented Oct 1, 2021 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
    Commented Oct 1, 2021 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
    Commented Oct 7, 2021 at 14:21