Your browser doesn't support the features required by impress.js, so you are presented with a simplified version of this presentation.

For the best experience please use the latest Chrome, Safari or Firefox browser.

CC By 4.0 This document is published under a CC Attribution 4.0 International license

Backtracking and XPath Derived Languages (XPDL)

Eric van der Vlist (vdv@dyomedea.com)

November 2015

XML Amsterdam 2015
This presentation online
http://vdv.re/ams2015

Backtracking for dummies (by a dummy)

Definition

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.

--Wikipedia

Description (1/4)

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.

--Wikipedia

Description (2/4)

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.

--Wikipedia

Description (3/4)

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.

--Wikipedia

Description (4/4)

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.

--Wikipedia

Additional benefit

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.

Prolog for dummies (by a dummy)

Why Prolog?

Backtracking is built into Prolog

Predicates

A Prolog program is a set of predicates.

A predicate consists in one or more clauses

Variables vs atoms

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.

Examples

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

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

?- speaker(xmlamsterdam, X).
X = eric.

8 queens puzzle

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.

--Wikipedia

Notes

Classical XQuery

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>

for $new in 1 to $N where not(f:attack($placed, $new))

In Prolog

% 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 ala Prolog

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>

A Prolog like backtracking library

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
        ()
};

Performances (in seconds)

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

So what?

Verbal arithmetic

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.

--Wikipedia

Canonical example

S E N D
+ M O R E
- - - - - -
= M O N E Y

Shocking!

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

WTF?

Conclusions

Use a spacebar or arrow keys to navigate