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

    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
    }


    /*
     * Exceptions als Mittel zur Steuerung des Kontrollflusses waren einmal recht populär.
     * Heute gilt das eher als ein Irrweg.
     * Der Vollständigkeit halber zeigen wir aber doch noch wie die dieser Algorithmus mit Hilfe von
     * Exceptions gestaltet werden kann:
     */
    static func NQueensBTImpEX(_ n: Int) -> [[Int]] {
        var solutions: [[Int]] = []
        var t : [Int] = []

        enum BTException: Error {
            case Backtrack
        }

        func solve() throws {
            if (t.count != 0) && !Ok(t) {
                throw BTException.Backtrack
            }
            if t.count == n {
                solutions.append(t)
            } else {
                for x in 0 ..< n {
                    t.append(x)
                    do {
                        try solve()
                    } catch BTException.Backtrack {}
                    t.removeLast()
                }
            }
        }

        do {
            try solve()
        } catch {
            return []
        }
        return solutions
    }


    /* Ausgabe:
     * [1, 3, 0, 2]
     * [2, 0, 3, 1]
    */
    static func run() {
        print(
            NQueensBTImpEX(4)
                .map( { (l: [Int]) -> [String] in l.map( { (i: Int) -> String in String(i) } ) } )
                .map( { (l: [String]) in "[\(l.joined(separator: ", "))]" } )
                .joined(separator: "\n")
        )
    }

}