I stumbled across the problem of connecting the points on a $n, n$ grid with a minimal amount of straight lines without lifting the pen.
For $n=1, n=2$ it is trivial. For $n=3$ you can find the solution with a bit trial and error (I will leave this to the reader as it is a fun to do, you can do it with 4 lines). I found one possible solution for a $4,4$ grid and animated it, it uses 6 lines and is probably optimal (will hopefully help you to understand the problem better, the path doesn't have to be closed like in the animation, open ends are allowed!):
Now my question is, for higher $n$, is there a way to get the amount of minimal lines to use and does an algorithm exist to find a actual solution? I think its quite hard to model the "straight lines" with graph theory.
Edit: Reading Erics excellent answer I found the following website: http://www.mathpuzzle.com/dots.html that also gives an algorithm to connect the points in $2n-2$ steps, solutions up to $10,10$ and mentions:
Toshi Kato conjectures: On $(2N+1)x(2N+1)$ grid, $N \geq 2$, Using $4N$ continuous lines, and not lifting your pencil from the paper, can go through all the dots of a $(2N+1)x(2N+1)$ grid, ending at the same place started. But must visit at least one dot twice in the route.
On $(2N)x(2N)$ grid, $N \geq 2$, Using $4N-2$ continuous lines, and not lifting your pencil from the paper, can go through all the dots of a $(2N)x(2N)$ grid, ending at the same place started. And can visit each dots just once.
It seems to be an open problem to show that $2n-2$ is optimal.
Also I found the following page with a proof that in the $3,3$ grid there cannot be $2$ parallel lines: http://fahim-patel.blogspot.com/2011/01/proof.html I think it might be interesting for coming up with a proof that $2n-2$ is optimal (however maybe there is no such proof, as we only saw solutions for very small $n$, for bigger $n$ there might be some developments we don't know about).