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_07_TupelIteratorQueensN_App extends App {

  case class Tuples(n: Int) extends Iterable[Seq[Int]] {

    override def iterator: Iterator[Seq[Int]] = new Iterator[Seq[Int]] {

      val a: Array[Int] = Array.fill(n)(0)
      var done = false
      var j = 0

      override def hasNext: Boolean = !done

      override def next(): Seq[Int] = {
        val res = a.toList
        j = n - 1
        while (j > -1 && a(j) == n - 1) {
          a(j) = 0
          j = j - 1
        }
        if (j == -1)
          done = true
        else {
          a(j) = a(j) + 1
          j = j-1
        }
        res
      }
    }

  }

  /*
   * Damit kann die Suche nach einer Lösung des n-Damen-Problems zwar recht effizient, aber nur
   * völlig erschöpfend ohne Backtracking formuliert werden:
   */

  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)

  for (t <- Tuples(8))
    if (Ok(t.toList)) {
      println(t.mkString(","))
    }

}