Magic Squares 
Author Message
 Magic Squares

Hi, I need some help with my Logo Programming.  I have Logo v5.1 alpha, and
I am trying to make a program that will solve magic squares.  A magic
square is:

2       9       4               A       B       C
7       5       3               D       E       F
6       1       8               G       H       I

All horizontal, vertical, and diagonal lines = 15.  In my program, I want
to have 10 variables, and assign each square a variable.  Then x = the
total sum I want each row, column, and diagonal to equal.  I'm trying to
make each variable a member of a solution set {1, 2, 3,...to 9}, and then
have the equation A + B + C = X.  Then I enter all the other formulas, such
as A + D + G = X.  Then if all the formulas work out, then it displays the
square and shows the solution.  

        If you've ever done something like this, please respond as soon as
possible.  Thanks!      



Mon, 14 Jun 1999 03:00:00 GMT  
 Magic Squares

Quote:

>I am trying to make a program that will solve magic squares.

This is really less of a Logo question than a math question!

You are proposing to find magic squares by setting up and solving
a system of eight equations (three horizontal, three vertical,
two diagonal) in ten variables.  Since you have fewer equations
than variables, you know there will be lots of possible solutions.
(As there should, since there are lots of magic squares!)  But
you want to constrain the solution by saying that each variable
must be a positive integer less than 10, or at least that's what
you want for the usual X=15 magic squares.  Certainly you want
each variable to be an integer.

Systems of equations in which the solution values are limited to
integers are called "Diophantine equations".  There are several
known methods for solving them, but they're all a bit complicated;
do some research at the library if you want to pursue this route.

But I wouldn't solve your original problem by using equations
at all!  Instead I'd use *backtracking*:  I'd try assigning
values to variables arbitrarily, and see if I get a consistent
result, and if not, change something.  So the structure of the
program would be something like this:

        for [A 1 9] [
          for [B 1 9] [
            if not (:A = :B) [
              for [C 1 9] [
                if (and (not :C = :A)
                        (not :C = :B)
                        (:A + :B + :C = 15)) [
                  for [D 1 9] [
                        ... etc.

At each step you check all the conditions that must be satisfied by
the variables you know so far.  If you get all the values assigned,
in the innermost loop, you print the results.

The structure of the program would be more elegant if you made all
the assignments first and then checked all the conditions:

        for [A 1 9] [
          for [B 1 9] [
            for [C 1 9] [
              ...
                for [I 1 9] [
                  if (and (none-equal :A :B :C :D :E :F :G :H :I)
                          (:A + :B + :C = 15)
                          (:D + :E + :F = 15)
                          ...) [
                     print (list :A :B :C :D :E :F :G :H :I)]]]]...]]

and it could be made even more elegant by using recursion to assign
all the values instead of having nine FOR invocations.  But this
version would run much too slowly, because it would generate and test
many unnecessary sets of values.  For example, it'd try having all
nine variables equal to 1, then it'd try all but I equal to 1 and
I equal to 2, and so on.



Thu, 17 Jun 1999 03:00:00 GMT  
 Magic Squares

Bravo.  Good answer!



Fri, 18 Jun 1999 03:00:00 GMT  
 Magic Squares

random thought: would magic squares (or any other diophantine system)
be suitable material for a GA search?

-j.allen
University of Maine CS
Emergent Systems Group
http://www.umcs.maine.edu/~obelix



Sat, 19 Jun 1999 03:00:00 GMT  
 Magic Squares

Quote:

>Hi, I need some help with my Logo Programming.  I have Logo v5.1 alpha, and

Since you said you have v5.1a I suspect your running MSWLogo 5.1a.
You might like to visit http://www.softronix.com for the latest 5.2d
version.

===============================================================
George Mills

http://www.softronix.com
The www page contains some very powerful educational software.
Our single most important investment is our kids.



Mon, 21 Jun 1999 03:00:00 GMT  
 
 [ 5 post ] 

 Relevant Pages 

1. Magic squares for J

2. Help Please! Magic Square

3. Magic Squares

4. Magic Squares

5. f77 magic square code

6. Fill a table (like a magic square)

7. Solving Magic Squares

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. Icetips Magic Entries & Magic Buttons demo

 

 
Powered by phpBB® Forum Software