It turns out that the answer to this question is known for all sizes of grid[1], though it was found fairly recently (2011) and the answer for small grids is qu

It turns out that the answer to this question is known for all sizes of grid[1], though it was found fairly recently (2011) and the answer for small grids is quite complicated. For the 9x4 grid, the optimal number is indeed 10. For large n×m grids, with n and m ≥ 16, the minimum number is: floor((n + 2)(m + 2) / 5) - 4. The linked paper has a full-page table giving the formulae for small grids. Thanks to Schoolmeister for mentioning the name of this problem, which gave me the right terms to search for. 1. https://arxiv.org/abs/1102.5206 https://arxiv.org/abs/1102.5206