dfs.py

def DFS(depth=0, state=None):
    if check_state_is_valid(depth, state):
        report_found(state)

    if depth >= target_depth:
        return

    for next_step in possible_steps(depth, state):
        current_state = state
        apply_step_on_state(next_step, state)
        if is_valid_state(state):
            DFS(depth + 1, state)
        state = current_state