Placing dominoes on a chessboard Find the smallest number of dominoes we must place on an $8×8$ chessboard, so that in every $2×2$ square, at least one of the squares is covered by a domino. I am getting confused again and again as I am making many cases and they seem to make the problem harder. Either this problem very easy or very hard.
 A: There are 49 $2\times 2$ boards.
A single domino can cover 6 $2\times 2$ boards.
Thus you need at least 9 dominoes.
On the other hand we can cover your squares claim with 11 dominoes using a greedy type algorithm. I can deploy a maximum of 6 dominoes that cover 6 $2\times 2$ squares per domino. Place dominoes at $(B7,C7)$, $(E7,F7)$, $(B5,C5)$, $(E5,F5)$, $(B3,C3)$, and $(E3,F3)$. The remaining $2\times 2$ all lie along the perimeter of the board and I can deploy 4 dominoes that cover 12 more $2\times 2$ squares. Place dominoes at $(B1,C1)$, $(E1,F1)$, $(H7,H6)$, and $(H4,H3)$. Leaving the final square to be covered with a domino at $(H1,H2)$.
UPDATE: In order to use 9 dominoes, 8 of the dominoes would have to be placed so that they could each cover 6 $2\times 2$ squares, with no overlap. This is impossible. Thus the minimum is at least 10 and I have found a way to do that, but the trick is to allow multiple dominoes cover some squares previously covered by other dominoes.
A: $10$ dominoes:
$$\begin{array}{|c|c|c|} \hline
\;\;&&&&5&&8&\\ \hline
&1&1&&5&&8&\\ \hline
&&&&&&&\\ \hline
&2&&4&&7&&10\\ \hline
&2&&4&&7&&10\\ \hline
&&&&&&&\\ \hline
&3&3&&6&&9&\\ \hline
&&&&6&&9&\\ \hline
\end{array}$$
I placed dominoes $1$ and $3$ for maximal coverage. It’s wasteful to have parallel dominoes with two spaces between them, so I tried turning dominoes $2$ and $4$ the other way. At that point the rest more less just fell into place.
Alternatively, dominoes $5$ and $6$ could be turned horizontal in the second and seventh rows and dominoes $8$ and $9$ moved over to the last column:
$$\begin{array}{|c|c|c|} \hline
\;\;&&&&&&\;\;&8\\ \hline
&1&1&&5&5&&8\\ \hline
&&&&&&&\\ \hline
&2&&4&&7&&10\\ \hline
&2&&4&&7&&10\\ \hline
&&&&&&&\\ \hline
&3&3&&6&6&&9\\ \hline
&&&&&&&9\\ \hline
\end{array}$$
