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