Minimum number of straight lines to cover $n \times n$ grid?

Question

I want to know the minimum number of lines needed to touch every square of an $n \times n$ grid. The only added rule is that the line has to pass inside the square, not on the edge/corner. I have found a solution for $n-1$ lines for all $2<n\le 10$ but not with fewer lines. I figure you can represent the lines by the squares they pass through, thus making a finite amount of "lines", but I don't have many further ideas. Here is an example of what I mean by "covering a square". The line just needs to pass through any part of the square:

Here is also a solution for a $3 \times 3$ grid with 2 lines:

Answer 1

I have worked on and asked many others about this problem. I think this is a hard problem. According to the authors of the paper below, it is an open problem, as of 2013.

I claim to have a construction of $n-1$ lines for all $n$, but I never wrote it down formally. I believe this to be the correct answer, but lower bound proofs are quite difficult. For small $n$ (say, $n \leq 9$), I could prove a matching lower bound by some ad hoc arguments.

If you want to have an interactive go at this problem, check out my website: https://bob1123.github.io/website/linecovering.html.
Update (2023-11-09): https://bob1123.github.io/linecovering.html

A trivial lower bound is $n/2$. A better lower bound of $2n/3$ is known. See Eyal Ackerman and Rom Pinchasi. "Covering a chessboard with staircase walks." Discrete Mathematics 313.22 (2013): 2547-2551. They generalize from lines to "monotone paths," i.e. contiguous sets of squares which always move down (or stay the same) when going right or always move up (or stay the same) when going right. When covering with monotone paths, the $2n/3$ is tight, so to get to $n-1$ you need to exploit the special structure of lines.

I will note that the only follow-up I know of is Kerimov, Azer. "Covering a rectangular chessboard with staircase walks." Discrete Mathematics 338.12 (2015): 2229-2233. They generalize from $n \times n$ board to an $n \times m$ board.

Answer 2

I think Bob is right. (Thanks for providing the gadget!) The pattern I found for $n=15$ should give an idea about a feasible general pattern. Once all squares were covered, I removed every other line to exhibit the stair shapes.

Going up from the bottom left (or going down from the top right), the pattern encountered is 1 2 1 - 1 2 1 - 1 2 1 - 1 2.
Going right from the bottom left (or going left from the top right), the pattern is 2 4 4 4 1. Both patterns together completely describe the covering.

So it looks like this only depends on n modulo 4 and is straightforward to iterate. To be complete:
Of course this is not yet a rigorous proof, but it should be pretty clear how to formalize it if wanted. :)

EDIT: Even though it is obviously a very hard problem, it is linear in a certain sense, in a similar vein as the (very easy) Pick's theorem. Now, from playing around with the gadget, I have a stronger conjecture:

Trying to cover an $n\times n$ square with only $n-2$ lines, at least 4 cells will remain uncovered. Moreover, if exactly four cells remain, the only connected components formed by those are 1x1 (i.e. isolated cells) and/or 2x1. This would also mean (but I am a bit less sure about this) that no two of those four cells can be diagonally adjacent, i.e. share exactly 1 vertex.

It is this conjecture/finding which gave me the idea of 'linearity'. After all, there may be a hidden but rather easy mechanism hiding behind!

Answer 3

Consider a continuous function $w$ in $Q=[-1,1]^2$ and think of your grid as of $2n\times 2n$ grid of squares of size $1/n$. Then the sum of the values of $w$ along the squares intersecting a line $\ell$ is essentially $n\int_{\ell\cap Q} w(|dx|+|dy|)\le n\sqrt 2\int_{\ell\cap Q}w\,ds$ where $s$ is the length element on $\ell$. Now, the full sum is approximately $n^2\int_Q w$. Thus we have an asymptotic bound of $n$ times $\frac 1{\sqrt 2}\int_Q w$ divided by the supremum of $\int_{\ell\cap Q}w\,ds$ over all lines. Now take $w$ to be a smoothed version of $1/{\sqrt{1-|z|^2}}$ in the unit disk and $0$ outside (the function used to show that you cannot cover the unit disk by strips of total width less than $2$). Then the ratio of the integral to the supremum is ${2\pi}/\pi=2$ and we get $\sqrt 2 n$ versus expected $2n$, which is a loss of factor of $\sqrt 2$. Of course, the whole argument is a shameless plagiarism from Archimedes and it seems like there should be room for some improvement. :-)

Answer 4

I used the integer linear programming (ILP) approach suggested by @BillyJoe. Let $L$ be the set of discrete lines, let $S$ be the set of squares, and let $L_s \subseteq L$ be the subset of lines that cover square $s$. Let binary variable $z_\ell$ indicate whether discrete line $\ell$ is used. The (set covering) problem is to minimize $$\sum_{\ell\in L} z_\ell$$ subject to $$\sum_{\ell\in L_s} z_\ell \ge 1$$ for all $s\in S$. For $n\in\{3,\dots,12\}$, the minimum does turn out to be $n-1$. I used the list of lines generated here by @MikeEarnest, but only the maximal ones (with respect to set inclusion) are needed.

For $n=10$, the linear programming (LP) lower bound is just under $7$, so we don't get a short optimality certificate from a dual LP solution. The ILP solver returned the following solution with $9$ lines, where each square is labeled by the lines that cover it. For example, the top left square is covered by lines $2$ and $7$.

27    2    2    1    1    9    9    8    8    6 
47    7    2    2    1   19    1    8    6    6 
 4    7    7    2   29    9  168  168    6    3 
 4    4    7   79  269   26   68   13   13    3 
 5    4    4  679   67   28  238   23    1    1 
 5   56 4569  469    7  378   37    2    2    1 
 6    6   59   45  345   38    7    7    2    2 
 6    9    9    3 3458  458    5    7    7    2 
 9    9    3    3    8    4    5    5    7    7 
39    3    3    8    8    4    4    5    5   57 

Here are the results for $n \le 15$: \begin{matrix} n & \text{# lines} & \text{# maximal lines} & \text{LP} & \text{ILP} \\ \hline 1 & 1 & 1 & 1 & 1 \\ 2 & 12 & 4 & 1.3333333333 & 2 \\ 3 & 54 & 16 & 2 & 2 \\ 4 & 152 & 44 & 2.5882352941 & 3 \\ 5 & 338 & 116 & 3.3333333333 & 4 \\ 6 & 652 & 236 & 4 & 5 \\ 7 & 1138 & 484 & 4.6976744186 & 6 \\ 8 & 1864 & 820 & 5.3979238754 & 7 \\ 9 & 2882 & 1384 & 6.1142857143 & 8 \\ 10 & 4236 & 2164 & 6.8352769679 & 9 \\ 11 & 6058 & 3276 & 7.5793705947 & 10 \\ 12 & 8376 & 4668 & 8.290598175 & 11 \\ 13 & 11358 & 6632 & 9.0237713232 & [11,12] \\ 14 & 15044 & 8988 & 9.7587254886 & [11,13] \\ 15 & 19498 & 12128 & 10.499058033 & [12,14] \\ \end{matrix}