package kapitel_11

/**
 * Beispiel aus
 *
 * - Algorithmen und Datenstrukturen für Dummies
 *   - von Andreas Gogol-Döring und Thomas Letschert
 *   - Verlag Wiley-VCH; Oktober 2019
 *  - Kapitel 11, Probleme totschlagen
 *
 * @author A. Gogol-Döring, Th. Letschert
 */

import scala.collection.mutable.ListBuffer

object AuD_11_08_BacktrackingStateSpace_App extends App {

  /*
   * Der Algorithmus zur Generierung aller Lösungen mit Backtracking
   * kann und wird oft als Suche in einem ``Zustandsraum'' organisiert.
   */

  def Ok(board: List[Int]): Boolean =
    (for (i <- 0 until board.length;
          j <- i+1 until board.length
          ) yield {
      val x = board(i)
      val y = board(j)
      val d = j-i
      ! (x == y || y == x-d || y == x+d)
    }).find( _ == false)
      .getOrElse(true)

  def NQueensBTImp(n: Int): List[List[Int]] = {
    val solutions = new ListBuffer[List[Int]]
    val t : ListBuffer[Int] = new ListBuffer[Int]

    class BTException extends Throwable

    def solve(): Unit = {
      if (t.nonEmpty && !Ok(t.toList)) throw new BTException
      if (t.length == n)
        solutions.append(t.toList)
      else {
        for (x <- 0 until n) {
          t += x
          try {
            solve()
          } catch {
            case _: BTException =>
          }
          t.trimEnd(1)
        }
      }
    }

    solve()

    solutions.toList
  }

  /*
   * Exceptions als Mittel zur Steuerung des Kontrollflusses waren einmal recht populär.
   * Das gilt heute eher als Irrweg.
   * Der Vollständigkeit halber zeigen wir aber doch noch wie die dieser Algorithmus mit Hilfe von
   * Exceptions gestaltet werden kann:
   */

  def NQueensBTImpEX(n: Int): List[List[Int]] = {
    val solutions = new ListBuffer[List[Int]]
    val t : ListBuffer[Int] = new ListBuffer[Int]

    class BTException extends Throwable

    def solve(): Unit = {
      if (t.nonEmpty && !Ok(t.toList)) throw new BTException
      if (t.length == n)
        solutions.append(t.toList)
      else {
        for (x <- 0 until n) {
          t += x
          try {
            solve()
          } catch {
            case _: BTException =>
          }
          t.trimEnd(1)
        }
      }
    }

    solve()

    solutions.toList
  }

  println(
    NQueensBTImp(4)
      .map( l => s"[${l.mkString(", ")}]")
      .mkString(", ")
  ) // => [1, 3, 0, 2], [2, 0, 3, 1]

  println(
    NQueensBTImpEX(4)
      .map( l => s"[${l.mkString(", ")}]")
      .mkString(", ")
  ) // => [1, 3, 0, 2], [2, 0, 3, 1]


}