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)
Here,
root(P)
: return the partial candidate at the root of the search tree.reject(P,c)
: returntrue
only if the partial candidatec
is not worth completing.accept(P,c)
: returntrue
ifc
is a solution ofP
, andfalse
otherwise.first(P,c)
: generate the first extension of candidatec
.next(P,s)
: generate the next alternative extension of a candidate, after the extensions
.output(P,c)
: use the solutionc
ofP
, as appropriate to the application.
The backtracking algorithm then starts with the call bt(root(P))
.
I'm trying to program this as efficiently as possible in Mathematica. I have already coded the pertinent root
, reject
, accept
, first
, and next
functions. Since I only need to obtain one solution, I am doing the output
through a Throw
, Catch
combo.
Given that one has the basic logic of root
, 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 Fold
or Map
, but I have no idea of how to do this.
Condition
. See the functionsproceedQ
andsowWord
for the equivalents ofreject/accept
andoutput
respectively.first/next
are implemented via recursion... $\endgroup$guidelines
tag and I think it goes with this question. @DanielLichtblau I do not need to store all the possible chess positions to search them. I just need methods that given a chess position, return other positions to explore (next
andfirst
) in an organized fashion. $\endgroup$