50 lines
1.1 KiB
Scala
50 lines
1.1 KiB
Scala
object NQueens {
|
|
|
|
private implicit class RichPair[T](
|
|
pair: (T,T))(
|
|
implicit num: Numeric[T]
|
|
) {
|
|
import num._
|
|
|
|
def safe(x: T, y: T): Boolean =
|
|
pair._1 - pair._2 != abs(x - y)
|
|
}
|
|
|
|
def solve(n: Int): Iterator[Seq[Int]] = {
|
|
(0 to n-1)
|
|
.permutations
|
|
.filter { v =>
|
|
(0 to n-1).forall { y =>
|
|
(y+1 to n-1).forall { x =>
|
|
(x,y).safe(v(x),v(y))
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
def main(args: Array[String]): Unit = {
|
|
val n = args.headOption.getOrElse("8").toInt
|
|
val (solns1, solns2) = solve(n).duplicate
|
|
solns1
|
|
.zipWithIndex
|
|
.foreach { case (soln, i) =>
|
|
Console.out.println(s"Solution #${i+1}")
|
|
output(n)(soln)
|
|
}
|
|
val n_solns = solns2.size
|
|
if (n_solns == 1) {
|
|
Console.out.println("Found 1 solution")
|
|
} else {
|
|
Console.out.println(s"Found $n_solns solutions")
|
|
}
|
|
}
|
|
|
|
def output(n: Int)(board: Seq[Int]): Unit = {
|
|
board.foreach { queen =>
|
|
val row =
|
|
"_|" * queen + "Q" + "|_" * (n-queen-1)
|
|
Console.out.println(row)
|
|
}
|
|
}
|
|
}
|