How to stop backtracking in Scala?

Question

Suppose I am solving a problem (e.g. N-Queen) with backtracking. What if I want to find the only one (the 1-st) solution rather than all of them.

I guess I can do it imperatively (e.g. with a mutable boolean flag). I wonder how I can do it functionally.

Answer 1

While Scala's Option will work here, as two other answers have pointed out, a more idiomatic functional approach would be to use a "lazy list"—or a Stream, in Scala—to represent the set of solutions.

I've found myself writing code like this, for example:

trait Node[A] {
  def children: Stream[A with Node[A]]

  def dfs(f: A => Boolean): Stream[A] = this.children.flatMap {
    child => if (f(child)) Stream(child) else child.dfs(f)
  }
}

Now suppose I have a Board class that extends Node[Board] and that has an implementation of the children method that returns all valid boards with one additional piece. Suppose it also has some other useful stuff, like a size method, a companion object with an empty, etc.

I can then write the following to get a Stream of solutions:

val solutions = Board.empty.dfs(_.size == 8)

A Stream is lazy and only evaluates its head, so right now we've only searched the tree far enough to find the first solution. We can get this solution using head:

scala> solutions.head
res1: Board = 
o . . . . . . .
. . . . o . . .
. . . . . . . o
. . . . . o . .
. . o . . . . .
. . . . . . o .
. o . . . . . .
. . . o . . . .

Or whatever. But I can also get other results if I want them:

scala> solutions(10)
res2: Board = 
. o . . . . . .
. . . . . . o .
. . . . o . . .
. . . . . . . o
o . . . . . . .
. . . o . . . .
. . . . . o . .
. . o . . . . .

This searches just enough more of the tree to find the tenth solution, and then stops.

The big advantage of Stream over the Option approach is that I can get additional results if I need them, without paying more for the first.

Answer 2

Here's a simple case with a depth-first search that stops when it finds what it's looking for. It makes use of Option, as mentioned in Chris K's answer.

case class Tree[A](v: A, subtrees: Tree[A]*) {
  def dfs(s: A): Option[A] = {
    println("visiting " + v)
    subtrees.foldLeft(if(v == s) Some(v) else None)((r, t) => 
      if(r.isDefined) 
        r 
      else 
        t.dfs(s)
    )
  }
  override def toString() = "Tree(%s%s%s)".format(v, if(subtrees.nonEmpty) ", " else "", subtrees.mkString(", "))
}

Usage:

scala> val t = Tree(1, Tree(2, Tree(3), Tree(4)), Tree(5, Tree(6), Tree(7)))
t: Tree[Int] = Tree(1, Tree(2, Tree(3), Tree(4)), Tree(5, Tree(6), Tree(7)))

The tree t looks like

     1
   /   \
  2     5
 / \   / \
3   4 6   7    

So we can search for an element and trace the nodes it visits:

scala> t.dfs(6)
visiting 1
visiting 2
visiting 3
visiting 4
visiting 5
visiting 6
res42: Option[Int] = Some(6)

Notice that we don't visit any more nodes after we find what we're looking for.