I am trying to fill missing fields in a 3x3 matrix (square) in order to form a magic square (row, columns both diagonals sum are the same, filled with any none repeating positive integers ). an example of such square will be like :
[_ _ _]
[_ _ 18]
[_ 28 _]
Since it doesn't follow the basic rules of the normal magic square where its integers are limited to 1-9(from 1 to n^2). , the magic constant (sum) is not equal to 15 (n(n^2+1)/2) rather it's unknown and has many possible values.
I tried a very naïve way where I generated random numbers in the empty fields with an arbitrary max of 99 then I took the whole square passed it into a function that checks if it's a valid magic square.
It basically keeps going forever till it finds the combination of numbers in the right places.
Needless to say, this solution was dumb, it keeps going for hours before it finds the answer if ever.
I also thought about doing an exhaustive number generation (basically trying every combination of numbers) till I find the right one but this faces the same issue.
So I need help figuring out an algorithm or some way to limit the range of random number generated
3 by 3 magic squares are a vector space with these three basis elements:
1 1 1 0 1 -1 -1 1 0
1 1 1 -1 0 1 1 0 -1
1 1 1 1 -1 0 0 -1 1
You can introduce 3 variables a, b, c that represent the contribution from each of the 3 basis elements, and write equations for them given your partial solution.
For example, given your example grid you'll have:
a + b - c = 18
a - b - c = 28
Which immediately gives 2b = 10 or b=-5. And a-c = 23, or c=a-23.
The space of solutions looks like this:
23 2a-28 a+5
2a-18 a 18
a-5 28 2a-23
You can see each row/column/diagonal adds up to 3a.
Now you just need to find integer solutions for a and c that satisfy your positive and non-repeating constraints.
For example, a=100, b=-5, c=77 gives:
23 172 105
182 100 18
95 28 177
The minimal sum magic square with positive integer elements occurs for a=15, and the sum is 3a=45.
23 2 20
12 15 18
10 28 7
It happens that there are no repeats here. If there were, we'd simply try the next larger value of a and so on.