Backtracking is a general algorithm for finding all (or some) solutions to some computational problem, that incrementally builds candidates to the solutions, and abandons each partial candidate c ("backtracks") as soon as it determines that c cannot possibly be completed to a valid solution. (from Wikipedia)
In pseudo-code, a backtracking algorithm looks something like this:
procedure bt(c) if reject(P,c) then return if accept(P,c) then output(P,c) s ← first(P,c) while s ≠ Λ do bt(s) s ← next(P,s)
root(P): return the partial candidate at the root of the search tree.
trueonly if the partial candidate
cis not worth completing.
cis a solution of
first(P,c): generate the first extension of candidate
next(P,s): generate the next alternative extension of a candidate, after the extension
output(P,c): use the solution
P, as appropriate to the application.
The backtracking algorithm then starts with the call
I'm trying to program this as efficiently as possible in Mathematica. I have already coded the pertinent
next functions. Since I only need to obtain one solution, I am doing the
output through a
Given that one has the basic logic of
reject, ..., already coded, are there alternative ways to program the backtracking loop (procedure
bt above) in Mathematica?
What I have in mind is a substitution of
while with something more Mathematica friendly, such as
Map, but I have no idea of how to do this.