Scala : add sandbox 12-nqueens

2 files changed, 34 insertions, 0 deletions

diff --git a/Scala/sandbox/0-main.scala b/Scala/sandbox/0-main.scala
index 4414f12..f6d6652 100644
--- a/Scala/sandbox/0-main.scala
+++ b/Scala/sandbox/0-main.scala
@@ -14,5 +14,6 @@ object Main  extends App {
     Lists.run
     MergeSort.run
     Pack.run
+    NQueens.run
 
 }
diff --git a/Scala/sandbox/12-nqueens.scala b/Scala/sandbox/12-nqueens.scala
new file mode 100644
index 0000000..3b9c60a
--- /dev/null
+++ b/Scala/sandbox/12-nqueens.scala
@@ -0,0 +1,33 @@
+object NQueens
+{
+  def queens(n: Int): Set[List[Int]] = {
+    def isSafe(col: Int, queens: List[Int]): Boolean = {
+      val row = queens.length
+      val queensWithRows = (row - 1 to 0 by -1) zip queens
+      queensWithRows forall {
+        case (r, c) => col != c && math.abs(col - c) != row - 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
+    placeQueens(n)
+  }
+
+  def showQueens(queens: List[Int]): String = {
+    val lines =
+      for (col <- queens.reverse)
+      yield Vector.fill(queens.length)("* ").updated(col, "X ").mkString
+    "\n" + (lines mkString "\n")
+  }
+
+  def run = {
+    println("NQueens")
+    println((queens(8) take 3 map showQueens) mkString "\n")
+  }
+}