This week's book giveaway is in the Mac OS forum.
We're giving away four copies of a choice of "Take Control of Upgrading to Yosemite" or "Take Control of Automating Your Mac" and have Joe Kissell on-line!
See this thread for details.
The moose likes Programming Diversions and the fly likes Magic Square water retention Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


JavaRanch » Java Forums » Other » Programming Diversions
Bookmark "Magic Square water retention" Watch "Magic Square water retention" New topic
Author

Magic Square water retention

Craig Knecht
Greenhorn

Joined: Jan 09, 2011
Posts: 5

Al Zimmermann's programing contest regarding maximum water retention for magic squares orders 4 - 28 ended this past July, 2010. For the 8x8 magic square with 797 units of water retained there is only one known pattern that achieves that maximum retention. I wish find all solutions for the 8x8 magic square that retain 797 units.

I believe the enumeration for 7x7 magic square - maximum retention 418 units has been solved with 10,432 examples.


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



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


above are two examples 8x8 MS retaining 797 units of water


http://www.knechtmagicsquare.paulscomputing.com/

The above link ... section #1, #13 explains the basic concept of water retention in a magic square

Thanks

Craig

Ryan McGuire
Ranch Hand

Joined: Feb 18, 2005
Posts: 1007
    
    3
Craig Knecht wrote:
I wish find all solutions for the 8x8 magic square that retain 797 units.


Can you write code to enumerate all the unique 8x8 Magic Squares? Do you have code that will evaluate their water retention (which I prefer to think of as Jaegermeister retention)? Put the two together and you have your solution.

You COULD try some sort of genetic algorithm, except A) You already have one optimal solution and B) there's no guarantee that you'd find ALL the optimal solutions.

Any other thoughts?
Craig Knecht
Greenhorn

Joined: Jan 09, 2011
Posts: 5

Thanks for your thoughts !

#1. no enumeration is possible for the 8x8 magic squares


5x5 magic squares can be enumerated .... there are 275 million of them .. so a complete sort is possible

A exact count or enumeration is not possible for orders > 5.

Walter Trump in 2003 give a estimate of the number of 7x7 magic squares ... 10 ^ 34 power.


#2. do you have code to evaluate the water retention ....

A real nice guy wrote a clever algorithm that will determine the water retention of any order of square . For the present stated problem I am only trying to find all solutions for the one given pattern ... so that simplifies things considerably. I think terms like lake and pond are fairly self explanatory. In this instance the lake is the largest water retaining area within the square. The lake border is always made up of the largest numbers .... and thus the spillway is always the smallest of the lake border numbers.....

I believe that their are 15 cells that make up the lake. They fill to the lowest number in the lake border .. so 15 x 52 = 780 units retained .. minus the base of the lake which is the sum of the 15 cell values that form the base of the lake ... apply the same principle to the ponds .. and one simple line of code will ensure that the retained value > 796 units......


#3. The scope of the 7x7 problem allowed the assignment of two types of constraints ... #1. a number range could be assigned to each of the 49 cells ... by using a logic constraint compiler ... supplying 1/2 the 49 values .. . and then deriving the number range possible for the unassigned values. #2. additional constraints .... such as the sum of all values ... in the lake border ... always using the largest number .. must always have the same total ... + the 4 corners must sum to 35 or 36.


*** the F1 compiler is a free download ... This is at least a initial attempt to begin to find the number range allowed for each of the 64 cells..

////// 11 - 17 - 2010
///// F1 compiler logic constraint program
///// examination of pattern maximum retention
///// 8 x 8 Magic Square

/////

///////

///// 797 units retained .. 224 examples


pred Magic5Assoc() iff
ms::[0..63]->>L[1..64] &
ms = [ a1, a2, a3, a4, a5, a6, a7 ,a8,
b1, b2, b3, b4, b5, b6, b7, b8,
c1, c2, c3, c4, c5, c6, c7 ,c8,
d1, d2, d3, d4, d5, d6, d7, d8,
e1, e2, e3, e4, e5, e6, e7, e8,
f1, f2, f3, f4, f5, f6, f7, f8,
g1, g2, g3, g4, g5, g6, g7, g8,
h1, h2, h3, h4, h5, h6, h7, h8 ] &

// I believe this section just states that lake border always uses the largest numbers
// and thus must always have a sum of … 754 …..
// these constraints other than the individual constraints speed up the finding of solutions

b4 + c3 + c5 + d2 + d6 + e1 + e7 + f1 + f6 + g2 + g5 + h3 + h4 = 754 &

a3 + b2 + c1 + h6 + g7 + f8 + a5 + a6 + b7 + c8 + d8 = 506 &


// I force some of the individual cell values to be a specific value in this section

a7 = 40 &
b8 = 32 &

g8 = 30 &
h7 = 31 &








b7 = 51 &

d5 = 27 &
e4 = 33 &

g2 = 63 &



b2 = 43 &
c3 = 62 &


f6 = 60 &
g7 = 46 &
h8 = 3 &

// this section is my educated guess on what the range of values for a individual
// Cell should be ……

a1 = 1 &

a2 > 23 &
a2 < 28 &

a3 > 40 &
a3 < 43 &

a4 > 37 &
a4 < 40 &








a5 > 46 &
a5 < 51 &



a6 > 46 &
a6 < 51 &

a7 > 38 &
a7 < 42 &


a8 > 14 &
a8 < 17 &


b1 > 34 &
b1 < 37 &


b2 = 43 &



b3 > 17 &
b3 < 23 &







b4 > 59 &

b5 > 1 &
b5 < 10 &



b6 > 1 &
b6 < 10 &


b7 > 49 &
b7 < 53 &

b8 > 30 &
b8 < 33 &


c1 > 40 &
c1 < 43 &

c2 > 1 &
c2 < 8 &

c3 > 59 &
// c3 < 63 &

c4 > 13 &
c4 < 20 &

c5 > 55 &
c5 < 60 &

c6 > 23 &
c6 < 27 &

c7 > 3 &
c7 < 10 &

c8 > 46 &
c8 < 51 &














d1 > 27 &
d1 < 31 &

d2 > 57 &
d2 < 60 &

d3 > 12 &
d3 < 16 &

d4 > 21 &
d4 < 24 &

d5 > 25 &
d5 < 29 &

d6 > 55 &
d6 < 58 &

d7 > 1 &
d7 < 10 &

d8 > 46 &
d8 < 51 &














e1 > 51 &
e1 < 56 &

e2 > 9 &
e2 < 15 &

e3 > 19 &
e3 < 25 &

e4 > 31 &
e4 < 35 &

e5 > 21 &
e5 < 24 &

e6 > 14 &
e6 < 20 &

e7 > 60 &

e8 > 35 &
e8 < 40 &













f1 > 51 &
f1 < 56 &

f2 > 16 &
f2 < 20 &

f3 > 33 &
f3 < 36 &

f4 > 19 &
f4 < 25 &

f5 > 7 &
f5 < 12 &

f6 > 59 &
f6 < 63 &

f7 > 18 &
f7 < 22 &

f8 > 43 &
f8 < 46 &













g1 > 34 &
g1 < 38 &

g2 = 63 &


g3 > 9 &
g3 < 15 &

g4 > 9 &
g4 < 15 &

g5 > 57 &
g5 < 60 &

// g6 > 1 &
g6 < 7 &


g7 = 46 &


g8 > 29 &
g8 < 32 &


h1 > 9 &
h1 < 12 &

h2 > 33 &
h2 < 38 &


h3 > 51 &
h3 < 56 &

h4 > 51 &
h4 < 56 &

h5 > 27 &
h5 < 30 &

h6 > 43 &
h6 < 46 &


h7 > 29 &
h7 < 32 &

// Hopefully this line of code is self explanatory. It only allows for solutions with
// greater than 796 units retained

// there are 15 cells making up the lake. They must fill to smallest value in the
// lake border .. ie 52 …. 52 x 15 = 780 …
// then you must subtract the sum of the cells forming the base of the lake and do the same process for the ponds .....
780 - (c4 + d3 + d4 + d5 + e2 + e3 + e4 + e5 + e6 + f2 + f3 + f4 + f5 + g3 + g4) + (235 - (b5 + b6 + c6 + c7 + d7)) + (41 - b3 ) + (172 - (f7 + g6 + b3 + c2)) > 796 &





/// these are just the normal magic square constraints .. all rows/columns/main diagonals = same sum

a1 + b1 + c1 + d1 + e1 + f1 + g1 + h1 = 260 &
a2 + b2 + c2 + d2 + e2 + f2 + g2 + h2 = 260 &
a3 + b3 + c3 + d3 + e3 + f3 + g3 + h3 = 260 &
a4 + b4 + c4 + d4 + e4 + f4 + g4 + h4 = 260 &
a5 + b5 + c5 + d5 + e5 + f5 + g5 + h5 = 260 &
a6 + b6 + c6 + d6 + e6 + f6 + g6 + h6 = 260 &
a7 + b7 + c7 + d7 + e7 + f7 + g7 + h7 = 260 &
a8 + b8 + c8 + d8 + e8 + f8 + g8 + h8 = 260 &


a1 + a2 + a3 + a4 + a5 + a6 + a7 + a8 = 260 &
b1 + b2 + b3 + b4 + b5 + b6 + b7 + b8 = 260 &
c1 + c2 + c3 + c4 + c5 + c6 + c7 + c8 = 260 &
d1 + d2 + d3 + d4 + d5 + d6 + d7 + d8 = 260 &
e1 + e2 + e3 + e4 + e5 + e6 + e7 + e8 = 260 &
f1 + f2 + f3 + f4 + f5 + f6 + f7 + f8 = 260 &
g1 + g2 + g3 + g4 + g5 + g6 + g7 + g8 = 260 &
h1 + h2 + h3 + h4 + h5 + h6 + h7 + h8 = 260 &


a1 + b2 + c3 + d4 + e5 + f6 + g7 + h8 = 260 &
a8 + b7 + c6 + d5 + e4 + f3 + g2 + h1 = 260 &



PrettyPrintA(ms,0)

local proc PrettyPrintA(ms:<[0..63]->>L[1..64], i:<I) iff
if i < 8 then
j = i*8 &
Print('\n') &
PrintDigit(ms(j)) &
PrintDigit(ms(j+1)) &
PrintDigit(ms(j+2)) &
PrintDigit(ms(j+3)) &
PrintDigit(ms(j+4)) &
PrintDigit(ms(j+5)) &
PrintDigit(ms(j+6)) &
PrintDigit(ms(j+7)) &


PrettyPrintA(ms,i+1)
else
Print('\n')

end

local proc PrintDigit(d:<L) iff
if d < 10 then
Print(' ',d,' ')
else
Print(d,' ')
end















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

___ Solution: 1 ___ [00:18:57] __ [Backtracks: 11797379] ____

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

___ Solution: 2 ___ [00:18:57] __ [Backtracks: 11797379] ____

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




#4. The scope of the 8x8 problem does not allow me to easily assign a restricted number range for each of the 64 cells. I think I need a automated process that helps do that

Thanks again

Craig
Craig Knecht
Greenhorn

Joined: Jan 09, 2011
Posts: 5

I looked at Walter Trump's magic square web page to get the number of magic squares for each order ...

#1. There are 3.798 x 10 ^ 34 number of 7x7 normal magic squares. The known number with maximum water retention at 10,432 narrows that down a bit.

#2. There are 5.225 x 10 ^ 54 number of 8x8 normal magic squares.

I presently just have a limited goal of getting proven examples that show that the 8x8 will have more solutions with max retention then the 7x7 MS (10,432) or 6x6 MS (14,277)


#3. trying to figure the number range allowed for each of the 64 cells .... I cannot find any examples for E4 other than the value 33

#4. finding ways to split the main problem up into small enough pieces that the logic constraint process can solve for solutions. Having examples with different values in the 4 corners is one way to split it up .... I also am forcing many of the cells in one of the main diagonals to just have one value.

#5 getting the correct range of values (20-25) around E4 ... .. (ie d4, e3, e5, f4) seems to add a lot of solutions



I do not think it is going to be very difficult to get > 14,000 solutions but it would be cool if there was actually a billion or more solutions for the 8x8 magic square with this one pattern retaining 797 units of water !


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



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



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


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


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


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


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


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




constraint table: Improvements from previous table


a1 < 4 &

a2 > 23 &
a2 < 28 &

a3 > 40 &
a3 < 43 &

a4 > 37 &
a4 < 40 &

a5 > 46 &
a5 < 51 &

a6 > 46 &
a6 < 51 &

a7 > 38 &
a7 < 42 &

a8 > 13 &
a8 < 17 &

b1 > 34 &
b1 < 37 &

b2 = 43 &

b3 > 17 &
b3 < 23 &

b4 > 59 &

b5 < 10 &

b6 < 10 &

b7 = 51 &
b7 > 49 &
b7 < 53 &

b8 > 30 &
b8 < 33 &

c1 > 40 &
c1 < 43 &

c2 < 8 &

c3 > 59 &

c4 > 13 &
c4 < 20 &

c5 > 55 &

c6 > 23 &
c6 < 27 &

c7 > 3 &
c7 < 10 &

c8 > 46 &
c8 < 51 &

d1 > 27 &
d1 < 31 &

d2 > 57 &
d2 < 60 &

d3 > 12 &
d3 < 16 &

d4 > 19 &
d4 < 25 &

d5 = 27 &
d5 > 25 &
d5 < 29 &

d6 > 55 &
d6 < 58 &



d7 > 1 &
d7 < 10 &

d8 > 46 &
d8 < 51 &


e1 > 51 &
e1 < 56 &

e2 > 9 &
e2 < 15 &

e3 > 19 &
e3 < 25 &

e4 = 33 &
e4 > 31 &
e4 < 35 &

e5 > 19 &
e5 < 25 &

e6 > 14 &
e6 < 20 &

e7 > 60 &

e8 > 35 &
e8 < 40 &


f1 > 51 &
f1 < 56 &

f2 > 16 &
f2 < 20 &

f3 > 33 &
f3 < 36 &

f4 > 19 &
f4 < 25 &

f5 > 7 &
f5 < 12 &

f6 > 59 &
f6 < 63 &

f7 > 18 &
f7 < 22 &

f8 > 43 &
f8 < 46 &


g1 > 34 &
g1 < 38 &

g2 = 63 &


g3 > 9 &
g3 < 15 &

g4 > 9 &
g4 < 15 &

g5 > 57 &
g5 < 60 &

g6 < 7 &

g7 = 46 &

g8 > 29 &
g8 < 32 &


h1 > 7 &
h1 < 12 &

h2 > 33 &
h2 < 38 &


h3 > 51 &
h3 < 56 &

h4 > 51 &
h4 < 56 &

h5 > 27 &
h5 < 30 &

h6 > 43 &
h6 < 46 &


h7 > 29 &
h7 < 32 &

h8 < 5 &



Craig Knecht
Greenhorn

Joined: Jan 09, 2011
Posts: 5

Harry White has a webpage up on "Bordered magic squares" where he posts in the download section a .exe program that will give the amount of water held by any square . The amount of water held by each cell is posted below .. ie in the first example the b3 value with 22 ... fills to a level of 42 before it spills off the square .. and thus retains 20 units of water ... which is shown below.




Order 8, cells retaining water 24 (37.5%), units retained 797

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

20 38 41
36 35 21 40
38 28 25 43
41 29 19 31 37
34 18 32 44 25
39 40 43



Order 8, cells retaining water 24 (37.5%), units retained 797

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

20 38 41
36 35 21 40
38 28 25 43
41 29 19 31 37
34 18 32 44 25
40 39 43



Order 8, cells retaining water 24 (37.5%), units retained 797

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

20 38 41
36 35 21 40
38 28 25 43
39 29 19 31 37
34 18 32 44 25
40 41 43



Order 8, cells retaining water 24 (37.5%), units retained 797

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

20 38 41
36 35 21 40
38 28 25 43
39 29 19 31 37
34 18 32 44 25
41 40 43

Craig Knecht
Greenhorn

Joined: Jan 09, 2011
Posts: 5

It turns out that the number of solutions is going to be more like a trillion instead of a billion.




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




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