$\begingroup$
Say you had a 3x3 grid, and could pick any square to start with.
From that square, choose an adjacent or diagonal tile to move to, and draw an arrow to it. This is your new tile, and you can now either draw another arrow or stop here. You can touch as many tiles as you'd like, but you can only move to adjacent and diagonal tiles, and can only touch each tile once (once you touch a tile, you can not touch it again). If you drew an arrow every time you chose a new tile, how many different pathways would be possible on this grid? (The path doesn't have to touch every tile, and can end on the first tile chosen)
$\endgroup$ 51 Answer
$\begingroup$The answer is $10305$. You can do it using Python.
# 0 1 2
# 3 4 5
# 6 7 8
Neighbor = {0:{1, 3, 4}, 1:{0, 2, 3, 4, 5}, 2:{1, 4, 5}, 3:{0, 1, 4, 6, 7}, 4:{0, 1, 2, 3, 5, 6, 7, 8}, 5:{1, 2, 4, 7, 8}, 6:{3, 4, 7}, 7:{3, 4, 5, 6, 8}, 8:{4, 5, 7} }
def search(nodes): # Input: A list of already-passed nodes # It must be the prefix of a path # This function calculates the number of paths starting with the nodes next_nodes = (set(range(9))-set(nodes)) & Neighbor[nodes[-1]] num_of_paths = 1 for node in next_nodes: num_of_paths += search(nodes+[node]) return num_of_paths
print(4*search([0])+4*search([1])+search([4]))
