Are there any combinations that produce identical outputs? Possibly a horizontal reflection being equivalent to a 180 degree rotation combined with a vertical reflection?
Good point! A 180 degree rotation combined with H and V mirrors appears to be the identity operation, so 880 solutions.
But the fourth rotation gives the original state, so....
There are four states (or solutions) related by 90 degree rotations, so I should have said "four rotational states".
To find the first set of 880, while excluding reflections and rotations, you'd have to do something more interesting than this code's exhaustive search.
I clearly haven't had enough coffee today. I thought the 880 permutations were unique? Are some of them duplicates of either 1 or 3 90 degree clockwise rotations or a vertical or horizontal flip?
We all seem to be in agreement about that number now.
For example, take
Solution #1 [0 sec]:
1 2 15 16
12 14 3 5
13 7 10 4
8 11 6 9
and see if you find it's mirror around the diagonal (rot 90, mirror) in the first 880 found from the exhaustive search.
...
Solution #222 [11 sec]:
1 12 13 8
2 14 7 11
15 3 10 6
16 5 4 9
You can't use the first 880 solutions generated by this code as the unique set to reflect and rotate.
My thinking is as follows:
Since we start at the upper left corner, then any solution that has a number in any other corner that is less than the number in the upper left corner would be a rotation/reflection of a previous solution.
Additionally, since we work from top to bottom, any solution where the lower left corner is lower than the upper right corner would also be a rotation of a previous solution (rotated along a diagonal from upper left to lower right).
The commented out if statements in the switch/case appear to be an attempt at something like this.
IIRC the number 1 can only be in 3 unique places { 0, 1, 5 } as all other locations are reachable with symmetry. That could reduce the search space with a factor 5.
I had to change the sense of some of the commented if statements, but that seems to work to filter out the reflections to produce 880 solutions:
/*
Magische Quadrate 4x4, rekursiv
Serial only version
*/
struct cell {
int left;
int top;
};
int w, h;
const byte cols = 4;
const byte maxi = cols * cols;
const byte sum = (maxi + 1) * maxi / 2 / cols;
byte p[maxi];
int colour[maxi + 1];
// Reihenfolge, in der die Werte gesetzt werden:
const byte seq[] = {
0, 1, 2, 3,
4, 5, 6, 7,
8, 10, 12, 13,
9, 11, 14, 15
};
/* die Positionen:
_0 _1 _2 3 alle Postionen ohne "_"
_4 _5 _6 7 koennen berechnet werden!
_8 _9 10 11
12 13 14 15
*/
cell disp[maxi];
char str[2 * maxi + 2];
int count = 0;
const byte charW = 13;
const byte charH = 13;
const byte left = 39;
const byte top = 59;
const byte p0 = 2;
const byte p1 = 102;
byte solution[maxi + 1] = {0};
void setup() {
Serial.begin(115200);
Serial.println(F(__FILE__));
// calculate the positions of the 16 cells
for (int i = 0; i < maxi; i++) {
int j = seq[i];
disp[j].left = left + 1 + (i & 3) * charW;
disp[j].top = top + 2 + (i / 4) * charH;
}
// Generate the strings to display the numbers faster
str[0] = 0xDB;
str[1] = 0xDB;
for (int i = 1; i <= maxi; i++) {
// colour[i] = hue(i);
str[i * 2] = i < 10 ? ' ' : '1';
str[i * 2 + 1] = '0' + i % 10;
dispNumAtpos(0, i);
}
// start the recursion:
place(0, 0xFFFF);
// finished and ready.
Serial.print(F("Complete ["));
Serial.print(millis() / 1000);
Serial.println(F(" sec]"));
}
void loop() {}
void place(byte pos, int avail) {
byte i;
switch (pos) {
case 0: case 1: case 2: case 4: case 5: case 6: case 8:
for (i = 1; i <= maxi; i++) Try(pos, i, avail); break;
case 3: i = rem3(0, 1, 2); if (p[0] < i)
Try(pos, i, avail); break;
// Row 1, mirrored on the vertical axis
case 7: i = rem3(4, 5, 6); Try(pos, i, avail); break; // Zeile 2
case 9: i = rem3(0, 4, 8); if ((p[0] < i) && (p[3] > i))
//if(p[3] > i)
Try(pos, i, avail); break; // Spalte 1
case 10: i = rem3(9, 6, 3); Try(pos, i, avail); break; // /-diagonal
case 11: i = rem3(1, 5, 10); Try(pos, i, avail); break; // Spalte 2
case 12: i = rem3(5, 6, 10); Try(pos, i, avail); break; // mittlerer Block
case 13: i = rem3(8, 10, 12); Try(pos, i, avail); break; // Zeile 3
case 14: i = rem3(2, 6, 12); Try(pos, i, avail); break; // Spalte 3
case 15: i = rem3(3, 7, 13); if (p[0] < i)
Try(pos, i, avail); break;
// Column 4, mirrored on the main diagonal
case 16: if (rem3(0, 5, 12) == p[15]) {
// signal the current solution
Serial.print(F("Solution #"));
Serial.print(++count);
Serial.print(F(" ["));
Serial.print(millis() / 1000);
Serial.println(F(" sec]:"));
for (size_t pr = 0; pr < maxi; pr++) {
Serial.print(str[solution[seq[pr]] * 2]);
Serial.print(str[solution[seq[pr]] * 2 + 1]);
Serial.print(' ');
if (((pr + 1) % cols) == 0) {
Serial.println();
}
}
Serial.println();
}
}
}
void Try(byte pos, byte value, int avail) {
if ((value < 1) || (value > maxi)) return; // ungueltige Zahl
int mask = 1 << (value - 1);
if (avail & mask) {
p[pos] = value;
dispNumAtpos(value, pos);
place(pos + 1, avail & ~mask);
dispNumAtpos(0, pos); // loesche Zelle
p[pos] = 0;
}
}
byte rem3(byte a, byte b, byte c) { // gib den Rest zurueck
return sum - p[a] - p[b] - p[c];
}
void dispNumAtpos(byte number, byte position) {
solution[position] = number;
}
On an Uno R3:
...
Solution #879 [115 sec]:
7 16 1 10
4 13 12 5
14 3 6 11
9 2 15 8
Solution #880 [115 sec]:
7 16 1 10
12 5 4 13
6 11 14 3
9 2 15 8
Complete [150 sec]:
It feels a bit wrong to filter out the exhaustive search and then plan to reflect/rotate the 880 that pass.
Indeed, and a surprise to me. So what exactly is this set of 880? Apart from the source that prompted this thread, I had the impression I’d seen it quite frequently described in ways that implied they were unique permutations.
BTW, how did you find that pair for your QED example?
I would not think that would be a surprise. The code generates all 7040 solutions, with 880 unique arrangements of numbers, the other 6160 being the same arrangement but rotated/mirrored in some combination. There is no reason to believe that the code would generate all the unique combinations first.
My interest in code that generates only the 880 unique solutions was to see if it would speed up the code by reducing the number of calculations. Once you have the unique solutions, the rotation/mirroring can be done by having eight versions of the seq array that represent all the possible rearrangements.
That would be quite easy. Once the code has finished, copy the contents of the serial monitor to a text file, then take the first number of each row (1, 12, 13, and 8 in the example) and search for any occurrence of those numbers in a horizontal row (" 1 12 13 8"). Since the code starts with 1 in the upper left, all answers with a 1 in that position will be generated before advancing to 2 or any high number, making it unlikely the matching solution will be very far away.
Yes. Since the code generates solutions in numerically sorted order, there's no reason to believe that none of the reflections could come early.
Yep. That's it exactly.
xactly.
You're right, as far as I know it was demonstrated in the 17th century by the French mathematician "de Bess" that the total number of unique magic squares is 880.
Anyway, an Arduino code to solve this puzzle is an interesting thing for me, thanks!
PS: I am a math enthusiast, and I manage a FB page dedicated to science, logic and mathematics where I have fun with problems and quizzes.
@david_2018
Sorry if I'm making heavy weather of this, but I'm still confused. In post #25 DaveX said "To find the first set of 880, while excluding reflections and rotations, you'd have to do something more interesting than this code's exhaustive search."
By 'this code'? I assumed he meant jremington's serial-only version? Implying that those 880 were not unique. And in post #28 he seemed to reinforce that with "You can't use the first 880 solutions generated by this code as the unique set to reflect and rotate."
So, are the 880 unique or not? By 'unique' I mean not one of the 6,160 others obtained by up to three rotations or vertical or horizontal mirroring.
I had assumed until post #25 that they were unique. Hence my post #26 and the surprise I expressed in #28.
There is some confusion over what is meant by "this code".
The first 880 solutions generated by the brute force approach posted in my "serial only" version are not all unique, as some are related to others by symmetry.
I presume (but have not tested) that the 880 generated by the code posted in reply #31 by DaveX are unique, and that the remaining 6160 can be generated from those.
Just to add my five cents and then I'll stop: download this paper I found, titled "Franklin Squares - a Chapter in the Scientific Studies of Magical Squares", where this topic is included (see chapter 6):
Hope it can be of some interest. Cheers!
@anon94801460's serial only code is a faithful version of the hackster code and produces the 7040 solutions including the rotations and reflections of the 880 'unique' solutions:
I meant that if you had a method to generate set of 880 unique solutions as mentioned in #1, and then applied the rotations and reflections to get the 7040 as per #13, it could be quicker than exhaustively searching the solution space, discarding the reflections and rotations to get to the unique 880, (as in the #31 code) and then applying the rotations and reflections to the 880.
There might be some math-graph-theory way of generating the 880 solutions as some permutation of operations on groups or some such magic, but the exhaustive search (with filter) is not that solution.
I have not tested them either, but after I un-commented the comments in the original, and adjusted the senses of the if statements to match @david_2018's #22 comments, It spat out the expected 880 solutions.
Double checking it's output for rotations and reflections would take more coding than would fit into the Uno.
EDIT: Posted before seeing your similar.
![]()
Interesting, thanks, prompted further browsing. On
this page
I read
In fact, this is the complete list of magic squares of order 4 but Frénicle's papers do not prove this.
Further browsing took me to
this stackexchange page
where those whose maths skills have faded much less than mine over the decades can find an apparent proof.