scala - 如何在 Scala 中停止回溯？

Question

假设我正在通过回溯解决问题(例如 N-Queen )。如果我想找到唯一一个(第一个)解决方案而不是所有解决方案怎么办。

我想我可以强制执行(例如，使用可变 bool 标志)。我想知道如何在功能上做到这一点。

Answer 1

而 Scala 的 Option将在这里工作，正如其他两个答案所指出的那样，更惯用的功能方法是使用“懒惰列表” - 或 Stream , 在 Scala 中——表示解决方案的集合。

我发现自己在写这样的代码，例如:

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

现在假设我有一个 Board扩展 Node[Board] 的类并且具有 children 的实现方法返回所有有效板和一个附加板。假设它还有一些其他有用的东西，比如 size方法，带有 empty 的伴随对象， 等等。

然后我可以编写以下内容以获得 Stream解决方案:

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

一个 Stream是懒惰的，只评估它的头部，所以现在我们只搜索了足够远的树来找到第一个解决方案。我们可以使用 head 获得此解决方案:

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

管他呢。但如果我想要它们，我也可以获得其他结果:

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

这将搜索足够多的树以找到第十个解决方案，然后停止。
Stream的大优势过 Option方法是，如果我需要，我可以获得额外的结果，而无需为第一个付出更多。