Skip to content

Instantly share code, notes, and snippets.

@isoiphone
Last active August 29, 2015 14:14
Show Gist options
  • Save isoiphone/a2b88b9b8ccaeab8fcb8 to your computer and use it in GitHub Desktop.
Save isoiphone/a2b88b9b8ccaeab8fcb8 to your computer and use it in GitHub Desktop.
N queens problem in Swift
// jacob schwartz | @isoiphone
// solves N queens problem in swift
// for N=8 there should be 92 possible solutions
// each solution is a list of numbers, these indicate the row to place queen for given column
// for example 0,4,7,5,2,6,1,3 maps to:
// Q-------
// ------Q-
// ----Q---
// -------Q
// -Q------
// ---Q----
// -----Q--
// --Q-----
var N = 8
var numSolutions = 0
var solution = [Int](count: N, repeatedValue: 0)
var inRow = [Bool](count: N, repeatedValue: false)
var inForwardDiag = [Bool](count: 2*N, repeatedValue: false)
var inBackDiag = [Bool](count: 2*N, repeatedValue: false)
func placeQueen(col: Int) {
if col == N {
let line = ",".join(solution.map{"\($0)"})
println("\(++numSolutions): \(line)")
return
}
for row in 0..<N {
if !inRow[row] && !inForwardDiag[row+col] && !inBackDiag[row-col+N] {
solution[col] = row
inRow[row] = true
inForwardDiag[row+col] = true
inBackDiag[row-col+N] = true
placeQueen(col+1)
inRow[row] = false
inForwardDiag[row+col] = false
inBackDiag[row-col+N] = false
}
solution[col] = row
}
}
placeQueen(0)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment