MAZE how many routes are possible

Question

What I did:

1. convert this to a graph with nodes representing rooms and edges representing the pathway possible

2. Figure out how many edges were leaving each node minus one since you can't go back (e.g node V would have a value of 2) except obv for Q

3. multiply all together (equaling to 2^8)

Is this right? I know this method might be dumb for a problem for 12-year-olds but im stupid. Any help on how to actually solve this efficiently/improvements is appreciated.

Answer 1

I wrote a little python script to find all the simple paths in the graph from $U$ to $Q$. It found $21$ such paths.

Here's the script:

from collections import defaultdict

adjacent = defaultdict(str)
adjacent['q'] = 'rsx'
adjacent['r'] = 'qst'
adjacent['s']= 'qrw'
adjacent['t']= 'ruv'
adjacent['u']= 'ty'
adjacent['v']= 'twy'
adjacent['w']= 'svx'
adjacent['x']= 'qwz'
adjacent['y']=  'uvz'
adjacent['z']= 'xy'

queue = ['u']
paths = []
while queue:
    path = queue.pop(0)
    if path.endswith('q'):
        paths.append(path)
    else:
        for room in adjacent[path[-1]]:
            if room in path: continue
            queue.append(path+room)
print(f'{len(paths)} simple paths found')
for path in paths:
    print(path.upper())

and here is the output:

21 simple paths found
UTRQ
UTRSQ
UYZXQ
UTVWSQ
UTVWXQ
UYVTRQ
UYVWSQ
UYVWXQ
UTRSWXQ
UTVWSRQ
UTVYZXQ
UYVTRSQ
UYVWSRQ
UYZXWSQ
UYZXWSRQ
UTVYZXWSQ
UYVTRSWXQ
UYZXWVTRQ
UTRSWVYZXQ
UTVYZXWSRQ
UYZXWVTRSQ

The idea of the program is very simple, and you can carry it out by hand for a program this small. Make a list of all the partial paths encountered so far. (This is called queue in the program.) Initially, the only path on the list is $U$. Now so long as there are partial paths on the list, do the following:

1. Remove the first path from the list.

2. For each room adjacent to the last room on the path:

   • If the room is $Q$, add it to the path and record the augmented path as a complete path.

   • If the room is already on the path, do nothing

   • Otherwise, add the room to the path, and put the augmented path back on the end of the list.