diff options
author | paltherr <paltherr@epfl.ch> | 2003-03-12 11:39:45 +0000 |
---|---|---|
committer | paltherr <paltherr@epfl.ch> | 2003-03-12 11:39:45 +0000 |
commit | d7bb5a3038306b69e0d412bdfc17c3ffde6e51cb (patch) | |
tree | 59b8ff5e4cd1c4de046045f2efcc87ad6dbd1abf /test | |
parent | 0bc479de95f3170aa989062cc4fadbe2c2f3a0dd (diff) | |
download | scala-d7bb5a3038306b69e0d412bdfc17c3ffde6e51cb.tar.gz scala-d7bb5a3038306b69e0d412bdfc17c3ffde6e51cb.tar.bz2 scala-d7bb5a3038306b69e0d412bdfc17c3ffde6e51cb.zip |
- Added queens
Diffstat (limited to 'test')
-rw-r--r-- | test/files/run/queens.check | 4 | ||||
-rw-r--r-- | test/files/run/queens.scala | 49 |
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; + () + } +} |