Fill the magic 4 x 4 square

Following question is courtesy to Mathex Exam: 1984

Given a 4 x 4 matrix, we need to fill in crosses at 10 out of 16 places such that each row and each column has an even number of crosses.

• I think I've asked a similar puzzle in the past. Need to find it... – Dmitry Kamenetsky Mar 22 at 8:20

It is fairly straightforward to deduce a solution.

10/4>2 so there has to be at least one row with more than 2 crosses. To be even, it must be a completely filled row. The same goes for a column.

If you permute the rows of a solution it remains a solution, and similarly you can permute columns.

So we can assume without loss of generality that the first row and the first column are completely filled. This uses 7 of the crosses, so we have 3 remaining. Rows 2-4 and columns 2-4 all need an extra cross (since they are odd). The easiest way to do this is to fill the diagonal, and this solution is essentially unique up to permutation of the rows or columns.

 x x x x
x x . .
x . x .
x . . x

An alternative is to start with a filled grid, and then place the 6 blank spaces, also using an even number in each row and column.

I believe this is a valid solution:

 X X X X  X X  X   X  X     X

Brief explanation:

As the OP noted in their answer, we must have a (4, 2, 2, 2) distribution of crosses among both the rows and the columns, otherwise there must be at least one row or column with an odd number of crosses. So we fill the first row and column with all Xs, leaving us with 3 crosses which we can place in the remaining 3 x 3 empty grid such that each cross is in a unique row and column. The solution above is one way to do this.

• Ah, you beat me to it. I didn't see your solution when I submitted mine. +1 – Jaap Scherphuis Mar 21 at 19:01

This pattern is only almost exactly the same that HTM and Jaap already posted, but the approach may be of some interest. Or then again, it may not :-)

 X X
X X X X
X   X
X X 

To find this solution, I first flipped the puzzle over: a full grid satisfies the parity condition, so instead of 10 crosses, we can just do the puzzle with 6. Any solution for 6 will automatically work for 10 as well: the 6 crosses will be the "holes" in the final solution.

Then I picked the shape of a deadly sudoku pattern with 6 cells, because those very often come with row- and columnwise paired squares. By chance, I happened to pick one that didn't produce the exact shape the others had.

And apart from choosing how to stretch that pattern to aesthetically fit it onto the 4x4 grid, that was pretty much all of it.