package kapitel_11

import scala.annotation.tailrec

/**
 * 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
 */

object AuD_11_06_NQueensBackTtrack_App extends App {

  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 FourQueensBT: List[Int] = {
    for (
      p0 <- 0 until 4;
      p1 <- 0 until 4
      if Ok(List(p0, p1))
    ) {
      for (p2 <- 0 until 4
           if Ok(List(p0, p1, p2))
           ) {
        for (p3 <- 0 until 4
             if Ok(List(p0, p1, p2, p3))
             ) {
          return List(p0, p1, p2, p3)
        }
      }
    }
    throw new NoSuchElementException("No solution found")
  }

  /*
   * In der allgemeinen Variante, n ist parameter statt Wert:
   */

  def QueensNBT(n: Int): List[Int] =
    LoopsBT(n, n, List(Nil)).headOption.getOrElse(throw new NoSuchElementException)

  @tailrec
  def LoopsBT(count: Int, limit: Int, acc: List[List[Int]]): List[List[Int]] =
    if (count == 0) {
      acc.filter( Ok )
    } else {
      LoopsBT(count-1,
        limit,
        for (
          board <- acc;
          x <- 0 until limit
          if Ok(board ++ List(x))
        ) yield board ++ List(x)
      )
    }

  /*
   * In einer weniger ambitioniert funktionalen Variante wird der Akkumulator in einer globalen Variablen
   * verwaltet und eine explizite Schleife eingesetzt und statt alle möglichen Pfade in einem Akkumulator-Parameter
   * aufzusammeln, verwenden wir eine globale Variable $acc$ die von \Al{LoopsBT} gefüllt wird.
   * Ein Pfad entspricht einen ganz oder teilweise gefüllten Brett.
   * Statt alle akzeptablen Bretter in $acc$ durch die Rekursionen zu schleppen, wird ein Brett (Pfad) in jeder
   * Rekursionsstufe ausgebaut und wenn es vollständig ist, in $acc$ gespeichert.  Das ergibt einen etwas anderen
   * in seiner Grundstruktur imperativen Algorithmus, der mit persistenten Listen als Werten der Variablen
   * board arbeitet:
   */

  def QueensNBT_MoreImperative(n: Int): List[Int] = {

    var acc: List[List[Int]] = Nil

    // NICHT @tailrec
    def LoopsBT(count: Int, limit: Int, board: List[Int]): Unit = {
      if (count == 0) {
        acc = acc ++ List(board)
      } else {
        for (x <- 0 until limit) {
          if (Ok(board ++ List(x))) {
            LoopsBT(count-1, limit, board ++ List(x))
          }
        }
      }
    }

    LoopsBT(n, n, Nil)

    acc.headOption.getOrElse(throw new NoSuchElementException)
  }


  println(FourQueensBT.mkString(", ")) // 1, 3, 0, 2
  println(QueensNBT(4).mkString(", ")) // 1, 3, 0, 2
  println(QueensNBT_MoreImperative(4).mkString(", ")) // 1, 3, 0, 2

}