algorithmmathcombinationscombinatoricsmagic-square

Find number of ways to fill the magic square


We have a simplified 3x3 magic square that can be filled with numbers from 0 to 9 with repetitions. The sum of the elements in each row must be equal the sum of the elements in each column, diagonals don't matter.

We need to count the number of ways to fill this square so the sum in each row and column is equal to N.


Solution

  • Let our matrix be

    [[a0, a1, a2],
     [a3, a4, a5],
     [a6, a7, a8]]
    

    The sum of the rows would then be:

    a0 + a1 + a2 = N
    a3 + a4 + a5 = N
    a6 + a7 + a8 = N
    

    And columns:

    a0 + a3 + a6 = N
    a1 + a4 + a7 = N
    a2 + a5 + a8 = N
    

    For each constant N, we have 6 equations of 9 unknowns. As it turns out, the last equation is dependent on the others, so we really only have 5 independent equations, and thus end up with 4 free variables.

    If you solve the system of equations for a given N, you can brute force these 4 variables, and then just verify that the rest resolve to integer values in the range [0, 8]. Here is an example for N=11:

    a1  =    1 a5   +1 a6   +1 a8   +1 a9   -11
    a2  =   -1 a5   -1 a8   +11
    a3  =   -1 a6   -1 a9   +11
    a4  =   -1 a5   -1 a6   +11
    a5  =   arbitrary
    a6  =   arbitrary
    a7  =   -1 a8   -1 a9   +11
    a8  =   arbitrary
    a9  =   arbitrary