# Two genies and their kind of chess

While playing chess Parcly and Tori Taxel, best friends and genies, got bored and transformed all the pieces into pawns to make pretty patterns. They found this 22-pawn arrangement where every 3×3 submatrix (not necessarily contiguous) has at least one pawn.

"But," Tori asked Parcly. "What if I remove one pawn?"

Is it possible to arrange 21 pawns so that every 3×3 submatrix is non-empty?

This puzzle was inspired by an MSE question.

• Salt and pepper go well with a steak; cheesecake, while delicious, doesn't really belong on the same plate.
– Bass
Dec 20, 2021 at 3:18
• Thanks Parcly for updating the question. Though I appreciate stories (for example see questions from Alconja, those are great story as a puzzle), I'm afraid I have to agree with Bass here that the previous version of this question feels out of place and perhaps too many unrelated images? As for the latest one, it's very clear now about the objective of the puzzle. You didn't have to remove everything, though. You can still include some variation of "Tori and Parcly are playing chess, but they got bored and decided to place 22 pawns on the board..." etc. Dec 20, 2021 at 10:07

## 2 Answers

You can solve this set covering problem via integer linear programming as follows. Let binary decision variable $$x_{i,j}$$ indicate whether cell $$(i,j)$$ contains a pawn. The problem is to minimize $$\sum_{i=1}^8 \sum_{j=1}^8 x_{i,j}$$ subject to linear constraints $$\sum_{i\in\{i_1,i_2,i_3\}} \sum_{j\in\{j_1,j_2,j_3\}} x_{i,j} \ge 1 \quad \text{for 1\le i_1 The minimum turns out to be

$$22$$.

• Your method is very close to what I myself used to make this puzzle. I used a SAT solver and hand-coded gates to prove the minimum, not just for this board but also for all boards to $11×11$, keeping the submatrix size at $3×3$ – $52$ pawns are needed in the $11×11$ case, and it took the solver over 2 hours to prove that $51$ is not possible there. Dec 19, 2021 at 22:28
• It might speed things up if you also impose constraints implied by smaller boards. Explicitly, let $a_n$ be the minimum for an $n \times n$ board. Then every $(n-1) \times (n-1)$ submatrix must have at least $a_{n-1}$ pawns. Dec 19, 2021 at 22:34
• I see linear programming, I know it must be from you. Haha Dec 20, 2021 at 10:08
• I've posted the optimal configurations I found to 11×11 on the original MSE question. Dec 20, 2021 at 19:57

It is

not possible.

(Ugly) proof:

Assume to reach a contradiction it were possible. Let WLOG ranks 1 and 2 be the two ranks with the smallest number of pawns in them. It is easily verified that the combined number is 4 or less. In other words k>=4 files (WLOG the first k files) have no pawns in the first two ranks. To preclude all 3x3 submatrices in the first k files each of rows 3-8 must have at least k-2 pawns in the first k files. If k>5 that's impossible. If k=5 it's all the pawns left and there would be no pawn at all in ranks 3-8 x files f-h, contradiction. So k must be 4, leaving 5 pawns to cover the 6-by-4 rectangle 3-8 x e-h. If 3 of its ranks are empty we are done. If two, one of the others can only have one pawn and we are done. Therefore there can only be one empty rank (WLOG rank 3) and 5 ranks with exactly one pawn. By pigeon hole principle two of these pawns are on the same file WLOG e4 and e5. But that leaves 3-5 x f-h uncovered. Contradiction.