diff options
author | paltherr <paltherr@epfl.ch> | 2003-07-18 11:17:08 +0000 |
---|---|---|
committer | paltherr <paltherr@epfl.ch> | 2003-07-18 11:17:08 +0000 |
commit | 5f77ce3a39f276eea29df1b09926553364d80e1d (patch) | |
tree | fb35a381874e7bc20950af7437fe068e08d25c45 /test/files/run/Course-2002-05.scala | |
parent | 5a64e1706c57b41a8b4199387efd081d6aabaf08 (diff) | |
download | scala-5f77ce3a39f276eea29df1b09926553364d80e1d.tar.gz scala-5f77ce3a39f276eea29df1b09926553364d80e1d.tar.bz2 scala-5f77ce3a39f276eea29df1b09926553364d80e1d.zip |
- Merged queens into Course-2002-05
Diffstat (limited to 'test/files/run/Course-2002-05.scala')
-rw-r--r-- | test/files/run/Course-2002-05.scala | 50 |
1 files changed, 48 insertions, 2 deletions
diff --git a/test/files/run/Course-2002-05.scala b/test/files/run/Course-2002-05.scala index 2d8a146624..46b4acc349 100644 --- a/test/files/run/Course-2002-05.scala +++ b/test/files/run/Course-2002-05.scala @@ -115,6 +115,12 @@ object M2 { object M3 { + def abs(x: int) = if (x < 0) 0 - x else x; + + def range(lo: Int, hi: Int): List[Int] = + if (lo > hi) List() + else lo :: range(lo + 1, hi); + type Placement = List[Pair[int,int]]; def queens(n: int): List[Placement] = { @@ -139,11 +145,50 @@ object M3 { placeQueens(n) } - def range(lo: int, hi: int): List[int] = + def test = { + System.out.println("queens(1) = " + queens(1)); + System.out.println("queens(2) = " + queens(2)); + System.out.println("queens(3) = " + queens(3)); + System.out.println("queens(4) = " + queens(4)); + System.out.println(); + } +} + +//############################################################################ + +object M4 { + + def abs(x: int) = if (x < 0) 0 - x else x; + + 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; + type Placement = List[Int]; + + 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("queens(1) = " + queens(1)); @@ -162,6 +207,7 @@ object Test { M1.test; M2.test; M3.test; + M4.test; () } } |