|
4
|
1 |
import scala.util._
|
|
5
|
2 |
type Pos = (Int, Int)
|
|
4
|
3 |
|
|
5
|
4 |
|
|
|
5 |
def print_board(n: Int)(steps: List[Pos]): Unit = {
|
|
4
|
6 |
for (i <- 0 until n) {
|
|
|
7 |
for (j <- 0 until n) {
|
|
|
8 |
print(f"${steps.indexOf((i, j))}%3.0f ")
|
|
|
9 |
}
|
|
|
10 |
println
|
|
|
11 |
}
|
|
|
12 |
//readLine()
|
|
|
13 |
System.exit(0)
|
|
|
14 |
}
|
|
|
15 |
|
|
5
|
16 |
def add_pair(x: Pos)(y: Pos) =
|
|
4
|
17 |
(x._1 + y._1, x._2 + y._2)
|
|
|
18 |
|
|
5
|
19 |
def is_legal(n: Int)(x: Pos) =
|
|
4
|
20 |
0 <= x._1 && 0 <= x._2 && x._1 < n && x._2 < n
|
|
|
21 |
|
|
5
|
22 |
def moves(n: Int)(x: Pos): List[Pos] = {
|
|
4
|
23 |
List((1, 2),(2, 1),(2, -1),(1, -2),
|
|
|
24 |
(-1, -2),(-2, -1),(-2, 1),(-1, 2)).map(add_pair(x)).filter(is_legal(n))
|
|
|
25 |
}
|
|
|
26 |
|
|
5
|
27 |
def ordered_moves(n: Int)(steps: List[Pos])(x : Pos): List[Pos] =
|
|
|
28 |
moves(n)(x).sortBy((x: Pos) => moves(n)(x).filterNot(steps.contains(_)).length)
|
|
4
|
29 |
|
|
|
30 |
moves(8)(1,3)
|
|
|
31 |
ordered_moves(8)(Nil)(1,3)
|
|
|
32 |
ordered_moves(8)(List((2, 4), (2, 6)))(1,3)
|
|
|
33 |
|
|
5
|
34 |
// non-circle tour
|
|
|
35 |
def tour(n: Int)(steps: List[Pos]): Unit = {
|
|
4
|
36 |
if (steps.length == n * n)
|
|
|
37 |
print_board(n)(steps)
|
|
|
38 |
else
|
|
|
39 |
for (x <- moves(n)(steps.head); if (!steps.contains(x))) tour(n)(x :: steps)
|
|
|
40 |
}
|
|
|
41 |
|
|
|
42 |
val n = 8
|
|
|
43 |
println(s"simple tour: n = $n")
|
|
|
44 |
|
|
|
45 |
for (i <- 0 until n; j <- 0 until n) tour(n)(List((i, j)))
|