Via integer linear programming, I found the following minimum values for $n \times n$ grids: >! \begin{matrix} n & \min \\ \hline 3 & 4 \\ 4 & 6 \\ 5 & 8 \\ 6 & 11 \\ 7 & 14 \\ 8 & 16 \\ 9 & 20 \\ 10 & 24 \\ 11 & 28 \\ 12 & 32 \end{matrix} Minimum values for $n \le 44$ are here: https://oeis.org/A365271 8x8: >! [![enter image description here][1]][1] 9x9: >! [![enter image description here][2]][2] 10x10: >! [![enter image description here][3]][3] 11x11: >! [![enter image description here][4]][4] 12x12: >! [![enter image description here][5]][5] [1]: https://i.sstatic.net/t8lV5vyf.png [2]: https://i.sstatic.net/O9wloSb1.png [3]: https://i.sstatic.net/8MBrbn1T.png [4]: https://i.sstatic.net/A0ndvb8J.png [5]: https://i.sstatic.net/UcdCf1ED.png