Solving Magic Squares 
Author Message
 Solving Magic Squares

Who can help me finding an algorithem for solving magical squares,
that will say, matrix form squares like 5x5 where horisontal, vertical
and diagonal sum of that row containing numbers is everywhere the
same. Like

834
159
672

and also for squares bigger than 5x5 with accaptable solving time.
(less than one hour).



Wed, 25 Jun 1997 02:18:34 GMT  
 Solving Magic Squares
Shiva Feddema says:

Quote:
>Who can help me finding an algorithem for solving magical squares,
>that will say, matrix form squares like 5x5 where horisontal, vertical
>and diagonal sum of that row containing numbers is everywhere the
>same. Like

>834
>159
>672

>and also for squares bigger than 5x5 with accaptable solving time.
>(less than one hour).

The follwing short program, written in Ilog Solver, a C++ constraint programming
library, allows to find the solution for a 5x5 magic square in less than
2 seconds on a 486/66.  Basically what the program does is stating that
all the numbers in the square are integer, are all different, and that the
sums of diagonals, lines, and columns are equal.  

#include <ilsolver/ctint.h>

int main(int argc, char* argv[]) {
  CtInt i,j;
  CtInt N;
  CtInit();
  N=(argc>1?atoi(argv[1]):5);
  CtIntVar * Sum = new (CtHeap()) CtIntVar(0,1000);  
  CtEq(Sum,N*(N*N+1)/2);
  CtIntVar ** Square=new (CtHeap()) CtIntVar * [N*N];  
  for (i=0; i<N*N; i++) Square[i]=new (CtHeap()) CtIntVar(1,N*N);
  CtAllNeq(N*N,Square);                                     // all the numbers are different
  for (i=0; i<N; i++) CtEq(CtArraySum(N,&Square[N*i]),Sum); // sums on lines
  CtIntVar ** Temp = new (CtHeap()) CtIntVar * [N];
  for (i=0; i<N; i++) {
    for (j=0; j<N; j++) Temp[j]=Square[N*j+i];
    CtEq(CtArraySum(N,Temp),Sum);                           // sums on columns
  }
  for (i=0; i<N; i++) Temp[i] = Square[N*i+i];              // 1st diagonal
  CtEq(CtArraySum(N,Temp),Sum);
  for (i=0; i<N; i++) Temp[i] = Square[N*i+N-i-1];          // second diagonal
  CtEq(CtArraySum(N,Temp),Sum);
  CtSolve(CtGenerate(N*N, Square,CtChooseMinSizeInt));      // enumeration primitive
  // for printing
  for (i = 0; i < N; i++) {
    for (j = 0; j < N; j++) {
      Square[N*i+j]->setName("");
      cout << " " << *Square[N*i+j];
    }
    cout << endl;
  }
  CtEnd();
  return 0;

Quote:
}

--

  ILOG S.A.                      url : http://www.ilog.fr
  2 Avenue Gallieni - BP 85      tel : +33 1 46 63 66 66
  F-94253 Gentilly Cedex FRANCE  fax : +33 1 46 63 15 82


Fri, 27 Jun 1997 17:25:56 GMT  
 Solving Magic Squares
: Who can help me finding an algorithem for solving magical squares,
: that will say, matrix form squares like 5x5 where horisontal, vertical
: and diagonal sum of that row containing numbers is everywhere the
: same. Like
:  
: 834
: 159
: 672

: and also for squares bigger than 5x5 with accaptable solving time.
: (less than one hour).

  For squares of any integer odd size there's an algorithm:

a) let N be the size of the magic square you want (an odd integer number).

        ex.:    N=3

b) write the numbers from 1 to N^2 in N parallel diagonals.

        ex.:            1
                      4   2
                    7   5   3
                      8   6
                        9

c) draw the square of size N centered on the figure you've got.

        ex.:            1
                      _____
                     |4   2|
                   7 |  5  | 3
                     |8   6|
                      -----
                        9

d) move every number outside the square in it, to the farthest position
    you can.

                      _____
        ex.:         |4 9 2|
                     |3 5 7|
                     |8 1 6|
                      -----

                in this case, you've got a magic square of
                size 3, where every column and row sum 15.

   I don't remember if this method says anything about the diagonals. I've
tried some examples and, normally, only the main diagonal match the sum.

   Hope this helps.

--------------------------------------------------------------------------------
Scientist: I'm inventing a new pill with which you'll never be thirsty again.
           Statistics demonstrate that you loose one hour every day to drink.
           For instance, what would you do with an hour of free time every day?
Little prince: I would go slowly to a fountain to drink.
                                            Antoine de Saint Exupery

Me: Be carefull with what do you call research.
--------------------------------------------------------------------------------
 Eduard Elias i Vila                     Univ. Politecnica de Catalunya

 NB: "Elias i Vila" is my last name    Dept. d'Arquit. de Computadors
--------------------------------------------------------------------------------
--

        Eduard Elias i Vila



Sat, 28 Jun 1997 20:20:39 GMT  
 Solving Magic Squares

Quote:

>Offerred without proof: for odd-sided squares, place 1 in the middle
>of the bottom row, and for each n+1 place it in the square at a
>position two squares above and one to the right of n, wrapping round
          ^^^
>the square where necessary.  If you obtain a collision, i.e. the
>previous algorithm requires you to use a previously filled square,
>then place n+1 in the square above n.

>So,

> ***       **2     **2     4*2     4*2     4*2     4*2     4*2     492
> ***  ===> *** ==> 3** ==> 3** ==> 35* ==> 35* ==> 357 ==> 357 ==> 357
> *1*       *1*     *1*     *1*     *1*     *16     *16     816     816
>                    collision               collision

For n=5, do not place it two above and one to the right, but 4 above
and one to the right. In general, perhaps, for a square of n, place it
n-1 above and 1 to the right. If there is a collision, again put m+1'th
number directly above m.

Also appears to work for n=7 with a step of 6 up, one to the right.

Why does this work?

Michael



Tue, 01 Jul 1997 00:31:03 GMT  
 Solving Magic Squares

Quote:


>>Offerred without proof: for odd-sided squares, place 1 in the middle
>>of the bottom row, and for each n+1 place it in the square at a
>>position two squares above and one to the right of n, wrapping round
>>the square where necessary.  If you obtain a collision, i.e. the
>>previous algorithm requires you to use a previously filled square,
>>then place n+1 in the square above n.
>>So,
>> ***       **2     **2     4*2     4*2     4*2     4*2     4*2     492
>> ***  ===> *** ==> 3** ==> 3** ==> 35* ==> 35* ==> 357 ==> 357 ==> 357
>> *1*       *1*     *1*     *1*     *1*     *16     *16     816     816
>>                    collision               collision
>For n=5, do not place it two above and one to the right, but 4 above
>and one to the right. In general, perhaps, for a square of n, place it
>n-1 above and 1 to the right. If there is a collision, again put m+1'th
>number directly above m.
>Also appears to work for n=7 with a step of 6 up, one to the right.
>Why does this work?

Simpler method: start in middle of top row, place next number 1 place
diagonaly up to right (or left, you just get mirror image), on collision place
next number 1 place below last one.  This gives the sequence:

 *1*       *1*     *1*     *1*     *1*     *16     *16     816     816
 ***  ===> *** ==> 3** ==> 3** ==> 35* ==> 35* ==> 357 ==> 357 ==> 357
 ***       **2     **2     4*2     4*2     4*2     4*2     4*2     492

Same method work for any odd square.

--
Mark Biggar



Tue, 01 Jul 1997 06:54:45 GMT  
 Solving Magic Squares

Quote:


>>Offerred without proof: for odd-sided squares, place 1 in the middle
>>of the bottom row, and for each n+1 place it in the square at a
>>position two squares above and one to the right of n, wrapping round
>      ^^^
>>the square where necessary.  If you obtain a collision, i.e. the
>>previous algorithm requires you to use a previously filled square,
>>then place n+1 in the square above n.

>>So,

>> ***       **2     **2     4*2     4*2     4*2     4*2     4*2     492
>> ***  ===> *** ==> 3** ==> 3** ==> 35* ==> 35* ==> 357 ==> 357 ==> 357
>> *1*       *1*     *1*     *1*     *1*     *16     *16     816     816
>>                    collision               collision

>For n=5, do not place it two above and one to the right, but 4 above
>and one to the right. In general, perhaps, for a square of n, place it
>n-1 above and 1 to the right. If there is a collision, again put m+1'th
>number directly above m.

>Also appears to work for n=7 with a step of 6 up, one to the right.

>Why does this work?

Because the most general and correct algorithm is: for odd-sided
squares, place 1 in the middle of row (n+1)/2 [also works if you place 1
in row (n-1)/2] and for each most recently placed n, place n+1 in the
square north-east of n's cell. That is, if n's cell is (i,j), place n+1
in (i-1,j+1). If that cell is already occupied, use the cell reached by
"bouncing" to the north-west of it, that is, (i-2,j). If you fall out of
the square, use modulo arithmetic to wrap around, and keep bouncing the
same way to the north-west as long as necessary.

For example, for n=3:

*** *** 3** 3** 35* 35* 357 357 357
*** **2 **2 4*2 4*2 4*2 4*2 4*2 492
*1* *1* *1* *1* *1* *16 *16 816 816

and for n=5 (using 1,2,3,...,9,a,b,...,n,o,p for single digit numbers in
radix 25 for compact display):

***** ***** ***** 4**** 4**** 4**** 4**** 4**8* 4**8* 4**8* 4**8* 4c*8*
***** ***** ****3 ****3 ****3 ****3 **7*3 **7*3 **7*3 **7*3 b*7*3 b*7*3
***** ***2* ***2* ***2* ***2* *6*2* *6*2* *6*2* *6*2* *6*2* *6*2* *6*2*
**1** **1** **1** **1** **1** **1** **1** **1** **1** a*1** a*1** a*1**
***** ***** ***** ***** *5*** *5*** *5*** *5*** *5**9 *5**9 *5**9 *5**9

4c*8* 4c*8* 4c*8* 4c*8g 4c*8g 4c*8g 4c*8g 4c*8g 4c*8g 4c*8g 4c*8g 4c*8g 4cp8g
b*7*3 b*7*3 b*7*3 b*7*3 b*7*3 b*7*3 b*7*3 b*7k3 b*7k3 b*7k3 b*7k3 bo7k3 bo7k3
*6*2* *6*2* *6*2f *6*2f *6*2f *6*2f *6j2f *6j2f *6j2f *6j2f n6j2f n6j2f n6j2f
a*1** a*1e* a*1e* a*1e* a*1e* ai1e* ai1e* ai1e* ai1e* ai1em ai1em ai1em ai1em
*5d*9 *5d*9 *5d*9 *5d*9 h5d*9 h5d*9 h5d*9 h5d*9 h5dl9 h5dl9 h5dl9 h5dl9 h5dl9

You may also verify that it works for n=7, and all n odd.

The reason David's method worked on n=3 with his "2 above" rule is
because n-2 is equal to 1 modulo 3. The "fix" proposed by Michael hinted
at that by changing the increment to n-1 for sinze n. This, as shown
above need not be, and the same decrement of 1 can always be used for
all sizes because in general n-(n-1) = 1 modulo n. Simple enough...

Cheers,

-hak
--



Tue, 01 Jul 1997 11:21:19 GMT  
 Solving Magic Squares

Quote:
>Who can help me finding an algorithem for solving magical squares,
>that will say, matrix form squares like 5x5 where horisontal, vertical
>and diagonal sum of that row containing numbers is everywhere the
>same.

Since version 1.0 of DFKI Oz is released, I would like to
show the solution of the magic square problem in Oz using
finite domain constraints.

declare

proc {Magic N ?Matrix ?Sum}
   !Matrix = {List N}
   %% make the matrix to consist of N rows
   {ForAll Matrix fun {$} {List N} end}
   %% build a list of all matrix elements ...
   Ds = {FoldR Matrix Append nil}
   %% ... and constrain them to numbers between 1 and N*N
   Ds  ::: 1#N*N
   %% what is the sum of a row, column or diagonal?
   !Sum =  N*(N*N+1) div 2
   %% sum up the elements of a list
   fun {FdSum Ds}
      case Ds of nil then 0
      [] D|Dr then {FD.'+' D {FdSum Dr}}
      end
   end
   proc {State Ds} {FdSum Ds Sum} end
in
   %% all matrix elements are different
   {FD.allDifferent Ds}
   %% sum up rows
   {ForAll Matrix State}
   %% sum up columns
   {Loop.for 1 N 1
    proc {$ I}
       {State {FoldL Matrix fun {$ Dr Ds} {Nth Ds I}|Dr end nil}}
    end}
   %% sum up diagonals
   {State {List.foldLInd Matrix fun {$ I Dr Ds} {Nth Ds I}|Dr end nil}}
   {State {List.foldLInd Matrix fun {$ I Dr Ds} {Nth Ds N-I+1}|Dr end nil}}
   % enumerate variables
   {FD.enums Ds}
end

/*

{Search query(proc {$ S}
                 !S=Sum#Square in
                 {Magic 5 Square Sum}
              end)}

{Search next}

*/

--
-----------------------------------------------------------------------
| Joerg Wuertz           | Phone: +49 681 302-5315                     |
| DFKI                   | Fax: +49 681 302-5341                       |

| D-66123 Saarbruecken   | WWW:   http://ps-www.dfki.uni-sb.de/~wuertz |
| Germany                |                                             |
-----------------------------------------------------------------------



Fri, 11 Jul 1997 21:43:20 GMT  
 
 [ 7 post ] 

 Relevant Pages 

1. Magic squares for J

2. Magic Squares

3. Help Please! Magic Square

4. Magic Squares

5. Magic Squares

6. f77 magic square code

7. Fill a table (like a magic square)

8. Magic Square

9. any1 done a magic square in c++ using class

10. Magic square

11. Heuristic search routine for Magic-N Squares puzzle?

12. Magic Number Mystery Solved

 

 
Powered by phpBB® Forum Software