How to stop rollback in Scala?

Question

Suppose I solve a problem (e.g. N-Queen ) with a backtrack. What if I want to find only one (1st) solution, and not all.

I suppose I can do this imperatively (for example, with a mutable boolean flag). I wonder how I can do this functionally.

Answer 1

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

I found myself such code, 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 has an implementation of the children method that returns all valid boards with one additional part. Suppose it has other useful things, such as the size method, companion object with empty , etc.

Then I can write the following to get Stream solutions:

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

A Stream lazy and evaluates only his head, so right now we were only looking for a 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 . . . . . 

It searches for enough of the whole tree to search for 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 one.

Answer 2

Here is a simple case with the search for depth, which stops when he finds what he is looking for. He uses Option , as stated 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(", ")) } 

Using:

 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))) 

Tree t looks like

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

So, we can search for an element and track its nodes:

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

Please note that we do not visit more sites after we find what we are looking for.

Answer 3

Assuming you are using a recursive search function, your function should either return the result (i.e. positioning the queens), or indicate that the result was not found for this branch. Scala There is probably an option / maybe a type, you can use this. This tip applies equally to any functional language.