| author | Christian Urban <christian dot urban at kcl dot ac dot uk> |
| Mon, 31 Oct 2016 10:43:11 +0000 | |
| changeset 2 | e0ec73c462c7 |
| parent 1 | b595d654cb2d |
| child 3 | 575a5c07c7fe |
| permissions | -rw-r--r-- |
|
0
02f53f76f828
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
1 |
|
|
02f53f76f828
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
2 |
|
|
02f53f76f828
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
3 |
def print_board(n: Int)(steps: List[(Int, Int)]): Unit = {
|
|
02f53f76f828
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
4 |
for (i <- 0 until n) {
|
|
02f53f76f828
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
5 |
for (j <- 0 until n) {
|
|
02f53f76f828
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
6 |
print(f"${steps.indexOf((i, j))}%2.0f ")
|
|
02f53f76f828
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
7 |
} |
|
02f53f76f828
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
8 |
println |
|
02f53f76f828
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
9 |
} |
|
02f53f76f828
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
10 |
//readLine() |
|
02f53f76f828
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
11 |
System.exit(0) |
|
02f53f76f828
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
12 |
} |
|
02f53f76f828
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
13 |
|
|
02f53f76f828
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
14 |
def add_pair(x: (Int, Int))(y: (Int, Int)) = |
|
02f53f76f828
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
15 |
(x._1 + y._1, x._2 + y._2) |
|
02f53f76f828
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
16 |
|
|
02f53f76f828
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
17 |
def is_legal(n: Int)(x: (Int, Int)) = |
|
02f53f76f828
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
18 |
0 <= x._1 && 0 <= x._2 && x._1 < n && x._2 < n |
|
02f53f76f828
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
19 |
|
|
02f53f76f828
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
20 |
def moves(n: Int)(x: (Int, Int)): List[(Int, Int)] = {
|
|
1
b595d654cb2d
typo
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
0
diff
changeset
|
21 |
List((1, 2),(2, 1),(2, -1),(1, -2), |
|
b595d654cb2d
typo
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
0
diff
changeset
|
22 |
(-1, -2),(-2, -1),(-2, 1),(-1, 2)).map(add_pair(x)).filter(is_legal(n)) |
|
0
02f53f76f828
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
23 |
} |
|
02f53f76f828
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
24 |
|
|
02f53f76f828
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
25 |
def tour(n: Int)(steps: List[(Int, Int)]): Unit = {
|
|
02f53f76f828
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
26 |
if (steps.length == n * n && moves(n)(steps.head).contains(steps.last)) |
|
02f53f76f828
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
27 |
print_board(n)(steps) |
|
02f53f76f828
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
28 |
else |
|
2
e0ec73c462c7
typo
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
1
diff
changeset
|
29 |
for (x <- moves(n)(steps.head); if (!steps.contains(x))) tour(n)(x :: steps) |
|
0
02f53f76f828
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
30 |
} |
|
02f53f76f828
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
31 |
|
|
02f53f76f828
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
32 |
val n = 6 |
|
02f53f76f828
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
33 |
|
|
02f53f76f828
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
34 |
println("started")
|
|
02f53f76f828
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
35 |
for (i <- 0 until n; j <- 0 until n) tour(n)(List((i, j))) |
|
02f53f76f828
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
36 |
println("finished")
|