49 of 100: Mathematical Meandering

One way to start is to focus on the squares that only have two ways they can be accessed. These are shown with a star:

Now let's draw in the part of the route that these imply. If it's going to be possible to make a full route then it must include these.

Now there are some new squares that only have two access points. They are shown with a star:

Put the route-fragments in for these too.

Repeat the process ...

... until finished:

This was a Hamiltonian paths problem. I tried to find all such paths, and determined that there was only one such way of doing so. I created a script that found all Hamiltonian paths between two points on a graph, as can be demonstrated below.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

connections1 = {'A1': ['A2', 'B1'], 'A2': ['A1', 'A3'], 'A3': ['A2', 'A4',  'B3'], 'A4': ['A3', 'A5', 'B4'], 'A5': ['A4', 'A6'], 'A6': ['A5', 'B6'], 
'B1': ['A1', 'B3', 'C1'], 'B3': ['A3', 'B4', 'C3'], 'B4': ['A4', 'B3', 'C4'],  'B6': ['A6', 'C6'], 
'C1': ['B1', 'C2', 'D1'], 'C2': ['C1', 'C3', 'D2'], 'C3': ['B3', 'C2', 'C4', 'D3'], 'C4': ['B4', 'C3', 'C5', 'D4'], 'C5': ['C4', 'C6', 'D5'], 'C6': ['B6', 'C5', 'D6'], 
'D1': ['C1', 'D2', 'E1'], 'D2': ['C2', 'D1', 'D3', 'E2'], 'D3': ['C3', 'D2', 'D4'], 'D4': ['C4', 'D3', 'D5', 'E4'], 'D5': ['C5', 'D4', 'D6', 'E5'], 'D6': ['C6', 'D5'], 
'E1': ['D1', 'E2', 'F1'], 'E2': ['D2', 'E1', 'F2'], 'E4': ['D4', 'E5', 'F4'], 'E5': ['D5', 'E4', 'F5'],  
'F1': ['E1', 'F2'], 'F2': ['E2', 'F1', 'F3'], 'F3': ['F2', 'F4'], 'F4': ['E4', 'F3', 'F5'], 'F5': ['E5', 'F4', 'F6'], 'F6': ['F5']}

def find_all_paths(graph, start, end, path=[]):
    path = path + [start]
    if start == end:
        return [path]
    paths = []
    for node in graph[start]:
        if node not in path:
            newpaths = find_all_paths(graph, node, end, path)
            for newpath in newpaths:
              if len(newpath)==len(graph):
                  paths.append(newpath)
    return paths

set=[]
set.append(find_all_paths(connections1, 'B1', 'F6'))

print(set)
print(len([j for i in set for j in i]))

I used a chessboard labelling to identify each square (letters at the bottom, numbers on the side). This outputs

1
2

[[['B1', 'A1', 'A2', 'A3', 'B3', 'B4', 'A4', 'A5', 'A6', 'B6', 'C6', 'D6', 'D5', 'C5', 'C4', 'D4', 'D3', 'C3', 'C2', 'C1', 'D1', 'D2', 'E2', 'E1', 'F1', 'F2', 'F3', 'F4', 'E4', 'E5', 'F5', 'F6']]]
1

It is quite fun to see that there is only one solution. There is only one way of getting into and out of a corner square. This applies to either a true corner square or a pattern of squares that is essentially a corner created either by blocked squares or squares already visited.

We start as in the left picture, showing how the path must go through the obvious corners. We then proceed to make forced joins between path sections, and fill in newly created corner turns. Doing this successively as shown, we end up with the RH diagram as the only solution.

But I don't know if this is the only possible path.

I used a constructive graph-theoretic approach. Sharing it for those interested. It looks equivalent to @Mark Dawes ' solution. (Well done, Mark.) Start by creating a graph $G$ from the problem.

Problem: In graph $G$ , construct an S $\rightarrow$ F path $P$ that visits every node (at most once, by definition of a path ).
Fact: each node in $P$ except S and F is required to have degree 2 (i.e., be between exactly 2 path edges), while deg(S) = 1 = deg(F) in $P$ .

Iterate by alternately adding or eliminating possible path edges from $G$ as follows:

(A) Add non-path edges from $G$ to $P$ if those edges are the only way to satisfy a node’s degree requirement in $P$ .

(E) Eliminate all non-path edges from $G$ at each node if the node’s degree requirement in $P$ has been satisfied.

STOP if either all node degree requirements are met (path found) or no more non-path edges can be added or eliminated (no path possible).

Algorithm iterates are shown below where edges in red are added or eliminated based on the degree requirements of red nodes.

This construction also shows the path is unique.

she could because she could go left up and left.(

I don't know if this is valid reasoning, but this is what I did.

I overlaid a checkerboard pattern on top of the grid. Whenever Zara moves from one square to another, the color of the square must change. Of the squares that are "under construction", there is a pair that is one color and a pair that is the other color. This means that there is an equal number of squares of each color remaining, and there is a valid path.

Imagine the grid as a chess board with the home being black. Then Zara is starting on a white space. This means she must take an odd number of steps to finish on a black space. There are 36 spaces on the board, meaning 35 steps to cover the entire board. Taking the construction into consideration, we subtract 4 from 35 to give Zara 31 steps, meaning she will end on a black space hence making it possible.

Think it opposite, ie from home to its initial position