1 reply to this topic

[The_Journey]

I'm having a tough time trying to create a backtracking that would find all solutions to a problem.

Here is the current general backtracking that I'm using from Backtracking Algorithms

ALGORITHM try(v1,...,vi)
IF (v1,...,vi) is a solution THEN RETURN (v1,...,vi)
FOR each v DO
IF (v1,...,vi,v) is acceptable vector THEN
sol = try(v1,...,vi,v)
IF sol != () THEN RETURN sol
END
END
RETURN ()

However, if I'm not wrong, this only gives me one solution vector, while there could be many solution vectors to a problem like the N-Queen problem.

So if you can, please help me with a general backtracking algorithm that could find all solutions to a problem, not just one. I've been wracking my brain for few days but I can't figure it out.

Thanks :)

[zoranh]

In recursive backtracking algorithm, add an argument to the function which contains the list of all solutions found this far.

Then, instead of RETURN sol, add sol to that list and continue as if nothing happened.

Once the originally invoked function exits, the list will contain all solutions that it encountered. Also, note that function will exit once all states of the system have been walked depth-first, which may be about never, depending on the system searched.