- Added queens

2 files changed, 53 insertions, 0 deletions

diff --git a/test/files/run/queens.check b/test/files/run/queens.check
new file mode 100644
index 0000000000..d4fcae7ccf
--- /dev/null
+++ b/test/files/run/queens.check
@@ -0,0 +1,4 @@
+Solutions to 1 queens: [[1]]
+Solutions to 2 queens: []
+Solutions to 3 queens: []
+Solutions to 4 queens: [[3,1,4,2],[2,4,1,3]]
diff --git a/test/files/run/queens.scala b/test/files/run/queens.scala
new file mode 100644
index 0000000000..2a705c4892
--- /dev/null
+++ b/test/files/run/queens.scala
@@ -0,0 +1,49 @@
+// $Id$
+
+module M0 {
+  type Placement = List[Int];
+
+  def range(lo: Int, hi: Int): List[Int] =
+    if (lo > hi) List()
+    else lo :: range(lo + 1, hi);
+
+  def abs(x: Int) = if (x < 0) 0 - x else x;
+
+  def queens(n: Int): List[Placement] = {
+    val columns = range(1, n);
+    def placeQueens(row: Int): List[Placement] = {
+      if (row == 0)
+        List(List())
+      else {
+        def isSafe(col: Int, p: Placement, delta: Int): Boolean =
+          p.isEmpty ||
+          (col != p.head &&
+           abs(col - p.head) != delta &&
+           isSafe(col, p.tail, delta + 1));
+
+        for {
+          val placement <- placeQueens(row - 1);
+          val col <- columns;
+          isSafe(col, placement, 1)
+        } yield {
+          col :: placement
+        }
+      }
+    }
+    placeQueens(n);
+  }
+
+  def test = {
+    System.out.println("Solutions to 1 queens: " + queens(1));
+    System.out.println("Solutions to 2 queens: " + queens(2));
+    System.out.println("Solutions to 3 queens: " + queens(3));
+    System.out.println("Solutions to 4 queens: " + queens(4));
+  }
+}
+
+module Test {
+  def main(args: Array[String]): Unit = {
+    M0.test;
+    ()
+  }
+}