Skip to content

Instantly share code, notes, and snippets.

@cgopalan
Created October 6, 2011 03:26
Show Gist options
  • Save cgopalan/1266433 to your computer and use it in GitHub Desktop.
Save cgopalan/1266433 to your computer and use it in GitHub Desktop.
Function isSafe for NQueens problem
object NQueensProblem {
def queens(n: Int): List[List[Int]] = {
def placeQueens(k: Int): List[List[Int]] =
if (k == 0) List(List())
else for { queens <- placeQueens(k - 1)
column <- List.range(1, n + 1)
if isSafe(column, queens, 1)} yield column :: queens
placeQueens(n)
}
def isSafe(col: Int, queens: List[Int], delta: Int): Boolean = queens match {
case Nil => true
case x :: xs => col != x && col != x - delta && col != x + delta &&
isSafe(col, xs, delta + 1)
}
def main(args: Array[String]) {
println ("Solving nqueens: ")
val x = queens(8)
println("Number of solutions: " + x.length)
println(x)
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment