Magic Squares

[TGR]

Recentallly i was doing a programming competition and this was one of the questions:


Task 4 - Balanced Squares
Description
9 numbers arranged in a 3x3 square is said to form a Balanced Square if every row and every column has the same sum.

For example

1 8 6
10 5 0
4 2 9

is a Balanced Square as every row and column add up to 15.
1 2 3
3 1 2
2 3 1

is also a Balanced Square, every row and column add up to 6.
Write a program which, given a list of 9 integers, prints them out in a Balanced Square. If the integers can be arranged into a Balanced Square in more than one way you may print whichever one you wish.

If it is not possible to form a Balanced Square using the integers print out a message stating this.

The format of your output should match the examples below:

Sample Output
Input
0 1 2 4 6 8 5 10 9
Output
1 8 6
10 5 0
4 2 9

Input
1 1 1 2 2 2 3 3 3
Output
1 2 3
3 1 2
2 3 1

Input
0 1 2 4 6 8 5 3 9
Output
0 1 2 4 6 8 5 3 9 cannot be made into a Balanced Square.


Test Data
0 1 2 4 6 8 5 10 9
1 1 1 2 2 2 3 3 3
0 1 2 4 6 8 5 3 9
1 2 3 4 5 6 7 8 9
12 1 2 3 4 5 6 7 8
1 2 3 3 6 7 4 5 5
8 2 7 1 4 3 3 6 2

Constraints
You may assume the integers are not negative.

It was the only question that I couldn't successfully complete, or even work out any way to even start it! All i could think of was to do a pure number crunch, but surly theres a better way! Any suggestions?

[klintsovi]

You can simplify your search by solving sets of simultaneous equations.

a + b + c = x
d + e + f = x
g + h + i = x

therefore a+b+c+d+e+f+g+h+i = 3x

the first one is to determine what is an x you can see that it is sum of all numbers devided by 3

following the same theory you can do the task. I would not recomend to use VB for the task. I is not going to be very quick.

I would recomend to use eclipse, if you have a choice. The other option is c/c++, you have to be very good to do it.
http://www.icparc.ic.ac.uk/eclipse/

Search internet for "constraint satisfaction and optimisation"

[plenderj]

This is an interesting one
I'll see if I can piece something together .....

[MarkT]

I think this does it. I’m not sure it is the most efficient way of getting there but it does seem to work. It can take some time for it to check all possible combinations. It appears there are about 36000 unique combinations that can be generated from 9 numbers.

It is not in the format shown but that could be easily changed.

By using klintsovi suggestion, you could avoid unnecessary checking.

[plenderj]

This may be of benefit :

http://www.math.twsu.edu/history/Act...html#magic-act


... btw, I hate number theory

[Nucleus]

For each combination of 9 integers there is 362880 permutations.

It took my PIII 5 mins just to run through all the permutations, and I haven't included the magic squares test.

However, I don't see what stops you from writing it in VB except that it will be slower than other lower level languages.

[plenderj]

Bah!

We dont want number crunching.
We want a smart way of doing it.


Though. Now that I come to think of it,
a number crunch application would be a great thing to put in a test. I dont think that a programming exam would test you on some obscure theorem ....

[TGR]

How would anyone have time to write all those if statements in a 2 hr comp? Now that I've seen a solution i understand a bit on how to do it. Thanks for the help!

[plenderj]

I just thought of something.


Lets say you have a 3x3 square.
There are 8 lines that have to add up correctly.

So I *think* I would be right in saying, that if you were to number crunch the combinations of numbers, and once you hit your 8th different permutation, you must have a magic square.

A general case then would be that you require (Number of squares - 1) different permutations of the numbers that add up the same to have a magic square.


Is this correct, or am I making some false assumptions ?

[Kaverin]

You're a bit hung up on what a permutation really is. For a set of N numbers, the value you get when you do a permutation calculation on N is the total number of different ways to arrange the N numbers where order is important, meaning that for N=3, 123 is considered distinct from 321. In a combination (the counterpart of a permutation), the order of the set is not considered important, and thus 123 and 321 are treated as the same set of numbers even though they have a different order. There's also two things mentioned here, a balanced square (which I've never actually heard described mathematically but that doesn't mean it's not real), and the magic square which I'm familiar with. The page mentioned deals with magic squares only, and there are certain requirements for the numbers, like cardinal order from 1 to N^2. If you went by the 8 distinct permutation rule though, nothing is really holding you to the constraint of having a "magic square" (or the balanced one) when you see the 8th different permutation, as all permutation sets are considered different from each other. If that doesn't make sense, look at this generalization (as if you have such a belief you want to test, it will have to hold up to any generalization you give it). Take this set of numbers 1, 1, 1, 1, 1, 1, 1, 1, 2 for a 3x3 square. According to the balanced square data entry, that would be allowable. There are at least 9 different orders, but you can't make a balanced square from that set, since any row or column that contains the 2 will be off.

[Nucleus]

Originally posted by TGR
How would anyone have time to write all those if statements in a 2 hr comp? Now that I've seen a solution i understand a bit on how to do it. Thanks for the help!

If you use a recursive function, you don't have to write much code at all.

Here is a general solution that calculates all permutations for any number of inputs:

Sub Permutations(s As String, Optional sleading As String)
 ' Nucleus
 Dim i          As Long
 Dim a          As Variant
 
 a = Split(s, ",")
 For i = 0 To UBound(a)
    If UBound(a) > 1 Then
        Permutations Right$(s, Len(s) - InStr(1, s, ",")), IIf(Len(sleading), sleading & "," & Left$(s, InStr(1, s, ",") - 1), Left$(s, InStr(1, s, ",") - 1))
    Else
        Debug.Print sleading & "," & s
    End If
    
    s = Right$(s, Len(s) - InStr(1, s, ",")) & "," & Left$(s, InStr(1, s, ",") - 1)
 Next
End Sub

To use the function pass csv input values and the function does the rest. Output is to the debug window.

For example to calculate all permutations for 1 2 10?

Call Permutations("1,2,10")

[MarkT]

I knew there had to be a cleaner way. I just never really got a handle on recurssion. This is really cool.

[Kaverin]

In case anyone wants them, here's some stuff relating to this whole discussion.

'in a module
 
'returns n!, by a recursive style (just in case anyone not familiar with recursion wants to see how it's done.  recursion should be avoided if possible though
Public Function RFactorial(ByVal n As Long) As Double
   RFactorial = 1
   If n < 1 Then Exit Function
   If n = 1 Then
      RFactorial = 1
   Else
      RFactorial = n * RFactorial(n - 1)
   End If
End Function
 
'returns n! as well, but by an iterative method
Public Function Factorial(ByVal n As Long) As Double
   Factorial = 1
   If n = 1 Then Exit Function
   Do While n > 0
      Factorial = Factorial * n
      n = n - 1
   Loop
End Function
 
'returns the permutations of n items taken r at a time; I just like to write mine in the math notation style
Public Function nPr(ByVal n As Long, ByVal r As Long) As Double
   'nPr = n! / (n - r)!
   nPr = 0
   If (n - r) < 0 Then Exit Function
   nPr = Factorial(n) / Factorial(n - r)
End Function
 
'returns the combinations of n items taken r at a time
Public Function nCr(ByVal n As Long, ByVal r As Long) As Double
   'nCr = n! / (r! * (n - r)!)
   nCr = 0
   If (n - r) < 0 Then Exit Function
   nCr = Factorial(n) / (Factorial(r) * Factorial(n - r))
End Function

Have fun

[plenderj]

What I'm saying, is that once you hit combination number :

NumberOfSquares - IIf(HasEvenNumberOfSquares, 0, 1)

then you should have enough for a magic square.
Obviously I mean combinations that fulfill the requirements for a magic square...

[klintsovi]

Right guys,

if I can find my old uni project ( Yes, about magic squares ) I'll post a link.

Ilia

[<ABX]

I wrote a class in VB.NET to do this, if you want you could port it to vb

link

[jemidiah]

Seeing as the other one says it doesn't work with even numbers, I wrote this:

'Needs: a command button (Command1), a listbox (List1)
 
Option Explicit
 
 
Private Sub Command1_Click()
Dim i As Long
Dim i2 As Long
Dim i3 As Long
Dim i4 As Long
 
Dim RndVal1 As Long
Dim RndVal2 As Long
Dim RndVal3 As Long
 
Dim Number(1 To 9) As Long
Dim Permutations(1 To 3, 1 To 504) As Long
Dim PermutationsCulled() As Long
Dim TotalNumber As Single
 
'Here is where you store the numbers. Get them however you feel like,
    'just store them in this array
    'Ex. 0 1 2 4 6 8 5 10 9 should be entered like this:
Number(1) = 0
Number(2) = 1
Number(3) = 2
Number(4) = 4
Number(5) = 6
Number(6) = 8
Number(7) = 5
Number(8) = 10
Number(9) = 9
 
'Find all 504 permutations
Randomize
For i = 1 To 504
ReInit:
    RndVal1 = Int(Rnd * 9) + 1
    RndVal2 = Int(Rnd * 9) + 1
    RndVal3 = Int(Rnd * 9) + 1
    For i2 = 1 To 504
        If Permutations(1, i2) = RndVal1 And Permutations(2, i2) = RndVal2 And Permutations(3, i2) = RndVal3 Then GoTo ReInit
    Next i2
    Permutations(1, i) = RndVal1
    Permutations(2, i) = RndVal2
    Permutations(3, i) = RndVal3
Next i
 
'Transfer the array while cutting out all permutations that do not
    'add up to Total Number / 3
ReDim PermutationsCulled(1 To 3, 1 To 1) As Long
For i = 1 To 9
    TotalNumber = TotalNumber + Number(i)
Next i
For i = 1 To 504
    If Number(Permutations(1, i)) + Number(Permutations(2, i)) + Number(Permutations(3, i)) = TotalNumber / 3 Then
        PermutationsCulled(1, UBound(PermutationsCulled, 2)) = Number(Permutations(1, i))
        PermutationsCulled(2, UBound(PermutationsCulled, 2)) = Number(Permutations(2, i))
        PermutationsCulled(3, UBound(PermutationsCulled, 2)) = Number(Permutations(3, i))
        
        If i <> 504 Then ReDim Preserve PermutationsCulled(1 To 3, 1 To UBound(PermutationsCulled, 2) + 1) As Long
    End If
Next i
 
'Basically, loop through all possible squares and check whether or
    'not it's a magic square. Also, loop through the list and check whether
    'or not it's already been found
For i = 1 To UBound(PermutationsCulled, 2)
For i2 = 1 To UBound(PermutationsCulled, 2)
For i3 = 1 To UBound(PermutationsCulled, 2)
    If PermutationsCulled(1, i) + PermutationsCulled(1, i2) + PermutationsCulled(1, i3) = TotalNumber / 3 Then
    If PermutationsCulled(2, i) + PermutationsCulled(2, i2) + PermutationsCulled(2, i3) = TotalNumber / 3 Then
    If PermutationsCulled(3, i) + PermutationsCulled(3, i2) + PermutationsCulled(3, i3) = TotalNumber / 3 Then
        For i4 = 0 To List1.ListCount - 1 Step 4
            If List1.List(i4) = PermutationsCulled(1, i) & " " & PermutationsCulled(2, i) & " " & PermutationsCulled(3, i) Then
            If List1.List(i4 + 1) = PermutationsCulled(1, i2) & " " & PermutationsCulled(2, i2) & " " & PermutationsCulled(3, i2) Then
            If List1.List(i4 + 2) = PermutationsCulled(1, i3) & " " & PermutationsCulled(2, i3) & " " & PermutationsCulled(3, i3) Then
                GoTo SkipIf
            End If
            End If
            End If
        Next i4
        
        List1.AddItem PermutationsCulled(1, i) & " " & PermutationsCulled(2, i) & " " & PermutationsCulled(3, i)
        List1.AddItem PermutationsCulled(1, i2) & " " & PermutationsCulled(2, i2) & " " & PermutationsCulled(3, i2)
        List1.AddItem PermutationsCulled(1, i3) & " " & PermutationsCulled(2, i3) & " " & PermutationsCulled(3, i3)
        List1.AddItem ""
        
        Me.Refresh
        DoEvents
    End If
    End If
    End If
SkipIf:
Next i3
Next i2
Next i
End Sub

It really is remarkable fast for the number of loops involved. Good luck

[jemidiah]

Well, I edited it seeing as it was using numbers more than once in the same box:

'Needs: a command button (Command1), a listbox (List1)
 
Option Explicit
 
 
Private Sub Command1_Click()
Dim i As Long
Dim i2 As Long
Dim i3 As Long
Dim i4 As Long
Dim i5 As Long
 
Dim RndVal1 As Long
Dim RndVal2 As Long
Dim RndVal3 As Long
 
Dim Number(1 To 9) As Long
Dim Permutations(1 To 3, 1 To 504) As Long
Dim PermutationsCulled() As Long
Dim CrossCheck(1 To 9) As Long
Dim TotalNumber As Single
 
'Here is where you store the numbers. Get them however you feel like,
    'just store them in this array
    'Ex. 0 1 2 4 6 8 5 10 9 should be entered like this:
Number(1) = 0
Number(2) = 1
Number(3) = 2
Number(4) = 4
Number(5) = 6
Number(6) = 8
Number(7) = 5
Number(8) = 10
Number(9) = 9
 
'Find all 504 permutations
Randomize
For i = 1 To 504
ReInit:
    RndVal1 = Int(Rnd * 9) + 1
    RndVal2 = Int(Rnd * 9) + 1
    RndVal3 = Int(Rnd * 9) + 1
    Do Until RndVal2 <> RndVal1
        RndVal2 = Int(Rnd * 9) + 1
    Loop
    Do Until RndVal3 <> RndVal2 And RndVal3 <> RndVal1
        RndVal3 = Int(Rnd * 9) + 1
    Loop
    For i2 = 1 To 504
        If Permutations(1, i2) = RndVal1 And Permutations(2, i2) = RndVal2 And Permutations(3, i2) = RndVal3 Then GoTo ReInit
    Next i2
    Permutations(1, i) = RndVal1
    Permutations(2, i) = RndVal2
    Permutations(3, i) = RndVal3
Next i
 
'Transfer the array while cutting out all permutations that do not
    'add up to Total Number / 3 plus checking to make sure all numbers
    'in Number array are used exactly once and displaying the % done
ReDim PermutationsCulled(1 To 3, 1 To 1) As Long
For i = 1 To 9
    TotalNumber = TotalNumber + Number(i)
Next i
For i = 1 To 504
    If Number(Permutations(1, i)) + Number(Permutations(2, i)) + Number(Permutations(3, i)) = TotalNumber / 3 Then
        PermutationsCulled(1, UBound(PermutationsCulled, 2)) = Number(Permutations(1, i))
        PermutationsCulled(2, UBound(PermutationsCulled, 2)) = Number(Permutations(2, i))
        PermutationsCulled(3, UBound(PermutationsCulled, 2)) = Number(Permutations(3, i))
        
        If i <> 504 Then ReDim Preserve PermutationsCulled(1 To 3, 1 To UBound(PermutationsCulled, 2) + 1) As Long
    End If
Next i
 
'Basically, loop through all possible squares and check whether or
    'not it's a magic square. Also, loop through the list and check whether
    'or not it's already been found
For i = 1 To UBound(PermutationsCulled, 2)
For i2 = 1 To UBound(PermutationsCulled, 2)
For i3 = 1 To UBound(PermutationsCulled, 2)
    If PermutationsCulled(1, i) + PermutationsCulled(1, i2) + PermutationsCulled(1, i3) = TotalNumber / 3 Then
    If PermutationsCulled(2, i) + PermutationsCulled(2, i2) + PermutationsCulled(2, i3) = TotalNumber / 3 Then
    If PermutationsCulled(3, i) + PermutationsCulled(3, i2) + PermutationsCulled(3, i3) = TotalNumber / 3 Then
        For i4 = 0 To List1.ListCount - 1 Step 4
            If List1.List(i4) = PermutationsCulled(1, i) & " " & PermutationsCulled(2, i) & " " & PermutationsCulled(3, i) Then
            If List1.List(i4 + 1) = PermutationsCulled(1, i2) & " " & PermutationsCulled(2, i2) & " " & PermutationsCulled(3, i2) Then
            If List1.List(i4 + 2) = PermutationsCulled(1, i3) & " " & PermutationsCulled(2, i3) & " " & PermutationsCulled(3, i3) Then
                GoTo SkipIf
            End If
            End If
            End If
        Next i4
        
        For i4 = 1 To 9
            CrossCheck(i4) = Number(i4)
        Next i4
        For i4 = 1 To 3
            For i5 = 1 To 9
                If CrossCheck(i5) = PermutationsCulled(i4, i) And CrossCheck(i5) <> 0 Then
                    CrossCheck(i5) = 0
                    Exit For
                End If
            Next i5
        Next i4
        For i4 = 1 To 3
            For i5 = 1 To 9
                If CrossCheck(i5) = PermutationsCulled(i4, i2) And CrossCheck(i5) <> 0 Then
                    CrossCheck(i5) = 0
                    Exit For
                End If
            Next i5
        Next i4
        For i4 = 1 To 3
            For i5 = 1 To 9
                If CrossCheck(i5) = PermutationsCulled(i4, i3) And CrossCheck(i5) <> 0 Then
                    CrossCheck(i5) = 0
                    Exit For
                End If
            Next i5
        Next i4
        i5 = 0
        For i4 = 1 To 9
            i5 = i5 + CrossCheck(i4)
        Next i4
        
        If i5 <> 0 Then GoTo SkipIf
        
        List1.AddItem PermutationsCulled(1, i) & " " & PermutationsCulled(2, i) & " " & PermutationsCulled(3, i)
        List1.AddItem PermutationsCulled(1, i2) & " " & PermutationsCulled(2, i2) & " " & PermutationsCulled(3, i2)
        List1.AddItem PermutationsCulled(1, i3) & " " & PermutationsCulled(2, i3) & " " & PermutationsCulled(3, i3)
        List1.AddItem ""
        
        Me.Refresh
        DoEvents
    End If
    End If
    End If
SkipIf:
Next i3
Next i2
Command1.Caption = Int(i / UBound(PermutationsCulled, 2) * 100) & "%"
Next i
 
Command1.Caption = "Command1"
End Sub

That should give you every single magic square a block of numbers can make. Again, it's amazingly fast for all the loops it uses. Please do note that the more possible magic square there are, the longer it will take (ie, [2, 2, 2, 2, 2, 2, 2, 2, 2] will take forever compared to [0, 1, 2, 4, 6, 8, 5, 10, 9] which will take maybe half a second]

Edit: Somehow my mind wandered back to this and thought the diagonals aren't being checked (though they aren't mentioned in the problem). To check them too, you'd use this:

If PermutationsCulled(1, i) + PermutationsCulled(1, i2) + PermutationsCulled(1, i3) = TotalNumber / 3 Then
    If PermutationsCulled(2, i) + PermutationsCulled(2, i2) + PermutationsCulled(2, i3) = TotalNumber / 3 Then
    If PermutationsCulled(3, i) + PermutationsCulled(3, i2) + PermutationsCulled(3, i3) = TotalNumber / 3 Then
    [b]If PermutationsCulled(1, i) + PermutationsCulled(2, i2) + PermutationsCulled(3, i3) = TotalNumber / 3 Then[/b]
    [b]If PermutationsCulled(3, i) + PermutationsCulled(2, i2) + PermutationsCulled(1, i3) = TotalNumber / 3 Then[/b]

with the proper End If's