Circular Trees

Examples where trees (the instances of tree values, not the data type definition) are self-dependent, recursive, or circular.

N-Queens

e.g. N=5
    Q    
        Q
  Q      
      Q  
Q        
13524

"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.[...]" - (Allison 1993)
[*] 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             .
|                       .
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
 let
   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
 let
   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

 in t

queens n = paths n (build n)

-- Queens.hs --

More

— L.A. 8/2002