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