Timeline for Can you reactivate a 4x4 Magic Square?
Current License: CC BY-SA 4.0
18 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Oct 7, 2021 at 14:21 | comment | added | Steve | 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. | |
| Oct 7, 2021 at 6:58 | comment | added | Steve | I've now deleted an attempt at a partial answer that treated this as a computer-puzzle, as I was unable both to iron out the bugs and to have a program run to completion in a reasonable time. Will revisit later. Extrapolating from results so far, a naive computer search is likely to need to keep track of in excess of half a billion grid states, so this approach either needs good compression and a powerful computer, or better pruning of "dead" branches in the search. | |
| Oct 1, 2021 at 21:43 | answer | added | Steve | timeline score: 3 | |
| Oct 1, 2021 at 20:19 | comment | added | Taco | @Steve Lbhe pheerag nccebnpu unf lbh nyvtarq jvgu zl pbapyhfvbaf. $\leftarrow$ ROT13. | |
| Oct 1, 2021 at 13:28 | comment | added | Steve | @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). | |
| Oct 1, 2021 at 13:20 | comment | added | Taco | @Steve out of curiosity, are you building new squares with your testing, or are you focusing it on just the provided one? | |
| Oct 1, 2021 at 13:19 | comment | added | Amoz | I am curious what the no computer solution path is. I tried and failed. My feeling was that without the target square given, this is very hard. Excited to see who cracks this. | |
| Oct 1, 2021 at 11:58 | comment | added | Steve | 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. | |
| Sep 30, 2021 at 18:38 | history | edited | Taco |
edited tags
|
|
| Sep 30, 2021 at 13:28 | history | edited | Taco | CC BY-SA 4.0 |
The strategy tag should be the mathematics tag; corrected.
|
| Sep 30, 2021 at 13:20 | history | edited | Taco | CC BY-SA 4.0 |
added 1356 characters in body
|
| Sep 30, 2021 at 13:05 | comment | added | Taco | @Steve $8_3$ cannot afford to pay the extra penalty, so you cannot move at all. | |
| Sep 30, 2021 at 13:02 | comment | added | Steve | 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"? | |
| Sep 30, 2021 at 3:47 | comment | added | Taco | @DrXorile any valid magic square is acceptable, though answers that don’t use the provided square should explain why they used a different square. | |
| Sep 30, 2021 at 3:29 | comment | added | Dr Xorile | Does it have to become the magic square you showed? Or is any 4x4 magic square acceptable? | |
| Sep 30, 2021 at 3:06 | history | edited | Taco | CC BY-SA 4.0 |
edited title
|
| Sep 30, 2021 at 0:00 | history | edited | RobPratt |
edited tags
|
|
| Sep 30, 2021 at 0:00 | history | asked | Taco | CC BY-SA 4.0 |