This page is no longer maintained — Please continue to the home page at

Abstraction for Backtracking

No replies
Joined: 2008-12-18,
User offline. Last seen 45 weeks 4 days ago.


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) =>
case head :: tail =>
if (reject(head)) backtrack
else first(head) match {
case None => backtrack
case Some(f) => path = f :: path

private def backtrack:Unit = path match {
case head :: tail => sibling(head) match {
case None => path = tail
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
} 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 =>{
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]) {

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!

Copyright © 2012 École Polytechnique Fédérale de Lausanne (EPFL), Lausanne, Switzerland