Skip to main content
gamedev.net
🔒 Locked

Magic Squares

Started by nick_wilko 13 replies 900+ views
Original Post
nick_wilko
nick_wilko
Hey, everyone loves those magic square puzzles right? You know the ones where all of the rows, columns and diagonals have to add up to the same number. e.g. 4 9 2 3 5 7 all the rows columns and diagonals = 15 8 1 6 Well, does anyone have an idea about how to write a program(c++) that can solve one of these? The square must be at least 3x3 and has no upper limit in its possible size. And there can be any number of missing values up to the extreme case where you only know one of the diagonals. e.g. 3 ? ? ? ? 11 ? ? ? ? 9 ? ? ? ? 13 I''m just looking for starting points because the only thing i''ve come up with is using matrices and that becomes a pain when considering multiple solutions and the diagonals.
vanillacoke
vanillacoke
Mathworld has an entry on this, and there''s a ridiculously simple way to solve arbitrary magic squares. Start with 1, and pick a random square. Then put 2 in the square to the top-right of that one. Then 3, then 4, et cetera. The square is topologically a torus, so if you hit the right edge, go to the left edge, if you hit the top, go to the bottom. If the next top-right square is filled, go down instead of up-right, then continue going up-right. Then you got yourself a solved magic square. Don''t ask me why it works, because I have no clue.
You know what I never noticed before?
nick_wilko
nick_wilko
Thanks, i''ll have a look at that. And I can''t believe i didn''t think of using the linear combinations. Thanks heaps!
GaulerTheGoat
GaulerTheGoat
quote:
Original post by vanillacoke
Mathworld has an entry on this, and there''s a ridiculously simple way to solve arbitrary magic squares. Start with 1, and pick a random square. Then put 2 in the square to the top-right of that one. Then 3, then 4, et cetera. The square is topologically a torus, so if you hit the right edge, go to the left edge, if you hit the top, go to the bottom. If the next top-right square is filled, go down instead of up-right, then continue going up-right. Then you got yourself a solved magic square. Don''t ask me why it works, because I have no clue.

Be careful, this only works on odd-number-sided squares. There is a way to do even-sided squares, too. I will have to look it up when I get home and will post it if nobody else already has. Sorry, I assumed you already knew about this trick .



no wise fish would go anywhere without a porpoise - The Mock Turtle
GaulerTheGoat
GaulerTheGoat
Alright, I''m back home now and I''ve found the book I''m looking for. Unfortunately I have to correct vanillacoke again because even for odd-squares, the method works but you cannot start by putting 1 in any random position. I mean, if you put 1 in the bottom left position and use this method, then the bottom left - top right diagonal will add up to 1 + 2 + 3 = 6. You need to start by putting the 1 on an edge and then the method will work.

Although, I haven''t proven this yet (to spare my ego, I haven''t actually tried yet,) I suspect that the middle position of an odd-square must be the mean of the smallest and largest numbers in the square (remember the square doesn''t have to start with 1.) Therefore, certain initial positions would be unsolvable. It would be very interesting to have some verified necessary conditions for a solution if anybody knows them.

It is easiest to describe the solving of a 4-square with an algorithm: 

int square [4][4];

for (int i = 0; i < 4; ++i) {
  for (int j = 0; j < 4; ++j) {
    if (i == j || i + j == 3)
      square [j] = 16 - 4 * i - j;
    else
      square [i][j] = 4 * i + j + 1;
  }
}

I admit this is very unenlightening... but the source I am looking at - Mathemagic by Royal Vale Heath, Dover - is using lots of pictures and I cannot draw too well. I will hopefully find some conditions for a solution and report back later.

no wise fish would go anywhere without a porpoise - The Mock Turtle
malpass
malpass
that will create a 4x4 but not solve 1, or a 3x3. Its cool though, i''m just gonna try n make a proggy that u''l solve any
malpass
malpass
nearly done, I am right in assuming u must have 1 from each row & colomn, IE

1 x x
x 2 x
x x 3

or
1 x x
x x 2
x 3 x

etc..

as a minimun input right? It isn''t possible to solve it without it is it, well, i suppose if there were less u could simple make it with serveral combos
nick_wilko
nick_wilko
Yeah, thats right. The minimum input is say one of the diagonals like you said.
But a few of the replys have been simply dealing with the normal magic squares where the numbers in the square range from 1 to n^2 for an nxn square. I didnt set that as a condition in the first post. My question is refering to a magic square which can have any positive integers in it, with at least one from each row and column being known. And the program only needs to find one solution.
Conner McCloud
Conner McCloud
If there are no limitations on what values can be in each square, then you could probably brute-force it pretty easily. Just pick some random numbers to complete your first row (or use the one that''s given), and then force the rest of the rows to sum to the same value. There are probably some limitations on how you chose those initial guesses, but my gut says it''ll work OK.

CM
Eelco
Eelco
yeah those funky brain/body scans also make use of this, and i could never figure out how. really annoying.
i assume they make a scan all around a certain part, creating a one dimensional array containing the opacity for each beam, for a given amount of steps around the bodypart. and then they somehow create a 2dimensional image from that, it really puzzles me. anyone knows how to go about that?
GaulerTheGoat
GaulerTheGoat
I''m not trying to write code that will solve a square given a partially filled in one, but if you want a function that will create any odd-square or any multiple-of-4-square, here they are.

#include <stdlib.h>

void OddMagicSquare (int *square, int n, int start, int jump)
{ /*  This makes a magic square of odd side n */
  int i = 0,
      j = n/2,
      shift = 0,
      val = start,
      end = start + n*n;
  while (val < end) {
    *(square + i*(n + jump) + j) = val;
    ++ val;
    ++ shift;
    if (shift % n != 0) {
      i = (i == 0 ? n - 1 : i - 1);
      j = (j == n-1 ? 0 : j + 1);
    }
    else
      i = (i == n - 1 ? 0 : i + 1);
  }
}

void FourMagicSquare (int *square, int n)
{ /*  This makes a magic square of multiple of 4 side n */
  int i, j,
      max = n*n;
  for (i = 0; i < n; ++ i)
    for (j = 0; j < n; ++ j)
      if (abs (i - j) % 4 == 0 || (i + j + 1) % 4 == 0)
        *(square + i*n + j) = max - i*n - j;
      else
        *(square + i*n + j) = i*n + j + 1;
}


The first function has a start and jump parameter because I was trying to use it to make other squares. Just set start to 1 and jump to 0. I wrote a function which makes a 6-square by juxtaposition of 4 3-squares and then swapping some of the positions. I saw this method in a book. Upon investagting it, I managed to prove that this method is a special case of the number 3 and cannot be generalized to larger squares. At this point, I''m not sure if a non-odd-or-multiple-of-4-square bigger than 6 exists. Has anybody seen one? Please post a link if you have one. I''ll go search google in a second. Just for fun, here is an output of my program for squares 0-20 (1 and 2 were a fluke) which says whether the square is magic.

  
MAGIC

MAGIC
    1

NOT MAGIC
    4    3
    1    2

MAGIC
    8    1    6
    3    5    7
    4    9    2

MAGIC
   16    2    3   13
    5   11   10    8
    9    7    6   12
    4   14   15    1

MAGIC
   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

MAGIC
   35    1    6   26   19   24
    3   32    7   21   23   25
   31    9    2   22   27   20
    8   28   33   17   10   15
   30    5   34   12   14   16
    4   36   29   13   18   11

MAGIC
   30   39   48    1   10   19   28
   38   47    7    9   18   27   29
   46    6    8   17   26   35   37
    5   14   16   25   34   36   45
   13   15   24   33   42   44    4
   21   23   32   41   43    3   12
   22   31   40   49    2   11   20

MAGIC
   64    2    3   61   60    6    7   57
    9   55   54   12   13   51   50   16
   17   47   46   20   21   43   42   24
   40   26   27   37   36   30   31   33
   32   34   35   29   28   38   39   25
   41   23   22   44   45   19   18   48
   49   15   14   52   53   11   10   56
    8   58   59    5    4   62   63    1

MAGIC
   47   58   69   80    1   12   23   34   45
   57   68   79    9   11   22   33   44   46
   67   78    8   10   21   32   43   54   56
   77    7   18   20   31   42   53   55   66
    6   17   19   30   41   52   63   65   76
   16   27   29   40   51   62   64   75    5
   26   28   39   50   61   72   74    4   15
   36   38   49   60   71   73    3   14   25
   37   48   59   70   81    2   13   24   35

NOT MAGIC
   92   24    1    8   15   67   74   51   58   65
   23   80    7   14   16   73   55   57   64   66
    4    6   88   20   22   54   56   63   70   72
   10   87   19   21    3   60   62   69   71   53
   86   18   25    2    9   61   68   75   52   59
   17   99   76   83   90   42   49   26   33   40
   98    5   82   89   91   48   30   32   39   41
   79   81   13   95   97   29   31   38   45   47
   85   12   94   96   78   35   37   44   46   28
   11   93  100   77   84   36   43   50   27   34

MAGIC
   68   81   94  107  120    1   14   27   40   53   66
   80   93  106  119   11   13   26   39   52   65   67
   92  105  118   10   12   25   38   51   64   77   79
  104  117    9   22   24   37   50   63   76   78   91
  116    8   21   23   36   49   62   75   88   90  103
    7   20   33   35   48   61   74   87   89  102  115
   19   32   34   47   60   73   86   99  101  114    6
   31   44   46   59   72   85   98  100  113    5   18
   43   45   58   71   84   97  110  112    4   17   30
   55   57   70   83   96  109  111    3   16   29   42
   56   69   82   95  108  121    2   15   28   41   54

MAGIC
  144    2    3  141  140    6    7  137  136   10   11  133
   13  131  130   16   17  127  126   20   21  123  122   24
   25  119  118   28   29  115  114   32   33  111  110   36
  108   38   39  105  104   42   43  101  100   46   47   97
   96   50   51   93   92   54   55   89   88   58   59   85
   61   83   82   64   65   79   78   68   69   75   74   72
   73   71   70   76   77   67   66   80   81   63   62   84
   60   86   87   57   56   90   91   53   52   94   95   49
   48   98   99   45   44  102  103   41   40  106  107   37
  109   35   34  112  113   31   30  116  117   27   26  120
  121   23   22  124  125   19   18  128  129   15   14  132
   12  134  135    9    8  138  139    5    4  142  143    1

MAGIC
   93  108  123  138  153  168    1   16   31   46   61   76   91
  107  122  137  152  167   13   15   30   45   60   75   90   92
  121  136  151  166   12   14   29   44   59   74   89  104  106
  135  150  165   11   26   28   43   58   73   88  103  105  120
  149  164   10   25   27   42   57   72   87  102  117  119  134
  163    9   24   39   41   56   71   86  101  116  118  133  148
    8   23   38   40   55   70   85  100  115  130  132  147  162
   22   37   52   54   69   84   99  114  129  131  146  161    7
   36   51   53   68   83   98  113  128  143  145  160    6   21
   50   65   67   82   97  112  127  142  144  159    5   20   35
   64   66   81   96  111  126  141  156  158    4   19   34   49
   78   80   95  110  125  140  155  157    3   18   33   48   63
   79   94  109  124  139  154  169    2   17   32   47   62   77

NOT MAGIC
  177   39   48    1   10   19   28  128  137  146   99  108  117  126
   38  194    7    9   18   27   29  136  145  105  107  116  125  127
   46    6  155   17   26   35   37  144  104  106  115  124  133  135
    5   14   16  172   34   36   45  103  112  114  123  132  134  143
   13   15  171   33   42   44    4  111  113  122  131  140  142  102
   21  170   32   41   43    3   12  119  121  130  139  141  101  110
  169   31   40   49    2   11   20  120  129  138  147  100  109  118
   30  186  195  148  157  166  175   79   88   97   50   59   68   77
  185   47  154  156  165  174  176   87   96   56   58   67   76   78
  193  153    8  164  173  182  184   95   55   57   66   75   84   86
  152  161  163   25  181  183  192   54   63   65   74   83   85   94
  160  162   24  180  189  191  151   62   64   73   82   91   93   53
  168   23  179  188  190  150  159   70   72   81   90   92   52   61
   22  178  187  196  149  158  167   71   80   89   98   51   60   69

MAGIC
  122  139  156  173  190  207  224    1   18   35   52   69   86  103  120
  138  155  172  189  206  223   15   17   34   51   68   85  102  119  121
  154  171  188  205  222   14   16   33   50   67   84  101  118  135  137
  170  187  204  221   13   30   32   49   66   83  100  117  134  136  153
  186  203  220   12   29   31   48   65   82   99  116  133  150  152  169
  202  219   11   28   45   47   64   81   98  115  132  149  151  168  185
  218   10   27   44   46   63   80   97  114  131  148  165  167  184  201
    9   26   43   60   62   79   96  113  130  147  164  166  183  200  217
   25   42   59   61   78   95  112  129  146  163  180  182  199  216    8
   41   58   75   77   94  111  128  145  162  179  181  198  215    7   24
   57   74   76   93  110  127  144  161  178  195  197  214    6   23   40
   73   90   92  109  126  143  160  177  194  196  213    5   22   39   56
   89   91  108  125  142  159  176  193  210  212    4   21   38   55   72
  105  107  124  141  158  175  192  209  211    3   20   37   54   71   88
  106  123  140  157  174  191  208  225    2   19   36   53   70   87  104

MAGIC
  256    2    3  253  252    6    7  249  248   10   11  245  244   14   15  241
   17  239  238   20   21  235  234   24   25  231  230   28   29  227  226   32
   33  223  222   36   37  219  218   40   41  215  214   44   45  211  210   48
  208   50   51  205  204   54   55  201  200   58   59  197  196   62   63  193
  192   66   67  189  188   70   71  185  184   74   75  181  180   78   79  177
   81  175  174   84   85  171  170   88   89  167  166   92   93  163  162   96
   97  159  158  100  101  155  154  104  105  151  150  108  109  147  146  112
  144  114  115  141  140  118  119  137  136  122  123  133  132  126  127  129
  128  130  131  125  124  134  135  121  120  138  139  117  116  142  143  113
  145  111  110  148  149  107  106  152  153  103  102  156  157   99   98  160
  161   95   94  164  165   91   90  168  169   87   86  172  173   83   82  176
   80  178  179   77   76  182  183   73   72  186  187   69   68  190  191   65
   64  194  195   61   60  198  199   57   56  202  203   53   52  206  207   49
  209   47   46  212  213   43   42  216  217   39   38  220  221   35   34  224
  225   31   30  228  229   27   26  232  233   23   22  236  237   19   18  240
   16  242  243   13   12  246  247    9    8  250  251    5    4  254  255    1

MAGIC
  155  174  193  212  231  250  269  288    1   20   39   58   77   96  115  134  153
  173  192  211  230  249  268  287   17   19   38   57   76   95  114  133  152  154
  191  210  229  248  267  286   16   18   37   56   75   94  113  132  151  170  172
  209  228  247  266  285   15   34   36   55   74   93  112  131  150  169  171  190
  227  246  265  284   14   33   35   54   73   92  111  130  149  168  187  189  208
  245  264  283   13   32   51   53   72   91  110  129  148  167  186  188  207  226
  263  282   12   31   50   52   71   90  109  128  147  166  185  204  206  225  244
  281   11   30   49   68   70   89  108  127  146  165  184  203  205  224  243  262
   10   29   48   67   69   88  107  126  145  164  183  202  221  223  242  261  280
   28   47   66   85   87  106  125  144  163  182  201  220  222  241  260  279    9
   46   65   84   86  105  124  143  162  181  200  219  238  240  259  278    8   27
   64   83  102  104  123  142  161  180  199  218  237  239  258  277    7   26   45
   82  101  103  122  141  160  179  198  217  236  255  257  276    6   25   44   63
  100  119  121  140  159  178  197  216  235  254  256  275    5   24   43   62   81
  118  120  139  158  177  196  215  234  253  272  274    4   23   42   61   80   99
  136  138  157  176  195  214  233  252  271  273    3   22   41   60   79   98  117
  137  156  175  194  213  232  251  270  289    2   21   40   59   78   97  116  135

NOT MAGIC
  290   58   69   80    1   12   23   34   45  209  220  231  242  163  174  185  196  207
   57  311   79    9   11   22   33   44   46  219  230  241  171  173  184  195  206  208
   67   78  251   10   21   32   43   54   56  229  240  170  172  183  194  205  216  218
   77    7   18  263   31   42   53   55   66  239  169  180  182  193  204  215  217  228
    6   17   19   30  284   52   63   65   76  168  179  181  192  203  214  225  227  238
   16   27   29  283   51   62   64   75    5  178  189  191  202  213  224  226  237  167
   26   28  282   50   61   72   74    4   15  188  190  201  212  223  234  236  166  177
   36  281   49   60   71   73    3   14   25  198  200  211  222  233  235  165  176  187
  280   48   59   70   81    2   13   24   35  199  210  221  232  243  164  175  186  197
   47  301  312  323  244  255  266  277  288  128  139  150  161   82   93  104  115  126
  300   68  322  252  254  265  276  287  289  138  149  160   90   92  103  114  125  127
  310  321    8  253  264  275  286  297  299  148  159   89   91  102  113  124  135  137
  320  250  261   20  274  285  296  298  309  158   88   99  101  112  123  134  136  147
  249  260  262  273   41  295  306  308  319   87   98  100  111  122  133  144  146  157
  259  270  272   40  294  305  307  318  248   97  108  110  121  132  143  145  156   86
  269  271   39  293  304  315  317  247  258  107  109  120  131  142  153  155   85   96
  279   38  292  303  314  316  246  257  268  117  119  130  141  152  154   84   95  106
   37  291  302  313  324  245  256  267  278  118  129  140  151  162   83   94  105  116

MAGIC
  192  213  234  255  276  297  318  339  360    1   22   43   64   85  106  127  148  169  190
  212  233  254  275  296  317  338  359   19   21   42   63   84  105  126  147  168  189  191
  232  253  274  295  316  337  358   18   20   41   62   83  104  125  146  167  188  209  211
  252  273  294  315  336  357   17   38   40   61   82  103  124  145  166  187  208  210  231
  272  293  314  335  356   16   37   39   60   81  102  123  144  165  186  207  228  230  251
  292  313  334  355   15   36   57   59   80  101  122  143  164  185  206  227  229  250  271
  312  333  354   14   35   56   58   79  100  121  142  163  184  205  226  247  249  270  291
  332  353   13   34   55   76   78   99  120  141  162  183  204  225  246  248  269  290  311
  352   12   33   54   75   77   98  119  140  161  182  203  224  245  266  268  289  310  331
   11   32   53   74   95   97  118  139  160  181  202  223  244  265  267  288  309  330  351
   31   52   73   94   96  117  138  159  180  201  222  243  264  285  287  308  329  350   10
   51   72   93  114  116  137  158  179  200  221  242  263  284  286  307  328  349    9   30
   71   92  113  115  136  157  178  199  220  241  262  283  304  306  327  348    8   29   50
   91  112  133  135  156  177  198  219  240  261  282  303  305  326  347    7   28   49   70
  111  132  134  155  176  197  218  239  260  281  302  323  325  346    6   27   48   69   90
  131  152  154  175  196  217  238  259  280  301  322  324  345    5   26   47   68   89  110
  151  153  174  195  216  237  258  279  300  321  342  344    4   25   46   67   88  109  130
  171  173  194  215  236  257  278  299  320  341  343    3   24   45   66   87  108  129  150
  172  193  214  235  256  277  298  319  340  361    2   23   44   65   86  107  128  149  170

MAGIC
  400    2    3  397  396    6    7  393  392   10   11  389  388   14   15  385  384   18   19  381
   21  379  378   24   25  375  374   28   29  371  370   32   33  367  366   36   37  363  362   40
   41  359  358   44   45  355  354   48   49  351  350   52   53  347  346   56   57  343  342   60
  340   62   63  337  336   66   67  333  332   70   71  329  328   74   75  325  324   78   79  321
  320   82   83  317  316   86   87  313  312   90   91  309  308   94   95  305  304   98   99  301
  101  299  298  104  105  295  294  108  109  291  290  112  113  287  286  116  117  283  282  120
  121  279  278  124  125  275  274  128  129  271  270  132  133  267  266  136  137  263  262  140
  260  142  143  257  256  146  147  253  252  150  151  249  248  154  155  245  244  158  159  241
  240  162  163  237  236  166  167  233  232  170  171  229  228  174  175  225  224  178  179  221
  181  219  218  184  185  215  214  188  189  211  210  192  193  207  206  196  197  203  202  200
  201  199  198  204  205  195  194  208  209  191  190  212  213  187  186  216  217  183  182  220
  180  222  223  177  176  226  227  173  172  230  231  169  168  234  235  165  164  238  239  161
  160  242  243  157  156  246  247  153  152  250  251  149  148  254  255  145  144  258  259  141
  261  139  138  264  265  135  134  268  269  131  130  272  273  127  126  276  277  123  122  280
  281  119  118  284  285  115  114  288  289  111  110  292  293  107  106  296  297  103  102  300
  100  302  303   97   96  306  307   93   92  310  311   89   88  314  315   85   84  318  319   81
   80  322  323   77   76  326  327   73   72  330  331   69   68  334  335   65   64  338  339   61
  341   59   58  344  345   55   54  348  349   51   50  352  353   47   46  356  357   43   42  360
  361   39   38  364  365   35   34  368  369   31   30  372  373   27   26  376  377   23   22  380
   20  382  383   17   16  386  387   13   12  390  391    9    8  394  395    5    4  398  399    1


no wise fish would go anywhere without a porpoise - The Mock Turtle
GaulerTheGoat
GaulerTheGoat
Hmmm... I found a 10 square on google. This is getting interesting. The 6 square they''ve got is nothing like my six square. BTW, if you don''t care that the numbers are between 1 and n squared, then do you allow negative numbers?

no wise fish would go anywhere without a porpoise - The Mock Turtle

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.

Sign in to reply to this topic.