Backtracking generic algorithm with demo on the problem of the 8 (or N) queens

Backtracking.scala

import scala.annotation.tailrec

object Backtracking {
  trait Problem {
    type Node

    trait Result
    case object Rejected extends Result
    case object Accepted extends Result
    case class Undecided(children: List[Node]) extends Result

    def root: Node

    def analyse(node: Node): Result

    // gets the first solution only
    @tailrec
    final def solve(candidates: List[Node] = List(root)): Option[Node] = candidates match {
      case candidate :: tail =>
        analyse(candidate) match {
          case Accepted => Some(candidate)
          case Rejected =>
            Console.err.println(s"Rejected : $candidate")
            solve(tail)
          case Undecided(children) =>
            Console.err.println(s"Undecided with ${children.size} children: $candidate")
            solve(children ::: tail)
        }
      case Nil => None
    }
  }
}


object DemoNQueens extends App {
  case class NodeNQueens(cols: List[Int] = Nil, size: Int = 8) {
    def clashes: Boolean = {
      cols.toSet.size != cols.size ||
        cols.zipWithIndex.combinations(2).exists { case List((r1, c1), (r2, c2)) => math.abs(r1 - r2) == math.abs(c1 - c2) }
    }
 
    def children: List[NodeNQueens] = for {
      c <- (0 to size - 1).toList.diff(cols)
    } yield NodeNQueens(c :: cols, size = size)
 
    override def toString = (for (c <- cols) yield "." * c + "X" + "." * (size - 1 - c)).mkString("\n", "\n", "\n")
  }
 
  object ProblemNQueens extends Backtracking.Problem {
    type Node = NodeNQueens
 
    def root = NodeNQueens(size = 15)
 
    def analyse(node: NodeNQueens) = {
      if (node.clashes) Rejected
      else if (node.cols.size == node.size) Accepted
      else Undecided(node.children)
    }
  }
  println(ProblemNQueens.solve())
}