Scala/sandbox/12-nqueens.scala


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
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")
  }
}