12
$\begingroup$

A 3x3 magic square is a 3x3 grid containing the numbers 1-9 once each, and in which every row, column, and diagonal sums to 15:

294
753
618

And I presume we all know the rules to Sudoku.

Consider the following completed Sudoku puzzle:

+---+---+---+
|294|516|738|
|753|842|196|
|618|379|254|
+---+---+---+
|571|468|329|
|936|125|847|
|482|793|561|
+---+---+---+
|345|981|672|
|827|634|915|
|169|257|483|
+---+---+---+

Notice that the top-left 3x3 portion of the Sudoku solution is a magic square! Likewise, consider this Sudoku solution:

+---+---+---+
|829|475|613|
|475|361|289|
|361|829|574|
+---+---+---+
|197|583|426|
|643|912|758|
|258|647|931|
+---+---+---+
|782|194|365|
|514|736|892|
|936|258|147|
+---+---+---+

This solution also has a magic square in the top-left corner. However, notice that it isn't perfectly aligned with one of the nine 3x3 squares that are considered when solving Sudoku. Instead, it's a column to the right of the edge.

Finally, consider this Sudoku solution:

+---+---+---+
|294|187|365|
|753|269|814|
|618|345|279|
+---+---+---+
|821|594|736|
|536|728|941|
|947|613|582|
+---+---+---+
|165|872|493|
|482|936|157|
|379|451|628|
+---+---+---+

This one has two overlapping magic squares. The first one is in the top-right corner, like in the first Sudoku example. The second magic square shares the 8 in the bottom-right corner of the first magic square, but the rest of its numbers are below and to the right of the first magic square.

Counting all magic squares that show up in a Sudoku solution, including ones that have overlapping numbers and that don't align with the 3x3 squares that are checked in a Sudoku puzzle, what is the maximum number of magic squares that can be present in a single Sudoku solution?

$\endgroup$
  • 4
    $\begingroup$ I know you can get at least five, but I'm struggling to prove that's a hard maximum. You definitely can't get more than 7, since at least two 5s must lay on the edges. $\endgroup$ – Set Big O Dec 16 '14 at 14:29
  • 1
    $\begingroup$ Furthermore, in a Sudoku X grid (where each of the two diagonal lines must also follow the 1-9 rule) it is impossible to get any more than 6 squares, as there must be at least 3 edge 5s $\endgroup$ – For I In Range Dec 16 '14 at 15:57
  • $\begingroup$ @Geobits If you haven't made any more progress on your solution, can you please post what work you've done so far as an answer? It will probably help other people trying to find a solution. $\endgroup$ – Kevin Dec 19 '14 at 1:41
  • 1
    $\begingroup$ There's only one 3x3 magic square, which has a symmetry group of order 8. If there are 7 magic squares in a Sudoku, two of the 5s must be in opposite corners, and there are 576 ways of positioning the others (reducible by taking into account symmetries). Thus an exhaustive check needs to attempt to solve at most $576 \times 8^7$ positions; some of them can probably be eliminated straight away for having overlapping magic squares which don't match up. $\endgroup$ – Peter Taylor Dec 20 '14 at 14:33
  • 1
    $\begingroup$ @Geobits, I've proven that 5 is the upper bound. Add your proof that it's the lower bound and we're done. $\endgroup$ – Peter Taylor Dec 20 '14 at 18:13
9
$\begingroup$

This is a two-part answer. First, it establishes a non-trivial upper bound of 5. Then a solution is given that proves 5 is also the lower bound.

There is only one 3x3 magic square, up to symmetry:

294
753
618

So in order to have seven magic squares in a Sudoku, we require seven 5s which aren't against an edge, and that requires two diagonally opposite corners to be 5s. If we then look at parity (e for even, o for odd):

eoe
o5o
eoe

and consider the possible positions of the other 5s, we eliminate almost all positions. E.g. consider the following grid:

5.. eoe ...
... o5o ...
... eoe ...

... ... ...
... ... ...
... ... ...

... ... ...
... ... ...
... ... ..5

By Sudoku rules there are two possible places for the 5 in the top-right block, but the parity matching prohibits the 5s from the magic squares being horizontally or vertically adjacent to an even number, so there's only one possible place:

5.. eoe ...
... o5o eoe
... eoe o5o

... ... eoe
... ... ...
... ... ...

... ... ...
... ... ...
... ... ..5

The 5 in the right-centre block is similarly forced; then the one in the centre block;

5.. eoe ...    5.. eoe ...
... o5o eoe    ... o5o eoe
... eoe o5o    ... eoe o5o

... ... eoe    ..e oe. eoe
... ..e oe.    ..o 5oe oe.
... ..o 5o.    ..e oeo 5o.

... ..e oe.    ... ..e oe.
... ... ...    ... ... ...
... ... ..5    ... ... ..5

and we can't place any 5 in the left-centre block.

With the aid of a computer to check the 576 cases, this simple parity matching eliminates all but one of them:

5.e oe. ...
..o 5oe oe.
eoe oeo 5o.

o5o eoe oe.
eoe o5o eoe
.eo eoe o5o

.o5 oeo eoe
.eo eo5 o..
... .eo e.5

If we zoom in on the top-left 3 blocks:

5.e oe.
..o 5o.
eoE oe.

o5o
eoe
...

the two magic squares overlap on one even numbered cell, which I've labelled E. Without loss of generality, let E = 2. Then the numbers which are two cells up, down, left, and right of E are suitably paired up 4s and 6s. But either we have two 4s in the same row as E, or we have two 4s in the same column as E, or we have two 4s or two 6s in the same block as E. So the only grid which meets the parity constraints for seven magic squares fails as soon as we try to go beyond parity.

If we look for solutions with 6 magic squares we keep one 5 in a corner and allow the others to vary. There are 29 positions of 5s which satisfy the parity check, and they all fail to the same kind of blockage between overlapping magic squares. So the upper bound for a solution is 5.


Solution with five magic squares (contributed by Geobits):

5-magic-sudoku

I found a template for this at http://www.sachsentext.de. Filling it in was a pain, but it's much easier once you realize that rotating/reflecting any of the magic squares causes it to break. Then you just have to fill in the "non-magic" spaces, which isn't much different than a regular sudoku board with a ton of givens.


(Peter resumes) Knuth's reduction of Sudoku to exact set cover can be augmented to add the magic square constraint. The reduction for standard Sudoku is to associate each $(\textrm{row}, \textrm{column}, \textrm{value})$ tuple with the set $\{\textrm{Row}(\textrm{row}, \textrm{value}), \textrm{Col}(\textrm{column}, \textrm{value}), \textrm{Block}(\lfloor\frac{\textrm{row}}3\rfloor, \lfloor\frac{\textrm{column}}3\rfloor, \textrm{value}), \textrm{Cell}(\textrm{row}, \textrm{column})\}$. Then an exact set cover of the union of all those sets provides exactly one instance of each value in each row, column, and block, and exactly one value per cell.

To extend for a magic square centred on $(r, c)$ we add a constraint for each of the four edges of the magic square that it must be one of the four sets $\{2,9,4\}, \{2,6,7\}, \{4,3,8\}, \{6,1,8\}$. This is sort-of related to the general lock puzzle: we can solve it with four "locks" and the following assignments:

2: A
4:  B
6:   C
8:    D
1: AB
3: A C
7:  B D
9:   CD

This isn't quite strong enough to avoid false positives, but it narrows down the field considerably. With these extra constraints, and iterating over the possible positions of "internal" fives, I find 64 grids. Interestingly, some include "internal" fives which aren't from magic squares: e.g.

843 127 695
276 895 143
951 643 827
        v
438 276 519
627 951 384
195 438 276
  ^
382 764 951
769 512 438
514 389 762

All of the ones I've checked have the same (IMO) structural defect that the magic squares are all in the same orientation. I haven't checked, but I think they may also all have a symmetry under rotation by 180 degrees and permutation of digits by $(19)(28)(37)(46)$.

$\endgroup$
  • $\begingroup$ Five magic square solution added, per request :D $\endgroup$ – Set Big O Dec 22 '14 at 0:21
  • $\begingroup$ Well done, Peter Taylor and Geobits! This is an impressive answer. $\endgroup$ – Kevin Dec 22 '14 at 6:02
-3
$\begingroup$

Make every square in one column contain the same. You can get another 4 squares from each then. This is 12 + 9 = 21 then. Same with rows → 33

$\endgroup$
  • 2
    $\begingroup$ I'm not sure whether this was posted in reply to the wrong question. I can't find any interpretation of the first sentence which is consistent with the rules of Sudoku, and the numbers don't make any sense as an answer to this question because, as pointed out in comments, it's certainly no larger than 7. $\endgroup$ – Peter Taylor Dec 20 '14 at 13:03
  • 3
    $\begingroup$ I think you're saying that if all 81 spaces in the Sudoku grid are filled with the same number, then there are 33 3x3 magic squares. However, doing so breaks the rules o of Sudoku. In addition, I specifically wrote in the question that I only consider magic squares that contain every number 1-9 once, which is more strict than any square where all the rows, columns and diagonals have the same sum but can have any numbers. $\endgroup$ – Kevin Dec 20 '14 at 15:29

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.