Estimation of space is required to store 275305224 of 5×5 MagicSquares? [closed]

Here are some examples of 5×5 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

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

A 5×5 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.

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.

Filed under: softwareengineering - @ 00:25

Thẻ: array, compression, estimation, memory, storage

Thiết kế website giá rẻ

Danh mục

Estimation of space is required to store 275305224 of 5×5 MagicSquares? [closed]

Final notes: