diff options
| -rw-r--r-- | Scala/sandbox/0-main.scala | 1 | ||||
| -rw-r--r-- | Scala/sandbox/12-nqueens.scala | 33 |
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") + } +} |