Connecting a $n, n$ point grid 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).
 A: Interesting question.  In what follows consider the $n\times n$ square grid.  Notice that the trivial solution obtained by following a square spiral towards the center starting from an outside corner yields a solution with $2n-1$ lines.
To see why, notice that 2 lines reduces the grid to a $(n-1)\times (n-1)$ grid, and since the $1\times 1$ grid requires only 1 line, induction yields $2n-1$ lines.
Can we do better?  Based on the posts in the forum and my own attempts, I believe the answer is that $2n-2$ lines is optimal.  Showing this is possible is again easy.  Start at a corner, and spiral towards the center until there is only a $3\times 3$ grid remaining.  Recall from above that 2 lines in the spiral will reduce the grid by a dimension, so thus far we will have used $2\cdot (n-3)=2n-6$ lines.  On the last line, end it so that we are in a position to go through the diagonal of the $3\times 3 $ grid.  Since the $3\times 3$ grid has a solution with $4$ lines starting diagonally from a corner we have found a solution to the $n\times n$ grid using only $2n-2$ lines.
Now, the question remains, is $2n-2$ optimal?  The more I think about it, the more I believe it, but a proof does not leap into mind.  I will think more.
Edit: Of course $n=1,2$ are exceptions, and required $2n-1$ lines.  The method I presented can be modified slightly to produce a closed path.  All that must be changed is the way the final $3\times 3$ grid is traversed, and perhaps moving the starting position of the first line to a spot slightly outside of the original $n\times n$ grid.  In other words the conjecture Toshi Kato is true.  
Edit 2: For a proof that $2n-2$ is optimal, see Joriki's answer to this question Not lifting your pen on the $n\times n$ grid.
A: There is some discussion of this problem here:  http://www.tek-tips.com/viewthread.cfm?qid=1370890&page=2
A: This preprint of mine, that I have just released, would definitely answer any questions concerning the planar case (the present one):
Shortest polygonal chains covering each planar square grid.
There, I prove that any $n \times n$ grid can be covered by using a path (see Lemma 1). 
Furthermore, we have also a cycle (i.e., a closed path) for any even value of $n$.
Basically, the $2 \cdot n - 2$ solution has been proved to be optimal (for any $n \geq 3$) since 2013 (as far as I know), but nobody has shown before that we do not need to use trails, we just need paths or even cycles.
