# Differences

This shows you the differences between two versions of the page.

 fuss:puzzles [2014/01/15 20:02]127.0.0.1 external edit fuss:puzzles [2017/02/22 18:30] (current) 2014/07/16 19:06 office [de la Loubère's Algorithm] 2014/01/15 20:02 external edit Next revision Previous revision 2014/07/16 19:06 office [de la Loubère's Algorithm] 2014/01/15 20:02 external edit Line 1: Line 1: + ====== Magic Square Generation ====== + A magic square is an arrangement of numbers in a square grid, where the numbers in each row, column, and the numbers on the big diagonals, all add up to the same number. We can determine that number. Suppose $M$ is the number that each row, column or big diagonal must add up to. Since there are $n$ rows, the sum of all the numbers in the magic square must be $n*M$. Now, the numbers being added give the series $1,​2,​3,​..,​n^{2}$,​ thus: + + $$+ \sum_{i=1}^{n^{2}}{i}=n*M +$$ + + Knowing that: + + $$+ 1+2+3+...+n^{2}=\frac{n^2(n^2+1)}{2} +$$ + + then it follows that: + + $$+ n*M=\frac{n^{2}(n^{2}+1)}{2} +$$ + + reducing, we obtain: + + $$+ M=\frac{n(n^{2}+1)}{2} +$$ + + Thus, for a $3 \times 3$ magic square, M=$15$, for a $4 \times 4$ magic square $M=34$, for a $5 \times 5$ magic square $M=65$, etc... + + ===== de la Loubère'​s Algorithm ===== + + - Start in the middle column and place the number $x=1$. + - Go up and right and place $x+1$. + - If you exceed the square bounds, wrap around and place $x+1$. + - If you meet an occupied square, move down and place $x+1$. + - Repeat at ''​1''​ until all numbers are placed. + + {{puzzles_magicsquareupright.gif}} + + ==== Generalizing Loubère Algorithm ==== + + The same concept applies, for all $90^\circ$ counter-clockwise rotations of the movement direction, going back each time a square is occupied. + + {{puzzles_generalizedloubere.png}} + + Every movement sequence will yield a magic square, all the columns, lines and big diagonals adding up to $15$. The squares generated by all four sequences are: + + + \begin{align} + MS_{1} = + \begin{pmatrix} ​ + 8 & 1 & 6 \\ + 3 & 5 & 7 \\ + 4 & 9 & 2 \\ + \end{pmatrix} + & + MS_{2} = + \begin{pmatrix} ​ + 6 & 7 & 2 \\ + 1 & 5 & 9 \\ + 8 & 3 & 4 \\ + \end{pmatrix} + & + MS_{3} = + \begin{pmatrix} ​ + 2 & 9 & 4 \\ + 7 & 5 & 3 \\ + 6 & 1 & 8 \\ + \end{pmatrix} + & + MS_{4} = + \begin{pmatrix} ​ + 4 & 3 & 8 \\ + 9 & 5 & 1 \\ + 2 & 7 & 6 \\ + \end{pmatrix} + \end{align} + + + The same applies to any odd square (with a central tile), although not all movements will necessarily build a magic square. + + {{puzzles_loubereodd.png}} + + In this case, two of the paths do not generate magic squares. All the rest though do generate magic squares. The results in a $5 \times 5$ case are the following squares: + + \begin{align} + \color{green} { + MS_{1} = + \begin{pmatrix} ​ + 17 & 24 & 1 & 8 & 15 \\ + 23 & 5 & 7 & 14 & 16 \\ + 4 & 6 & 13 & 20 & 22 \\ + 10 & 12 & 19 & 21 & 3 \\ + 11 & 18 & 25 & 2 & 9 + \end{pmatrix} + } + & + \color{green} { + MS_{2} = + \begin{pmatrix} ​ + 11 & 18 & 25 & 2 & 9 \\ + 17 & 24 & 1 & 8 & 15 \\ + 23 & 5 & 7 & 14 & 16 \\ + 4 & 6 & 13 & 20 & 22 \\ + 10 & 12 & 19 & 21 & 3 + \end{pmatrix} + } + & + \color{green} { + MS_{3} = + \begin{pmatrix} ​ + 15 & 9 & 3 & 22 & 16 \\ + 8 & 2 & 21 & 20 & 14 \\ + 1 & 25 & 19 & 13 & 7 \\ + 24 & 18 & 12 & 6 & 5 \\ + 17 & 11 & 10 & 4 & 23 + \end{pmatrix} + } + \end{align} + + + + \begin{align} + \color{green} { + MS_{4} = + \begin{pmatrix} ​ + 16 & 15 & 9 & 3 & 22 \\ + 14 & 8 & 2 & 21 & 20 \\ + 7 & 1 & 25 & 19 & 13 \\ + 5 & 24 & 18 & 12 & 6 \\ + 23 & 17 & 11 & 10 & 4 + \end{pmatrix} + } + & + \color{green} { + MS_{5} = + \begin{pmatrix} ​ + 9 & 2 & 25 & 18 & 11 \\ + 3 & 21 & 19 & 12 & 10 \\ + 22 & 20 & 13 & 6 & 4 \\ + 16 & 14 & 7 & 5 & 23 \\ + 15 & 8 & 1 & 24 & 17 + \end{pmatrix} + } + & + \color{red} { + MS_{6} = + \begin{pmatrix} ​ + 3 & 21 & 19 & 12 & 10 \\ + 22 & 20 & 13 & 6 & 4 \\ + 16 & 14 & 7 & 5 & 23 \\ + 15 & 18 & 1 & 24 & 17 \\ + 9 & 2 & 25 & 18 & 11 + \end{pmatrix} + } + \end{align} + + + + \begin{align} + \color{green} { + MS_{7} = + \begin{pmatrix} ​ + 11 & 10 & 4 & 23 & 17 \\ + 18 & 12 & 6 & 5 & 24 \\ + 25 & 19 & 13 & 7 & 1 \\ + 2 & 21 & 20 & 14 & 8 \\ + 9 & 3 & 22 & 16 & 15 + \end{pmatrix} + } + & + \color{red} { + MS_{8} = + \begin{pmatrix} ​ + 10 & 4 & 23 & 17 & 11 \\ + 12 & 6 & 5 & 24 & 18 \\ + 19 & 13 & 7 & 1 & 25 \\ + 21 & 20 & 14 & 8 & 2 \\ + 3 & 22 & 16 & 15 & 9 + \end{pmatrix} + } + \end{align} + + + where the green squares are magic squares all the lines, columns and big diagonals adding up to $65$ while the red squares are not magic squares.