-1

Here are some examples of 5x5 Magic Squares found by some good solvers :

Magic Square Generator by Marcel Roos

this program state using 2.4GHz Intel takes about 95 hours to generate all solutions.

open source tool

Magic squares 5x5
Sum must be: 65

Solution:             1
  1  2 13 24 25
  3 23 17  6 16
 20 21 11  8  5
 22  4 14 18  7
 19 15 10  9 12

Solution:             2
  1  2 13 24 25
  3 23 16  8 15
 21 19 10  6  9
 22  4 14 20  5
 18 17 12  7 11

Solution:             3
  1  2 13 24 25
  3 23 19  4 16
 21 15 10 12  7
 22  8  9 20  6
 18 17 14  5 11

 ...

The number of all possible solutions is 275305224. Since calculation of all solutions takes a very long time, I would like have one person with a high speed computer find all solutions (in a long continues span of time) and then share them on the web for other people.

What would be an efficient way to store these solutions, using some sort of compression?

(simple logical trick)by attention to the principle that the sum in all rows and columns and diagonal are equal to 65

we only need to know the value for only 14 cells of 25 cells as shown below , this cause the storage space almost reduce to half 14/25

legend:+ means stored value and x means skipped value !

+ + + + x
+ + + + x 
+ + + + x
x + x + x
x x x x x

closed as unclear what you're asking by gnat, Tulains Córdova, user40980, Michael Shaw, Wayne Molina Aug 14 '14 at 23:31

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 2
    Unclear what help you need. Please clarify your specific problem or provide additional details to highlight exactly what you need. As it's currently written, it’s hard to tell what problem you are trying to solve or what aspect of your approach needs to be corrected or explained. See the How to Ask page for help clarifying this question. – gnat Aug 14 '14 at 10:24
  • 4
    The ftparmy.com/101308-magic-square-generator.html software ("this tool", which you didn't link) is only 327Kb. So, you can effectively compress its entire output to 327Kb if you can assume a compiler is available on the receiving end. – Useless Aug 14 '14 at 10:30
  • @Useless you didn't notice the horrible time needed for calculation of all solution , the purpose is to one person with high speed computer find all solution in long continues span of time and then share them on web for other people – Fereydoon Shekofte Aug 14 '14 at 11:01
  • @gnat the only thing that i know is that transferring of such huge data in ascii format is madness ! and i am not familiar with up to date technologies that relevant to this subject , also i don't know another persons that evaluated all 275305224 on hard disk and examined various compression algorithms on them to tell us about smallest archive that can provided ? – Fereydoon Shekofte Aug 14 '14 at 11:16
  • 2
    Who knows? The question was apparently for a way to compress the output of that software, and sending the software is the best plausible answer to the question as originally asked. I think there's an X-Y problem here anyway. – Useless Aug 15 '14 at 13:08
12

So let's start with the simple approach to calculate the bare minimum and find additional means to reduce the size required.

A 5x5 magic square contains the values from 1 - 25. Said another way, we have 25 potential numbers to store.
There are 25 cells within the grid, and 5 rows.

1st approach
The simplest approach is to use 1 Byte per cell.
So that's 25 Bytes per grid.
25 Bytes for 275,305,224 combinations is 6,882,630,600 Bytes or 6.4 GB.

2nd approach
But we only need 5 bits to represent those 25 potential numbers. 5 bits per cell times 25 cells gives us 15 Bytes, 5 bits per grid.
15.625 Bytes per grid times 275,305,224 combinations is 4,301,644,125 Bytes or 4 GB.

3rd approach
As pointed out in your question, we only need to keep 14 of the 25 cells since we can reliably calculate the missing cells to recreate the grid.

So we can modify the 2nd approach to reduce our required storage further.
5 bits per cell times 14 cells gives us 8 Bytes, 6 bits per grid.
8.75 Bytes per grid times 275,305,224 combinations is 2,408,920,710 Bytes or 2.2 GB

4th approach
According to this site dedicated to magic squares, there are 1,394 ways to add up to 65 using the numbers 1 - 25. So that's 1,394 reductions.

We need 11 bits to represent those 1,394 reductions.
And now we only need to keep 5 reductions instead of 25 cells.
11 bits times 5 reductions gives us 6 Bytes, 7 bits per grid.
6.875 Bytes per grid times 275,305,224 combinations is 1,892,723,415 Bytes or 1.7 GB

5th approach
We can combine the minimum required cell technique with reduction approach to reduce the required space even further.

In this approach, we only need to keep 4 of the 5 reductions since we can calculate the remaining row of values.

11 bits times 4 reductions gives us 5 Bytes, 4 bits per grid.
5.5 Bytes per grid times 275,305,224 combinations is 1,514,178,732 or 1.4 GB.

6th approach
Based on Pieter B's observation about magic squares, we can reduce the number of potential combinations we need to store.

You can rotate a magic square 90 degrees and it will still be good and you can mirror one and it will still be good, so 1 square can actually stand as a solution for 8 squares.

Which brings us from 275,305,224 combinations down to 34,413,153 combinations.

And using our 5th approach, we now have:
11 bits times 4 reductions gives us 5 Bytes, 4 bits per grid.
5.5 Bytes per grid times 34,413,153 combinations gives us 189,272,341.5 Bytes or 180.5 MB.


Final notes:

A good compression algorithm ought to be able to find additional patterns within the listed reductions and reduce the amount of required space even further. I haven't played with calculating permutations lately, so I'm not going to wager a guess as to how much further compression you would see from a good compression algorithm.

  • thank you very much on your very beautiful technical advice ! i should think about your approaches strategy ... – Fereydoon Shekofte Aug 15 '14 at 2:45
2

25 cells each of a number < 255, means each occupies 25 bytes. 25 * 275305224 is 6,563Mb or 6.4Gb.

That's uncompressed. Compressed - it depends on the compression algorithm but you're probably looking at a couple of gig no matter what.

  • 1
    If one assumes each number is <= 25, they will fit into 5 bits, so you can get away with quite a lot less. – Oded Aug 14 '14 at 10:22
  • 1
    @Oded 5/8th the size in fact, still 4Gb uncompressed. Though as he mentioned the web, I'm sure the modern answer would be to store them in an XML format :-) – gbjbaanb Aug 14 '14 at 10:39
  • 2
    store them in an algorithm – Pieter B Aug 14 '14 at 10:46
  • 1
    Given the way these things are calculated (taking a long time) there will not be many (repetitive/predictable) relations among the 25 numbers. But if you look at the order in which they are presented it's obvious that there is some repetition between squares resulting from the way the calculator works. Maybe a compression algorithm can use that, but I would not count on much less data than that 4 GB. I would first suggest lining up the 25x5 bits and see how that compresses, but then how do you want to retrieve the data? – Jan Doggen Aug 14 '14 at 12:18
  • 1
    @gbjbaanb sorry, I wasn't telling enough, I don't know how to exponentially decrease it, but two observations are that: you can rotate a magic square 90 degrees and it will still be good and you can mirror one and it will still be good, so 1 square can actually stand as a solution for 8 squares. – Pieter B Aug 14 '14 at 13:21

Not the answer you're looking for? Browse other questions tagged or ask your own question.