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

    struct Tuples: Sequence {
        let tupleIterator: TupleIterator

        init(_ n: Int){
            self.tupleIterator = TupleIterator(n)
        }

        struct TupleIterator: IteratorProtocol {
            let n: Int
            var a: [Int]
            var done = false
            var j = 0

            init(_ n: Int) {
                self.n = n
                self.a = [Int](repeating: 0, count: n)
            }

            mutating func next() -> [Int]? {
                if done {
                    return nil
                } else {
                    let res: [Int]? = a
                    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
                    }
                    return res
                }
            }
        }

        func makeIterator() -> TupleIterator {
            tupleIterator
        }
    }

    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
    }

    /*
     * 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:
     */
    static func run() {
        for t in Tuples(8) {
            if Ok(t) {
                print(t.map( { (i) in String(i)} ).joined(separator: ", "))
            }
        }
    }

}