Mathematical puzzles that train the programmer's brain Q08 Excellent cleaning robot

Problem summary

Find the number of path patterns that the cleaning robot that moves back and forth and left and right can move in 12 steps. However, the same place will not be visited twice.

Code Depth-first search. Write using recursion.

N = 12 #Number of movements

def dfs(path):
    if len(path) > N:
        return 1
    cnt = 0 #Number of patterns
    for d in [(0,1), (0,-1), (1,0), (-1,0)]:
        next = path[-1][0] + d[0], path[-1][1] + d[1]
        if next not in path:
            cnt += dfs(path + [next])
    return cnt

print(dfs([(0, 0)])) #Initial position(0, 0)To

ToDo Python recursion seems to be slow. Is it faster to write using the stack?

Recommended Posts

Mathematical puzzles that train the programmer's brain Q08 Excellent cleaning robot
Mathematical puzzles that train the programmer's brain Q05 Still paying cash?
Mathematical puzzle to train the programmer's brain Q04 Carving a stick
Mathematical puzzle to train the programmer's brain Q01 "Palindrome in decimal"
Mathematical puzzle to train the programmer's brain Q03 Turn the card over
Mathematical puzzle to train the programmer's brain Q06 (modified version) Collatz's prediction