Skip to content

Instantly share code, notes, and snippets.

@radustoenescu
Created November 18, 2012 20:42
Show Gist options
  • Save radustoenescu/4107307 to your computer and use it in GitHub Desktop.
Save radustoenescu/4107307 to your computer and use it in GitHub Desktop.
Queens problem in Scala
object Queens {
def main(args: Array[String]): Unit = {
println(queens(9))
}
def queens(n: Int): List[List[Int]] = {
def expandSol(currentSol: List[List[Int]], size: Int): List[List[Int]] = {
if (size == n)
currentSol
else {
expandSol( for {l <- currentSol
newColPostion <- 1 to n
if (! l.contains(newColPostion))
if (l.zipWithIndex.forall {case (col, row) =>
math.abs(col - newColPostion) != math.abs(size - row)})
} yield (l :+ newColPostion), size + 1)
}
}
expandSol(List(List()), 0)
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment