Minimum guard problem

Question

Placing 1x2 dominoes on an 8x8 chess board, in non-overlapping way, what is the lowest possible number of dominoes to lock (guard) the board, so that no further dominoes can be placed on the board? The aim here is to cover as little as possible and save the maximum number of unused dominoes

Thank you

Answer 1

Regarding the original question, what is the lowest possible number of dominoes to lock the board (assuming that dominoes are actually $2\times1$, not $2\times2$):

The lowest possible number is 22. Here is an example of an optimal placing:

.11.22.3
44.55.63
.77.886.
99.AA.BB
.CC.DD.E
FF.GG.HE
.II.JJH.
KK.LL.MM

Regarding the question how to get this number:

I got that answer using dynamic programming (Python code).

Suppose we have a board partly filled by dominoes and the "emptyness markers", see fig. 1 in the image below.

The generalized problem is: what is the lowest possible number of dominoes can be placed on the rest of the board to lock it? The answer depends only on the last two rows (green ones in fig. 2; note that it doesn't matter how occupied cells pair into dominoes, it only matters if the cell is occupied, or has an "emptyness marker" in it, or neither; and grey cells don't matter at all).

So, if we have seen the same two green rows before, we use the known result for this problem. Otherwise, we recursively try (fig. 3) to put an "emptyness marker" (impossible in this particular case because it would create two nearby empty cells), a horizontal domino, and a vertical domino in the first free cell (moving from top to bottom and from left to right in every row), and count the minimal number for these three cases; the result is stored in the cache.

Finally, we apply this method to the original problem when the board has nothing in it. The program checks all intermediate configurations and gives the answer. By the way, in this particular case of $8\times8$ board (perhaps in other cases, too) the optimal placing given above is the very first locking placing obtained by the sequential addition of the emptiness markers, the horizontal dominoes, and the vertical dominoes, as described above. So it could be obtained by simple greedy algorithm (but the optimality of that placing would require proof anyway, of course).