# 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.

• The figure has 2 axes of symmetry. – user5402 Sep 20 '13 at 13:16

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.

• There are only twelve variables. – Don Larynx Sep 20 '13 at 13:55
• @Jossie That's true. So...what's your point? – ftfish Sep 20 '13 at 13:58

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

For example, $2$ of them:  Way of solving: "try-and-check". 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).