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

struct AuD_11_06_NQueensBackTtrack {

    static func Ok(_ board: [Int]) -> Bool {
        for i in 0 ..< board.count {
            for j in i + 1 ..< board.count {
                let x = board[i]
                let y = board[j]
                let d = j - i
                if (x == y || y == x - d || y == x + d) {
                    return false
                }
            }
        }
        return true
    }

    /*
     * Backtracking: Breche die Suche ab wenn der eingeschlage Weg im Lösungsbaum
     * sich als ausichtslos zeigt.
     */
    static func FourQueensBT() -> [Int] {
        for p0 in 0..<4 {
            for p1 in 0..<4 {
                if Ok([p0, p1]) {
                    for p2 in 0..<4 {
                        if Ok([p0, p1, p2]) {
                            for p3 in 0..<4 {
                                if Ok([p0, p1, p2, p3]) {
                                    return [p0, p1, p2, p3]
                                }
                            }
                        }
                    }
                }
            }
        }
        return []
    }

    /*
     * Backtracking, wenn verschachtelte Schleifen nicht möglich sind:
     */
    static func QueensNBT(_ n: Int) -> [Int] {

        func LoopsBT(_ count: Int, _ limit: Int, _ acc: [[Int]]) -> [Int]? {
            if (count == 0) {
                return acc.filter( { (board) in Ok(board)  } ).first
            } else {
                return LoopsBT(
                    count-1,
                    limit,
                    acc.flatMap( {
                        (board) in (0 ..< limit)
                            //.filter( { (x) in Ok(board + [x]) } )
                            .map( { (x) in board + [x] } ) } )
                )
            }
        }
        return LoopsBT(n, n, [[]]) ?? []
    }

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

    static func QueensNBT_MoreImperative(_ n: Int) -> [Int] {
        var acc: [[Int]] = []

        func Loops(_ count: Int, _ limit: Int, _ board: [Int]) {
            if count == 0 {
                    acc = acc + [board]
            } else {
                for x in 0 ..< limit {
                    if Ok(board + [x]) {
                        Loops(count - 1, limit, board + [x])
                    }
                }
            }
        }

        Loops(n, n, [])
        return acc.count > 0 ? acc[0] : []
    }

    static func run() {
        print(FourQueensBT().map( { (i) in String(i)} ).joined(separator: ", ")) // 1, 3, 0, 2
        print(QueensNBT(4).map( { (i) in String(i)} ).joined(separator: ", ")) // 1, 3, 0, 2
        print(QueensNBT_MoreImperative(4).map( { (i) in String(i)} ).joined(separator: ", ")) // 1, 3, 0, 2
    }

}