How do I stop my backtracking algorithm once I find and answer?

Question

I have wrote this code for solving a problem given to me in class, the task was to solve the "toads and frogs problem" using backtracking. My code solves this problem but does not stop once it reaches the solution (it keeps printing "states" showing other paths that are not a solution to the problem), is there a way to do this?. This is the code:

def solution_recursive(frogs):
    #Prints the state of the problem (example: "L L L L _ R R R R" in the starting case
    #when all the "left" frogs are on the left side and all the "right" frogs are on
    #the right side)
    show_frogs(frogs)

    #If the solution is found, return the list of frogs that contains the right order
    if frogs == ["R","R","R","R","E","L","L","L","L"]:
        return(frogs)

    #If the solution isn't the actual state, then start (or continue) recursion
    else:

        #S_prime contains possible solutions to the problem a.k.a. "moves"
        S_prime = possible_movements(frogs)

        #while S_prime contains solutions, do the following
        while len(S_prime) > 0:
            s = S_prime[0]
            S_prime.pop(0)
            #Start again with solution s
            solution_recursive(s)

Thanks in advancement!

Answer 1

How do I stop my backtracking algorithm once I find an answer?

You could use Python exception facilities for such a purpose.

You could also adopt the convention that your solution_recursive returns a boolean telling to stop the backtrack.

It is also a matter of taste or of opinion.