Circular Trees

home1 home2
 Bib
 Algorithms
 Bioinfo
 FP
 Logic
 MML
 Prog.Lang
and the
 Book

FP
 Haskell
  Haskell98
   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)

More


L.A. 8/2002
Coding Ockham's Razor, L. Allison, Springer

A Practical Introduction to Denotational Semantics, L. Allison, CUP

Linux
 Ubuntu
free op. sys.
OpenOffice
free office suite
The GIMP
~ free photoshop
Firefox
web browser

© L. Allison   http://www.allisons.org/ll/   (or as otherwise indicated),
Faculty of Information Technology (Clayton), Monash University, Australia 3800 (6/'05 was School of Computer Science and Software Engineering, Fac. Info. Tech., Monash University,
was Department of Computer Science, Fac. Comp. & Info. Tech., '89 was Department of Computer Science, Fac. Sci., '68-'71 was Department of Information Science, Fac. Sci.)
Created with "vi (Linux + Solaris)",  charset=iso-8859-1,  fetched Friday, 29-Mar-2024 16:11:48 AEDT.