Skip to content

Instantly share code, notes, and snippets.

@gopigof
Created August 9, 2020 02:43
Show Gist options
  • Save gopigof/9295de4a5b743d9abcc49e7e23338562 to your computer and use it in GitHub Desktop.
Save gopigof/9295de4a5b743d9abcc49e7e23338562 to your computer and use it in GitHub Desktop.
class nQueens {
def isSafe(col: Int, queens: List[Int]): Boolean = {
val rows = queens.length
val rowsQueens = (rows-1 to 0 by -1).zip(queens)
rowsQueens.forall{
case(r, c) => col != c && math.abs(col - c) != rows - r
}
}
def placeQueens(k: Int): Set[List[Int]] =
if(k == 0) Set(List())
else for{
queens <- placeQueens(k-1)
col <- 0 until n
if isSafe(col, queens)
} yield col :: queens
def show(queens: List[Int]): String = {
val lines = for (col <- queens.reverse)
yield Vector.fill(queens.length)(". ").updated(col, "X ").mkString
"\n" + lines.mkString("\n")
}
}
object nQueens extends nQueens{
val temp: Set[List[Int]] = placeQueens(9)
println("Total generated solutions: "+ temp.size)
temp.map(show).mkString("\n/")
}
@gopigof
Copy link
Author

gopigof commented Aug 9, 2020

This is a potential solution for solving the nQueens problem using functional programming

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment