Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
A Swift 2 Program That Finds The 92 Distinct Solutions To The Eight Queens Puzzle
//
// 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")
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.