Re: [q-lang-users] Newbie: Backtracking again

[Albert G. <Dr....@t-...>]

Mele, Greg (MH) wrote:
> I dont understand the queens algorithm enough to see how backtracking 
> works by the fail instruction.
>  
> I would like to have a prolog-like system:
> ie the classic genealogical database
>  
>  
> father(a,b).
> father(b,c).
> father(c,d).
>  
> ancestor(X,Y) :- father (X,Z), ancestor (Z,Y). 

Prolog uses both unification and backtracking to solve problems like 
this. Of course you could do something similar in Q, but it would 
essentially amount to writing a simple Prolog interpreter in Q. I won't 
go into this here, but I'll try to explain the workings of the fail 
construct in the following.

The fail instruction is only useful to implement backtracking, without 
the unification part. It just tells the interpreter that the current 
equation has failed, so that it moves on to the next applicable 
equation. E.g., if you have two equations like this:

foo = writes "foo#1\n" || fail;
foo = writes "foo#2\n";

and you evaluate `foo' then the interpreter first starts evaluating the 
right-hand side of the first rule. After printing out "foo#1", it will 
evaluate the `fail', causing the first rule to fail. Now the second rule 
gets executed, printing "foo#2". So the end result would be the 
following printout:

foo#1
foo#2

(I also often use this trick for debugging purposes. E.g., if you have a 
function bar X with a bunch of defining equations, then simply putting 
an equation like bar X = printf "bar invoked with arg %s\n" (str X) || 
fail; in front of those equations allows you to print bar's argument 
whenever it is invoked, after which the bar X call is evaluated as usual.)

Ok, now how does the queens example work? Let's take a look at the 
crucial definition of the search function (which is invoked as search N 
1 1 [] from queens N):

search N I J P	= write P || writes "\n" if I>N;
		= search N (I+1) 1 (P++[(I,J)]) || fail if safe (I,J) P;
		= search N I (J+1) P if J<N;
		= () otherwise;

N is the size of the board (number of rows/columns), I the current row, 
J the current column and P the list of places (row/column pairs) of the 
queens determined so far (in rows 0..I-1 of the board).

The first equation simply checks whether we've already found a solution 
(I>N implies that #P=N) which is printed out.

The second equation is where the backtracking actually happens. If it is 
safe to place the next queen at position (I,J), w.r.t. the places P we 
already have, then we add (I,J) to P and invoke the algorithm 
recursively starting at column 1 in the next row. After returning from 
the recursive call, the entire subspace of the solution space with the 
given placements P++[(I,J)] has been covered. Now we let the equation 
fail, so that the interpreter moves on to the third equation to try 
other columns for the Ith row.

In any case (i.e., also if the second equation is skipped because (I,J) 
is not safe), the third equation moves on to the next column J+1 and 
invokes the algorithm recursively. This only happens if J<N, otherwise 
there are no other potential placements for the Ith row in which case 
the fourth equation returns ().

Note that the third equation is tail-recursive, i.e., it is essentially 
just a loop which iterates over the different columns for the same row 
I. The second equation is where the algorithm recursively descends into 
the solution subspace for a given initial placement.

Well, I hope that this clarifies the inner workings of the algorithm a 
bit. Tracing the algorithm for a small value of N (either on paper or 
with the interpreter's debugger) also helps. ;-)

Cheers,
Albert

-- 
Dr. Albert Gr"af
Dept. of Music-Informatics, University of Mainz, Germany
Email:  Dr....@t-..., ag...@mu...
WWW:    http://www.musikinformatik.uni-mainz.de/ag