Abstraction for Backtracking

Hi!

I asked myself how to abstract backtracking in Scala. The best I could come
up with so far is this quite ugly solution:

trait Backtrackable[S] extends Iterable[S] {

def root:S //the initial partial solution
def reject(s:S):Boolean //should this partial solution be rejected?
def accept(s:S):Boolean //is this a final solution?
def first(s:S):Option[S] //give the first "child" of this partial
solution, if possible
def sibling(s:S):Option[S] //give the next "sibling" of this partial
solution, if possible

def elements():Iterator[S] = new OptionIterator[S] {
var path:List[S] = List(root)

def nextOption:Option[S] = path match {
case Nil => None
case head :: tail if accept(head) && ! reject(head) =>
backtrack
Some(head)
case head :: tail =>
if (reject(head)) backtrack
else first(head) match {
case None => backtrack
case Some(f) => path = f :: path
}
nextOption
}

private def backtrack:Unit = path match {
case head :: tail => sibling(head) match {
case None => path = tail
backtrack
case Some(sib) => path = sib :: tail
}
case Nil =>
}
}

private abstract trait OptionIterator[T] extends Iterator[T] {
def nextOption:Option[T]
private var nextSolution:Option[T] = None
def hasNext():Boolean = {
if (nextSolution.isEmpty) nextSolution = nextOption
! nextSolution.isEmpty
}
def next():T = if (hasNext()) {
val result = nextSolution.getOrElse(error("impossible"))
nextSolution = None
result
} else throw new NoSuchElementException
}
}

...which can be used like that...

object Queens extends Backtrackable[List[Int]] {
def root:List[Int] = List()
def reject(list:List[Int]):Boolean = list match {
case Nil => false
case head :: tail => tail.zip(tail.indices).exists{
case (pos, index) => pos == head ||
Math.abs(pos - head) == index + 1 }
}
def accept(list:List[Int]):Boolean = list.length == 8
def first(list:List[Int]):Option[List[Int]] = Some(1 :: list)
def sibling(list:List[Int]):Option[List[Int]] = list match {
case head :: tail if head < 8 => Some((head + 1) :: tail)
case _ => None
}

def main(args:Array[String]) {
Queens.foreach(println)
}
}

Of course you can write shorter spezialized versions of the eight queens,
but filling the gaps in my solution seems to be a no-brainer. But I wrote
Backtrackable with the eight queens in the back of my head, so it's no
surprise that this use case fits well. I have some doubts that it is good
enough for a wider range of problems.

So I'd like to get some feedback, not only how to redeem me from the sins of
my evil imperative ways but also how to generalize the API. And would be
Stream more convenient than Iterator?

Take care!
Daniel