Scala学习笔记 之 N皇后问题

学再多理论也比不上自己写一些代码来的实在,今天用Scala来实现一下N皇后问题。个人觉得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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
package me.mzorro.scala.what.nqueues

/**
* Created by Zorro on 7月29日.
*/

/**
* Scala version of the N-Queues problem.
*/
object NQueues {
type Position = (Int, Int)
type Solution = List[Position]

def solve(n: Int) = {

def isSafe(col: Int, current: Solution): Boolean = {
val row = current.length + 1 // put it in next row
current forall { case (r, c) =>
col != c && row - r != (col - c).abs
}
}

def placeQueue(row: Int): List[Solution] = {
assert(row >= 0)
if (row > 0) {
for {
current <- placeQueue(row - 1)
col <- 1 to n
if isSafe(col, current)
} yield (row, col) :: current
} else {
List(Nil)
}
}

val solutions = placeQueue(n)
printSolutions(solutions)

solutions.length
}

private def printSolutions(solutions: List[Solution]) = {
solutions.view.zipWithIndex foreach { case (so, i) =>
val index = i+1
println(s"Solution:$index")
val cols = so.length
so foreach { case (_, col) =>
1 to cols foreach {
case c if c == col => print("*")
case _ => print("-")
}
println()
}
}
}
}

测试代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
package me.mzorro.scala.what.nqueues

import me.mzorro.scala.what.UnitSpec
import org.junit.runner.RunWith
import org.scalatest.junit.JUnitRunner

/**
* Created by Zorro on 7月29日.
*/
@RunWith(classOf[JUnitRunner])
class NQueuesSpec extends UnitSpec {

"4-queue problem" should "have 2 solutions" in {
NQueues.solve(4) should be (2)
}

"8-queue problem" should "have 92 solutions" in {
NQueues.solve(8) should be (92)
}
}