469,927 Members | 1,549 Online

# magic square - topographical model ...

I am 50 years old ...and am working physical models of the math structure called a magic square .. for my own interest.

My present problem is this. I have a topograhical model for the square ... where each cell in the square is a solid structure to the height specified by the value in that cell. Then conceptually I pour water on top of the square and see where the water collects ... in lakes as it were.

**** there are 880 different 4x4 magic squares

**** there are 3600 different pandiagonal 5x5 magic squares....

What I think I need is a program that will generate all possible paths from any given cell in the interior of the square ... to the exterior of the square .... restricted to movement on the x,y axis.

For the 5x5 square I have hand written 91 different paths from the x2y2 ... or first interior corner cell to the exterior ...

I would like a algorithm/code that would generate the paths for any order of square ... ie 6x6 , 7x7 etc ...

*******

A real nice guy gave me a example in pseudo code ...that he thought would be a step in the right direction .... I have never done any recursive routines ... and quite frankly don't even know how to right the string to keep adding the new value to the end of itself ... etc ...

*****

here is the idea he gave me ...

#1. you should first use a depth-first search algorithm ...
( I have no acquantaince with that)

#2. for each cell c in the interior
find every path from c to the exterior

define function "find and report every path from c to the exterior."
called FAREPFHTTE(c)

for each diretion up (+1 0), down (-1 0 ), left (0 +1), right (0-1)
nextc = c + direction
if next c is already in the path, skip it
if next c is exterior report path
otherwise call FAREPFHTTE (next c)

****** paths cannot take diagonals ****

We don't want the program to try up, down, up , downn over and over ..
So how can we mark that the cell is already in the path ? We'll keep a array of cells and mark each one as we take it ( and unmark each one as we leave it). So now it is

FAREPFHTTER(c)
A(c) = 1 # mark that c is in use
for each direction up (+1,0), down ((-10), left(0+1), right (0-1)
next c = c + direction
if A(nextc) is 1 , try next direction # it is already in the path skip it
if nextc is exterior, report path
otherwise call FAREPFHITTE(nextc)
A(c) = 0 # mark that c is no longer used

the next problem is , how can we report the whole path? Well pass a string P with the path so far

Clear an array of cells A

FAREPFHTTE(c,P)
A(c) = 1 # mark that c is in use
for each direction up (+1,0), down (-1,0), left (0,+1, right (0 -1)
nextc = c + direction
if A(nextc) is 1 , try next direction #it is already in the path, skip it
if nextc is exterior, print P #print what we have
otherwise call FAREPFHTTE(next c,P."nextc")
A(c) = 0 #mark that c is no longer used

I feel embarrassed to ask someone else to do my work that I would enjoy doing ... but I am interested in the solution ... and for/next loops, some simple sorting .... reading and writing from a file is about the extent of my VB skills...

If any know the landscape and can be of help I would be greatful

Thanks

Craig
Aug 10 '07 #1
1 3756
JosAH
11,448 Expert 8TB
I don't think I understand what your actual problem is or, in other words, what
exactly you want to solve. Can I assume that the magic square is in a horizontal
position and on top of every cell of the square are n cubes positioned where n is
the number in that cell of the square?

You wrote that you 'conceptually' pour water over those piles of cubes. At which
cell? The cell with the highest pile of cubes on it, i.e. the cell with the highest
number?

I assume, correct me if I'm wrong, that the water can only 'fall down' i.e. move
from a cell with a higher number to a cell with a lower number as long as those
cells are adjacent (not diagonal). Right?

What do you want to find? You wrote 'all paths' but 'all paths' starting from the
highest position and ending at a (local) minimum?

kind regards,

Jos
Aug 15 '07 #2