# Find the path in 15 transitions

I found this online (I don't know who made it)

(Note: there is a missing link at the bottom!)

I guess that a transition is a contiguous movement in the same direction (or: the number of changes of direction plus $1$).

I can't solve this in $15$ transitions, and I am starting to doubt a solution even exists. This is the best I could do:

57 58 07 08 09 10 23 24
56 59 06 41 40 11 22 25
55 60 05 42 39 12 21 26
54 61 04 43 38 13 20 27
53 62 03 44 37 14 19 28
52 63 02 45 36 15 18 29
51 64 01 46 35 16 17 30
50 49 48 47 34 33 32 31

which uses $16$ transitions.

• There are similar questions which require you to think 'outside the box'. Almost literally. Maybe something similar is going on here. – Mathias711 Jun 4 '15 at 10:19
• I can do it in 10 if we're allowed to draw outside the box and angle lines. – Ian MacDonald Jun 4 '15 at 12:18

Got it! Here's a badly-done drawing:

• It's 16 because after the 15th you must continue and finish in the starting square – wil93 Jun 25 '15 at 16:23
• To me, 15 transitions sounds like 15 changes in direction which would mean that this answer counts. If the author of the original problem wanted only 15 lines, then I feel like it would have been stated as lines rather than transitions. Of course, this is speculation, but I am giving a +1 to this answer and feel it is correct. – Ryan Jun 25 '15 at 17:59
• @Ryan Transition: the process or a period of changing from one state or condition to another. Synonyms: change, passage, move, transformation, conversion, metamorphosis, alteration, handover, changeover. None of that sounds like "turning"; it all sounds like "moving". I.E., one transition = one move, not one turn. – Engineer Toast Jun 25 '15 at 20:37
• @EngineerToast it sure sounds to me like "changing" directions counts as a transition, but that's just my interpretation. – Ryan Jun 25 '15 at 21:04
• @EngineerToast also thesaurus.com/browse/transition synonym list contains "turn" but not move. I'm not trying to start an argument, but just saying that the original author's intent may not have been to make an unsolvable puzzle. – Ryan Jun 25 '15 at 21:10

It's actually impossible to do this in fewer than 16 transitions if you use only horizontal and vertical transitions, even if your path is allowed to cross itself and/or go out of the box!

Proof: Pick any closed path passing through each square. Extend each transition into a line. Now merge all runs of consecutive identical lines. Now these lines still cover all squares together, and the number of horizontal and vertical lines in the extended path is always equal (and not larger than the number of transitions in the original path), since horizontal and vertical lines alternate.

Assume the path has less than 16 lines, so less than eight horizontal lines. Then there is one row which does not contain a horizontal line. But this row has eight squares, which are necessarily passed over by one vertical line each, so there are at least eight vertical lines, so also eight horizontal lines in contradiction to the assumption.

Hence any axis-aligned path through every square must necessarily have at least 16 transitions.

And here's a non-axis-aligned solution in 15 transitions with self-intersections (14 if you can start somewhere else than the marked square), credit to Sam Loyd:

• I'm not sure if it changes anything but: have you taken in consideration the missing link at the bottom? I'll read and try to understand your proof though, thanks :) – wil93 Jun 4 '15 at 13:02
• This proof doesn't work: there's no reason every row has to have a horizontal and vertical line going through it. – Deusovi Jun 25 '15 at 15:57
• @Deusovi I never claimed that was the case, and the proof doesn't even need that. – Anon Mar 29 '16 at 18:30

The rule you can always apply on a square like this is: shortest even side * 2
This works for every square/rectangle with atleast one even number.

So on a 8*8 square you have to do 8*2 = 16 minimal lines.
And on a 4*17 rectangle you do 4*2 to get 8 minimal lines.

This is the result that I got. It is drawn with fifteen lines, none of which intersect. This is how I interpreted the rules.

• The start of the path and the end of the path must be at the point designated on the map. (The path can be traveled in reverse.)
• The path must follow the paths marked on the map.
• The path may not intersect itself.
• A transition is defined as a change in direction.

This was drawn with sixteen lines, indicating that there are fifteen changes of direction.

• Any reason you've added the image as link rather than as image directly? – BmyGuest Jun 25 '15 at 20:09
• It said "Drag here" and I did that. It posted it as a link instead of inline. I suppose I prefer a smaller spoiler section than a great big one. – Paul Rowe Jun 25 '15 at 20:13
• Simply add a ! before the link like I just did in the edit. – BmyGuest Jun 25 '15 at 20:14
• @BmyGuest Thanks. I didn't think to have two bangs, one for the spoiler and one for the image. – Paul Rowe Jun 25 '15 at 20:16