How to prove the number of solutions to nine dots puzzle

Forget to begin with that we have to find a path, but simply try covering the $9$ points by four infinte straight lines.

Call a line covering $n$ points an $n$-line. Since four lines covering only $2$ points each can never cover $9$ points a solution has at least one $3$-line in it. When identifying rotations and reflections we have exactly three distinct types of $3$-lines:

enter image description here

No parallel $3$-lines

It is not possible to have a solution involving parallel $3$-lines. For instance if we have the following situation:

enter image description here

When the two blue $3$-lines shown above have been placed we have to cover the remaining three points by two lines. So at least one line must cover more than one point which implies that the dashed grey line has to be added. But three parallel lines are clearly impossible, since it takes two additional linear moves to visit and travel along all three, but we only have one line left!

Ruling out type 3

With the above we can rule out type 3 being a part of any solution: We cannot have any line parallel to the initial $3$-line by the above argument. This actually means that each of the remaining three lines has to cover exactly $2$ of the remaining $6$ points each. Also we can only have one line orthogonal to the $3$-line for otherwise we would again have parallel $3$-lines (in the orthogonal direction).

So we have to have two lines passing through $2$ of the remaining $6$ points each that are not parallel nor orthogonal to the initial $3$-line of type 3. When symmetries are considered, this gives essentially two setups to consider. The first one is:

enter image description here

which clearly does not hold a solution since the lines only intersect at one point so it takes far more than four linear moves to travel since you would have to return to this intersection time and again in any path traversing parts of all of these lines. The other setup to consider is:

enter image description here

One way of seing why the above holds no solution is, that some of the lines are only intersected in ways having some of their points lying to both sides of the point of intersection. This makes it impossible to go through all points on any of these without visiting that line twice or reversing direction at some point.

Ruling out exclusive type 1 or 2

If we start from type 1 and do not allow type 2 and already know that type 3 must be ruled out and that no line parallel to the initial $3$-line is allowed, we see that this means that a line that passes the center point of the $9$ point pattern can pass no other point it the pattern as that would lead to one of the situations just mentioned. But with a line that only passes through the center the remaining two lines must covers $5$ points, so one of the lines must cover the $3$ points that are parallel to the initial $3$-line which again leads to a paralel $3$-lines contradiction.

If we start from type 2 and do not allow the other two types, there is essentially only one setup not already covered to consider:

enter image description here

which is another setup having three parallel lines. By previous arguments three distinct parallel lines can never be part of any solution.

The unique solution (type 1 + type 2)

By inclusion-exclusion any solution must involve type 1 and type 2 at the same time. So the situation looks like this to begin with:

enter image description here

and since we already know that we are not allowed to add a line parallel to the $3$-line of type 1 there are only two ways to complete the above setup. One way is like this:

enter image description here

and we see how the $3$-line of type 1 is the only line connecting to the other three lines to one side of their points. The other three lines divide each other in parts having points on each side. So all three other lines must be connected to the $3$-line of type 1 in a given solution. This is impossible since each line can only be connected to two other lines in a path that does not travel along any line twice.

So finally this leaves us with the well known solution as essentially the only possibility when considering rotations and reflections.


As always, the solution depends entirely on your assumptions. In fact, that is the stated purpose of this exercise, to examine your assumptions. And yet the standard "solution" only scratches the surface of examining the solutions. For example... We assume that the paper is perfectly flat. We assume that the lines must pass through the center of each dot rather than touching the edge of a dot. We assume that the line has no thickness. We assume that the paper can't be folded. If you discard any of these assumptions, more solutions appear. For example, if you discard the assumption that the line must pass through the center of each dot, there is a quite simple three line solution. The three lines are almost, but not quite, parallel to each other. Two of them slant very slightly down and one of them slants very slightly up. Extend the lines very far away from the grid and they meet. Just how far you need to extend them depends on the thickness of the dots how closely spaced the dots are.

Even if you restrict the answers to the world of mathematics, where points are infinitely small and lines are infinitely thin, there is still a three line solution if you use a different coordinate system. Imagine a sphere perched on top of an infinite plane. Draw x-y coordinates on the plane, as usual. Now imagine a telescope mounted at the very top of the sphere (the "north pole", you might say). Every point on the x-y plane can be mapped to a specific point on the sphere by pointing the imaginary telescope from the top of the sphere toward that xy point and seeing where the line of sight intersects the sphere. Now we define a "straight line" on the sphere to be whatever projects as a straight line on the x-y plane. Locate the 3x3 grid on the x-y plane and project it onto the sphere. Draw three horizontal lines (which are parallel on the x-y plane) covering the entire grid. Project these lines onto the sphere. Note that lines on the x-y plane which extend to infinity are line segments on the sphere, all of which meet at the north pole. Hence, you can draw the grid of nine dots on the sphere, trace ONLY THREE line segments through those nine dots. It's easy. You put your imaginary pencil on dot1, trace through dot2 and dot3, all the way up to the north pole, then start your second segment at the perfect angle so it will hit dot6, dot5, and dot4, and come back around to the north pole again, where you start your third line segment which hits dot7, dot8, and dot9.