From 12a9fca3908dc0b9bf7d51abd37db542b4600bb1 Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?J=C3=A9r=C3=A9my=20Zurcher?= <jeremy@asynk.ch>
Date: Fri, 17 May 2013 16:17:59 +0200
Subject: Scala : add sandbox 12-nqueens

---
 Scala/sandbox/0-main.scala     |  1 +
 Scala/sandbox/12-nqueens.scala | 33 +++++++++++++++++++++++++++++++++
 2 files changed, 34 insertions(+)
 create mode 100644 Scala/sandbox/12-nqueens.scala

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")
+  }
+}
-- 
cgit v1.1-2-g2b99