Backtracking is a general algorithm for finding all (or some) solutions to some computational problems .../... that incrementally builds candidates to the solutions, and abandons each partial candidate ("backtracks") as soon as it determines that cannot possibly be completed to a valid solution.

The backtracking algorithm enumerates a set of partial candidates that, in principle, could be completed in various ways to give all the possible solutions to the given problem. The completion is done incrementally, by a sequence of candidate extension steps.

Conceptually, the partial candidates are represented as the nodes of a tree structure, the potential search tree. Each partial candidate is the parent of the candidates that differ from it by a single extension step; the leaves of the tree are the partial candidates that cannot be extended any further.

The algorithm traverses this search tree recursively. At each node c, it checks if c can be completed to a valid solution. If not, the whole sub-tree rooted at c is pruned. Otherwise, the algorithm checks whether c itself is a valid solution, and if so reports it to the user; and recursively enumerates all sub-trees of c.

Therefore, the actual search tree that is traversed by the algorithm is only a part of the potential tree. The total cost of the algorithm is the number of nodes of the actual tree times the cost of obtaining and processing each node. This fact should be considered when choosing the potential search tree and implementing the pruning test.

Backtracking most efficient when searching to prove that a problem has a solution (or to find its first solution).

Will focus on this aspect in our examples.

Backtracking is built into Prolog

A Prolog program is a set of predicates.

A predicate consists in one or more clauses

A variable is a sequence of letters and digits starting with a capital letter (_ is considered as a capital letter)

An atom is a sequence of letters and digits starting with a lowercase letter or a any sequence of characters enclosed by single quotes.

speaker(xmlamsterdam, eric). attendee(xmlamsterdam, john). attendee(Conference, X) :- speaker(Conference, X). ?- attendee(xmlamsterdam, X). X = john ; X = eric. ?- speaker(xmlamsterdam, X). X = eric.

The eight queens puzzle is the problem of placing eight chess queens on an 8×8 chessboard so that no two queens threaten each other. Thus, a solution requires that no two queens share the same row, column, or diagonal.

- Finding the index of the queen in each row is sufficient
- Simple to implement with two loops

xquery version "3.0"; declare namespace f = "https://gitlab.dyomedea.com/presentations/backtracking/tree/master"; declare function f:queens($N as xs:integer) as element()* { f:queens($N, ()) }; declare function f:queens($N as xs:integer, $placed as xs:integer*) as element()* { if (count($placed) = $N) then <q>{$placed}</q> else for $new in 1 to $N where not(f:attack($placed, $new)) return f:queens($N, ($placed, $new)) }; declare function f:attack($placed as xs:integer*, $new as xs:integer) as xs:boolean { ($new = $placed) or f:same_diag($placed, $new) }; declare function f:same_diag($to_test as xs:integer*, $new as xs:integer) { if (count($to_test) = 0) then false() else ( let $h := $to_test[1] let $t := $to_test[position() > 1] let $ydist := count($to_test) let $xdist := abs($h - $new) return ($xdist = $ydist) or f:same_diag($t, $new) ) }; <solutions> {f:queens(8)} </solutions>

- Candidate selection in the where clause
- Flower expressions cannot be "aborted" after first complete match
- f:queens(8)[1] potentially as long to evaluate than f:queens(8)

% User friendly predicate to find solutions to the N queens problem. queens(N, Queens) :- queens(N, [], Queens). % Recursive predicate to actually compute the solutions. queens(N, Placed, Queens) :- between(1, N, New), \+attack(Placed, New), append(Placed, [New], NewlyPlaced), queens(N, NewlyPlaced, Queens). queens(N, Queens, Queens) :- length(Queens, N). % Detect an attack if the queens are on a same column attack(Placed, New):- member(New, Placed). % Detect an attack of the queens are on a same diagonal attack(Placed, New):- same_diag(Placed, New). % Do the actual check for the diagonals same_diag([H|T], New):- length([H|T], Ydist), Xdist = abs(New-H), ( Ydist is Xdist; same_diag(T, New) ). ?- queens(8, Q). Q = [1, 5, 8, 6, 3, 7, 2, 4] ; Q = [1, 6, 8, 3, 7, 4, 2, 5] ; Q = [1, 7, 4, 6, 8, 2, 5, 3] .

xquery version "3.0"; import module namespace b = "https://gitlab.dyomedea.com/presentations/backtracking/tree/master" at "backtrack.xq"; declare namespace f = "https://gitlab.dyomedea.com/presentations/backtracking/tree/master"; declare function f:queens($N as xs:integer) as element()* { f:queens($N, ()) }; declare function f:queens($N as xs:integer, $placed as xs:integer*) as element()* { if (count($placed) = $N) then <q>{$placed}</q> else b:between(1, $N, function ($new as xs:integer) { ( b:report(f:attack($placed, $new)), f:queens($N, ($placed, $new)) ) }) }; declare function f:attack($placed as xs:integer*, $new as xs:integer) as xs:boolean { ($new = $placed) or f:same_diag($placed, $new) }; declare function f:same_diag($to_test as xs:integer*, $new as xs:integer) { if (count($to_test) = 0) then false() else ( let $h := $to_test[1] let $t := $to_test[position() > 1] let $ydist := count($to_test) let $xdist := abs($h - $new) return ($xdist = $ydist) or f:same_diag($t, $new) ) }; <solutions> {f:queens(8)} </solutions>

xquery version "3.0"; module namespace b = "https://gitlab.dyomedea.com/presentations/backtracking/tree/master"; declare function b:between($from as xs:integer, $to as xs:integer, $statements as function(*)) { if ($from <= $to) then try { $statements($from) } catch b:fail { b:between($from + 1, $to, $statements) } else b:fail() }; declare function b:fail() { error(QName('https://gitlab.dyomedea.com/presentations/backtracking/tree/master', 'fail')) }; declare function b:report($condition as xs:boolean) { if ($condition) then b:fail() else () };

Saxon | MarkLogic | BaseX | |
---|---|---|---|

11 queens | 7.9 | 17.9 | 1.7 |

11 queens[1] | 0 | 17.9 | 1.7 |

11 queens backtrack | 0 | not supported | 0 |

- Saxon is able to optimize finding the first solution
- In this specific case, the backtracking library works quite well
- That's not always the case!

Verbal arithmetic, also known as alphametics, cryptarithmetic, ..., is a type of mathematical game consisting of a mathematical equation among unknown numbers, whose digits are represented by letters. The goal is to identify the value of each letter.

S | E | N | D | ||

+ | M | O | R | E | |

- | - | - | - | - | - |

= | M | O | N | E | Y |

Backtracking library ~ 10 times slower (213s vs 23s with BaseX)

- The only solution at the "end" of the tree
- Flower expressions highly optimized (can be run in parallel)
- Recursive functions are much slower

- Same mechanisms possible in XSLT 3
- HOF are fun
- try/catch can be fun too
- Fun, but... use with caution!

Use a spacebar or arrow keys to navigate