A Swift 2 Program That Finds The 92 Distinct Solutions To The Eight Queens Puzzle

EightQueens

//
//  main.swift
//  EightQueens
//
//  Created by David Steuber on 6/12/15.
//  Copyright © 2015 David Steuber. Donated to the Public Domain.
//
//: Find all solutions to the "Eight Queens Puzzle"
//
// http://en.wikipedia.org/wiki/Eight_queens_puzzle
//
// This is certainly not the best solver. It's not even a good one.

struct Chessboard {
    enum BoardError : ErrorType {
        case noMoreBoards
    }

    private var board: [Int]

    init() {
        board = [0, 0, 0, 0, 0, 0, 0, 0]
    }

    private init(b: Chessboard) throws {
        guard !b.isLast() else {
            throw BoardError.noMoreBoards
        }
        self.board = b.inc()
    }

    func getBoardRep() -> [Int] {
        return board
    }

    private func inc() -> [Int] {
        let maxRank = self.board.count - 1
        var newBoard = self.board
        var cf = true

        for i in 0 ... maxRank {
            if cf {
                newBoard[i]++
                if newBoard[i] > maxRank {
                    newBoard[i] = 0
                    cf = true
                } else {
                    cf = false
                }
            }
        }

        return newBoard
    }

    func nextBoard() -> Chessboard {
        var nextBoard: Chessboard
        do {
            try nextBoard = Chessboard(b: self)
        }
        catch {
            return self
        }
        return nextBoard
    }

    func rankAttacks() -> Bool {
        var retval = false

        for j in 0 ..< board.count {
            let t = board[j]
            for i in j+1 ..< board.count {
                if t == board[i] {
                    retval = true
                    break
                }
            }
            if retval {
                break
            }
        }
        return retval
    }

    func diagonalAttacks() -> Bool {
        var retval = false

        for j in 0 ..< board.count {
            let t = board[j]
            for i in j+1 ..< board.count {
                let m = j - i
                let u = board[i] + m
                let v = board[i] - m
                if t == u || t == v {
                    retval = true
                    break
                }
            }
            if retval {
                break
            }
        }
        return retval
    }

    func isSolution() -> Bool {
        return !(rankAttacks() || diagonalAttacks())
    }

    func isLast() -> Bool {
        return board == [7, 7, 7, 7, 7, 7, 7, 7]
    }
}

var board = Chessboard()
var steps = 0
var solutions = 0

repeat {
    steps++
    board = board.nextBoard()
    if board.isSolution() {
        solutions++
        print("Solution \(solutions): \(board.getBoardRep()) in \(steps) steps")
    }
} while !board.isLast()

print("DONE")