Skip to content

Magic Square Finder in Java using combination trees and object-orientated design principles. The algorithm will search and find all N*N magic squares.

Notifications You must be signed in to change notification settings

seanemery1/magic-squares

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

18 Commits
 
 
 
 
 
 

Repository files navigation

Magic Squares

A magic square is a square array of numbers consisting of the distinct positive integers 1, 2, ..., n^2 arranged such that the sum of the n numbers in any horizontal, vertical, or main diagonal line is always the same number. For instance, for a 3x3 Magic Square, every row, column, and diagonal sums to 15:

3x3 Magic Square Example

alt tag

Row summations: 2 + 7 + 6 = 15, 9 + 5 + 1 = 15, 4 + 3 + 8 = 15.
Column summations: 2 + 9 + 4 = 15, 7 + 5 + 3 = 15, 6 + 1 + 8 = 15.
Diagonal summations: 2 + 5 + 7 = 15, 6 + 5 + 4 = 16.

Algorithm

The naive/brute-force approach finding all NxN magic squares would be to simply test every permutation of 1, 2, ..., N^2. However, this is extremely problematic because a NxN magic square would have N^2! permutations to validate. Although brute-forcing through all 362880 (9!) permutations of a 3x3 magic square is manageable, anything beyond this would take too long to run (a 4x4 magic square would have ~21 trillion permuations).

The approach that this algorithm uses to significantly cut down on the number of permutations we would normally have to validate is by abusing two known properties of magic squares:

  1. Each total row/column/diagonal sum of a NxN magic square is N(N^2-1)/2
  2. One base magic square has 8 variants if we apply the appropriate transformation.
Original Flip Y-Axis Flip X-Axis Flip XY-Axis
816
357
492
616
753
294
492
357
816
294
753
618
Transpose Flip Y-Axis Flip X-Axis Flip XY-Axis
834
159
672
438
951
276
672
159
834
276
951
438

Ideally, it might be possible to only search through a subset of permutations that will only find 1/8 of all the possible NxN magic squares and then apply the above transformations to obtain all 8. However, the algorithm in this code only manages to find 1/2 of all the possible magic squares before it applys a reflection on the Y-axis to obtain the rest of the valid magic squares.

The way this algorithm is implemented is as follows:

  1. Using an index tree, we search through all combinations of N summands that add up N(N^2-1)/2 and store them in an ArrayList. For example, in a 3x3 magic square, the summands are as follow:

         15=1+5+9      15=1+6+8      15=2+4+9      15=2+5+8
         15=2+6+7      15=3+4+8      15=3+5+7      15=4+5+6

Consequently, the summands {1,5,9}, {1,6,8}, {2,4,9}, {2,5,8} {2,6,7}, {3,4,8}, {3,5,7} {4,5,6} are then stored in an ArrayList.

  1. Next, a recursive method is called that isolates the first set of valid summands from the ArrayList, and then filters all other sets by removing any sets that shares a common element with the removed set:

{1,5,9} is isolated. {1,6,8}, {2,4,9}, {2,5,8} {2,6,7} are removed because it contains 1, 5, or 9. {3,4,8}, {4,5,6} are kept through the filtering process.

  1. With the isolated set of summands, all permuations are found:

{1,5,9}, {1,9,5}, {5,1,9}, {5,9,1}, {9,1,5}, {9,5,1}

  1. Construct the first row of multiple magic square candidates by making the above permutations the numbers in the first row. However, it should be noted that when constructing the first row, only the first half of the permutations of the isolated summands are kept (keep {1,5,9}, {1,9,5}, {5,1,9}) while the second half is discarded (discard {5,9,1}, {9,1,5}, {9,5,1}). By doing this only on the construction of the first row of a magic square, when we do eventually find one magic square, we can also find the other by reflecting the square on the Y-axis:
Kept Discarded
159
xxx
xxx
951
xxx
xxx
194
xxx
xxx
591
xxx
xxx
519
xxx
xxx
915
xxx
xxx
  1. For each of the currently constructed magic squares with the first row filled in, repeat steps 2-4 on the remaining summands that survived the filter (in this case, {3,4,8}, {4,5,6}). For instance, this magic square:
1 5 9
x x x
x x x

will have its second row recursively filled with either {3,4,8}, {3,8,4}, {4,3,8}, {4,8,3}, {8,3,4}, or {8,4,3}. And because the remaining set of summands ({4,5,6}) shares no common elements with {3,4,8}, it will survive the filtering process and all of its permutations will be filled in on the 3rd and final row.

  1. When a magic square is fully filled in (or there are no more filtered summands that can complete the square), all column and diagonal sums will be validated to see if they each add up to N(N^2-1)/2 (row sums have already been validated to add up N(N^2-1)/2). For example:

Invalid Magic Square (Discarded)

1 5 9
3 4 8
4 5 6
Found/Valid Y-flipped
816
357
492
618
753
294

When a valid magic square is found, both the original and its flipped variant are logged and the count for the total number of square is incremented by 2.

Usage

Clone or download the repository.

Under the public static void main(String[] args) method in tester.java, modify "byte n = 4;" to desired magic square dimension to find all nxn magic squares.

Benchmarks: n = 3 will finish in a few seconds n = 4 will finish in 4-10 minutes (depending on hardware) n = 5 will produce magic squares throughout, but may take a few days to finish running

About

Magic Square Finder in Java using combination trees and object-orientated design principles. The algorithm will search and find all N*N magic squares.

Topics

Resources

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published

Languages