# Circular Trees

 home  Bib  Algorithms  Bioinfo  FP  Logic  MML  Prog.Lang and the  mmlist

FP
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
window on the wide world:
 The Darwin Awards V: Next Evolution

 Linux  Ubuntu free op. sys. OpenOffice free office suite, ver 3.4+ The GIMP ~ free photoshop Firefox web browser FlashBlock like it says!

 © 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 Sunday, 15-Dec-2019 07:39:19 AEDT.