Minimum strokes = odd dots ÷ 2
In a connected figure with 2k odd dots (k at least 1), you need at least k strokes, and k strokes are always enough.
| Odd dots | Minimum strokes | Example |
|---|---|---|
| 0 or 2 | 1 | Square, House of Santa Claus |
| 4 | 2 | X square, the original seven bridges of Königsberg |
| 6 | 3 | Hexagon + 3 diagonals through the centre |
| 8 | 4 | 3×3 square grid (the 8 non-corner dots on the border are 3) |
Why it works
A single stroke can only “use up” an odd dot at its start and its finish, two per stroke. So 2k odd dots need at least k strokes. Going the other way, pair the odd dots and add an imaginary line between each pair: every dot becomes even, the figure becomes drawable in one line, and lifting the pen at each imaginary line splits it into k strokes.
Retracing instead of lifting
If you cannot lift the pen but may run over lines you have already drawn, the question becomes “what is the least retracing?” This is the Chinese postman problem, first studied by the Chinese mathematician Guan Meigu (Kwan Mei-ko) in 1960.
- Find all the odd dots.
- Pair them up so that the total of the shortest distances between partners is as small as possible.
- The shortest path between each pair is what you will travel twice.
- Count those paths as doubled lines and every dot is even, so a closed one-line route exists.
With only 2 odd dots and no need to return to the start, you do not have to retrace anything; just draw from one odd dot to the other.
Everyday routes
Any job that has to cover every street at least once has the same shape: delivering flyers to every road in a neighbourhood, walking every trail in a park, or sweeping every lane of a car park. Put a dot on each junction of a map, count the odd ones, and you get a sense of how much backtracking can be cut.
In the app
You never get an impossible board
OneTrail builds each board on your device and checks it can be solved before showing it. Every board therefore has 0 or 2 odd dots. If a board seems impossible, recheck your start and your order rather than the board.
FAQ
What if the drawing has separate pieces?
Work out each piece on its own. Even a piece with no odd dots needs one stroke, so add one per piece with 0 odd dots and (odd dots ÷ 2) for the others.
Does it matter how I pair the odd dots?
Not for the number of strokes. It does matter for the shortest retrace: pick pairs that are close to each other.
OneTrail: One Line Draw Puzzle
No sign-up, fully offline, and every board is checked to be solvable before you see it. Free on Android.