How to solve this system of linear equations

$$M = \left(\begin{smallmatrix} a_1 & a_2 & a_3 & a_4\\ b_1 & b_2 & b_3 & b_4\\ a_1 & c_2 & b_2 & c_4\\ a_4 & d_2 & b_3 & c_4\\ b_1 & c_2 & a_2 & e_4\\ b_4 & d_2 & a_3 & e_4\end{smallmatrix}\right)$$ All of the equations equal to 26; augmented, the matrix would then have have “26” to the right of each row.

This is basically the “Star of David” that another user posted:

http://i.stack.imgur.com/mVHwZ.jpg

but I don’t think anyone has solved it like this.

Solutions Collecting From Web of "How to solve this system of linear equations"

You have forgotten the very important condition that all integers between 1 and 12 must be used exactly once.

Though the equations themselves are linear and contain only 0 and 1 as coefficients, the constraint is very tough. I don’t think you could find an easy solution without integer programming, which is, like you may have known, NP-Hard and thus we have by now only exponential solutions, which are not better than brute force for such a small problem.

As I see, there are $960$ solutions ($80$ different solutions, ignoring rotation and mirror-transformation).

For example, $2$ of them:

enter image description here

enter image description here

Way of solving: “try-and-check”.

enter image description here

A).
Consider any values $a,h$.
For example, $a=5,h=6$.

Then possible values for $i,c$ are:
– $3,12$;
– $4,11$;
– $7,8$;
– $8,7$;
– $11,4$;
– $12,3$.

For these values you’ll get system of $5$ equations for $8$ variables. Reduction of system.
Sometimes such system will have no solutions.

B).
Consider $3$ any values for cells $a,c,e$.
Choose values for $b,d,f$, such that $a+c+e=b+d+f$.

When we’ll have values for $a,b,c,d,e,f$, we’ll get system of $6$ equations for $6$ variables ($g,h,i,j,k,l$).

But such system can have no solutions.


If you’ll use brute computer search, then there is not so much permutations of $12$ numbers: $12! = 479~001~600$ (a few seconds of computer work).