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

object AuD_11_03_EightQueensExhaustiveSearch_App extends App {

  /*
   * Es lebe die Kraft der geschachtelten Schleifen.
   */

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

  println(EightQueens)

}