# Walk a Crooked Path

Here is a $$7\times7$$ board with three squares removed.

You walk a path from square to square (adjacent horizontally or vertically), without visiting any square more than once. What is the most crooked path you could walk?

• You may start on any square and end on any square.
• You do not need to visit every square.
• Find a path that has as many quarter turns as possible.

Here is a short example path:

This path has $$7$$ turns in it.

Here's the solution, and a proof of its optimality:

This solution has 38 turns.

First, an important fact:

Any row, or section of a row that is blocked on both sides, with an odd number of cells must have at least one non-turn. This is because every cell with a turn has exactly one horizontal (and one vertical) half-segment, but every horizontal half-segment connects to a partner in the same row.

This also shows that every row must have an even number of "turns plus horizontal endpoints". And of course, the same argument applies to columns, but replacing 'horizontal' with 'vertical'.

Now, analysing the grid:

The grid has 46 cells in it. I've marked four regions in different colors.

The blue cells cannot have turns in them; there are 2 of those.

There must be at least 1 non-turn in the red cells. (The only way to get both of the left ones to turn is to make a C shape, but then if the right ones both turn you've formed a tiny loop.)

The 1 yellow column, and each of the 4 purple columns, must each have at least one non-turn, by the "important fact" above.

This gives an upper bound of 46 - (2+1+1+4), or 38 cells.

Constructing the solution:

All gray cells must then be turns, and we must have 3 turns in the red region and 2 in the yellow. So that gives this:
At least one of the red dotted lines will be taken, and exactly one of the yellow dotted lines will be taken. Each dotted line, if taken, turns cells 3-7 of the row it is in into an odd row; these must be the positions of the four non-turns in the pink region, and so the rows that do not have dotted lines (3, 7, and either 1 or 2) are entirely turns.

The cell in row 1, column 6, cannot be a turn. So the upper red dotted line must be used, and that must be the non-turn in its row.

If the top yellow dotted line is taken, the 3x3 region in the middle is closed off. So the bottom yellow dotted line must be taken instead. Row 4 must then be full of turns, and row 6 must have its non-turn in column 3 to not create a small loop:

Then from here, we can either skip the top right or bottom right cell of the central 3x3 area. Either leads to a valid 38-turn solution.

• 38 is possible. Your proof is correct until a mistake in constructing the last picture. – Jaap Scherphuis Jun 19 '19 at 5:20
• @JaapScherphuis Ah, I see the problem -- I didn't realize the red section could be resolved that way! Fixed. – Deusovi Jun 19 '19 at 5:58
• I don't quite get "If the top yellow dotted line is taken, the 3x3 region in the middle is closed off." as all the grey sections still lead into it, but the paths you get then are not crooked enough so that choice does indeed fail. When I constructed this puzzle with computer assistance I wasn't sure if there was a nice argument that did not rely on brute force, so I'm happy that you worked it out. You get the green tick. – Jaap Scherphuis Jun 19 '19 at 6:20
• @JaapScherphuis I meant that if the bottom yellow cell is not a turn, the remaining cells in the middle of that row are turns, and so the only way in is with the two endpoints in column 6. But the lower one would need to turn up to complete the path after going to R5C5, cutting off the rest of the area. – Deusovi Jun 19 '19 at 6:26

I will start the ball rolling with 36 corners