Examples where trees
(the instances of tree values, not the data type definition)
are self-dependent, recursive, or circular.
"The well known n-queens problem is to place n queens
on an n×n chess board so that no two queens threaten
each other. Each queen must be on a separate row,
column and diagonal and this property is an invariant
that must be maintained as partial solutions are extended.
The fastest imperative solutions [Rohl 1983] are based on
permutation generators. A board is represented by
the permutation of rows that the queens on the columns occupy.
This representation automatically ensures the separate row and column
parts of the invariant. Here we observe that a partial solution
abcde can be extended to a partial solution abcdeX if and
only if bcdeX is also a partial solution and a and X are
on separate diagonals and rows. By using shadows*, X need
only be tested against a's diagonals as the results of
the other diagonal tests against other queens are already encoded in the
shadow tree and do not need to be repeated.[...]" -
The shadow of the partial solution abcde
is bcde which is also a partial solution and
must be in the tree (and closer to the root),
if abcde is in the tree.
1 2 3 4 5
| | | | |
------- ----- ----- ----- -------
3 4 5 4 5 1 5 1 2 1 2 3
| . . . . . | . . . | . etc
| . . . --- |
5 . . 1 2 4
| . | .
2 4 .
|Partial tree of solutions, N=5.
module Queens (module Queens) where
-- NB. element subtree siblings! This is an n-ary tree
data Tree a = Node a (Tree a) (Tree a) | Empty
paths depth t = -- paths from the root of t to given depth
across d ancestors Empty rest = rest
across d ancestors (Node e l r) rest =
down d (e:ancestors) l (across d ancestors r rest)
down d ancestors t rest =
if d >= depth then ancestors:rest
else across (d+1) ancestors t rest
in across 1  t 
member x  = False
member x (y:ys) = x==y || member x ys
build n = -- build tree of solutions
t = toplevel 1 -- note circularity t ~ toplevel -- L.A.
toplevel m = -- note the use of t below
if m > n then Empty
else Node m (f 1 m t) (toplevel (m+1))
f col banned Empty = Empty -- shadowless
f col banned (Node a subtree sibs) =
let others = f col banned sibs
in if member banned [a, a+col, a-col] then others
else Node a (f (col+1) banned subtree) others
queens n = paths n (build n)
window on the wide world:|