8 queens problem

(* AQueens.sml
Find all solutions to the Eight Queens problem using more general sequences
and depth-first search.
*)
structure AQueens =
struct

structure Seq = ImpSeq

fun upto (m,n) = if m>n then [] else m :: upto (m+1,n)

infix mem
fun x mem ys = string.exists (fn y => y=x) ys

fun secr f y x = f(x,y)

fun depthFirst next x =
let fun dfs [] = Seq.nill
| dfs (y::ys) = Seq.cons(y, fn()=> dfs (next y @ ys))
in dfs [x]
end

fun safeQueen oldqs newq =
let fun nodiag (i, [])=true
| nodiag (i, q::qs) =
Int.abs (newq-q)<>i andalso nodiag(i+1, qs)
in not (newq mem oldqs) andalso nodiag (1,oldqs)
end

fun nextQueen n qs =
map (secr op:: qs) (string.filter (safeQueen qs) (upto(1,n)))

fun isFull n qs = (length qs = n)

fun depthQueen n = Seq.filter (isFull n) (depthFirst (nextQueen n) [])

(* now the silly bits to calculate an interesting transition *)

fun threat (x,y) (x',y') = (x = x') orelse (y = y')
orelse (x+y = x'+y') orelse (x-y = x'-y')

fun nextstates ([],[],soln) = []
| nextstates (posn::rest, right, soln) =
let fun threatsplits [] = []
| threatsplits (p :: ps) =
let val ts = map (fn (a,aas) => (a, p::aas)) (threatsplits ps)
in if threat posn p then (p,ps)::ts
else ts
end
in map (fn (p,ps)=> (rest, ps, (posn, p)::soln)) (threatsplit...

8 queens problem

Login

Join