|
1 |
1 // Part 1 about finding and counting Knight's tours |
2 // Part 1 about finding and counting Knight's tours |
2 //================================================== |
3 //================================================== |
3 |
4 |
4 object CW7a { |
5 object CW7a extends App{ |
5 |
6 |
6 type Pos = (Int, Int) // a position on a chessboard |
7 type Pos = (Int, Int) // a position on a chessboard |
7 type Path = List[Pos] // a path...a list of positions |
8 type Path = List[Pos] // a path...a list of positions |
8 |
9 |
9 def print_board(dim: Int, path: Path): Unit = { |
10 //(1a) Complete the function that tests whether the position |
10 println |
11 // is inside the board and not yet element in the path. |
11 for (i <- 0 until dim) { |
12 |
12 for (j <- 0 until dim) { |
13 //def is_legal(dim: Int, path: Path)(x: Pos) : Boolean = ... |
13 print(f"${path.reverse.indexOf((j, dim - i - 1))}%3.0f ") |
14 |
14 } |
15 def is_legal(dim: Int, path: Path)(x: Pos) : Boolean = { |
15 println |
16 |
16 } |
17 // if ((x._1<dim && x._2<dim) && (x._1>0 || x._2>0)) false else !path.contains(x) |
|
18 |
|
19 if (x._1 < 0 || x._2 < 0) false |
|
20 else if (x._1 < dim && x._2 < dim && !path.contains(x)) true |
|
21 else false |
|
22 |
|
23 |
17 } |
24 } |
18 |
|
19 def add_pair(x: Pos)(y: Pos): Pos = |
|
20 (x._1 + y._1, x._2 + y._2) |
|
21 |
|
22 def is_legal(dim: Int, path: Path)(x: Pos): Boolean = |
|
23 0 <= x._1 && 0 <= x._2 && x._1 < dim && x._2 < dim && !path.contains(x) |
|
24 |
|
25 assert(is_legal(8, Nil)((3,4)) == true) |
|
26 assert(is_legal(8, List((4,1), (1,0)))((4,1)) == false) |
|
27 assert(is_legal(2, Nil)((0,0)) == true) |
|
28 |
25 |
29 |
26 |
30 |
27 |
31 def moves(x: Pos): List[Pos] = |
28 def legal_moves(dim: Int, path: Path, x: Pos) : List[Pos] = { |
32 List(( 1, 2),( 2, 1),( 2, -1),( 1, -2), |
|
33 (-1, -2),(-2, -1),(-2, 1),(-1, 2)).map(add_pair(x)) |
|
34 |
|
35 def legal_moves(dim: Int, path: Path, x: Pos): List[Pos] = |
|
36 moves(x).filter(is_legal(dim, path)) |
|
37 |
|
38 def count_tours(dim: Int, path: Path): Int = { |
|
39 if (path.length == dim * dim) 1 |
|
40 else |
|
41 (for (x <- legal_moves(dim, path, path.head)) yield count_tours(dim, x::path)).sum |
|
42 } |
|
43 |
|
44 def count_tours(dim: Int, path : Path) : Int = { |
|
45 |
29 |
46 if (path.length == dim * dim) {1} |
30 val allPossibleMoves = List((x._1+1, x._2+2), (x._1+2, x._2+1), (x._1+2, x._2-1), (x._1+1, x._2-2), (x._1-1, x._2-2), (x._1-2, x._2-1), (x._1-2, x._2+1), (x._1-1, x._2+2)); |
47 else |
31 |
48 val x = for (m <- legal_moves(dim,path,path.head)) yield { |
32 //val finalList = allPossibleMoves.filter((a=>a._1<dim && a._2<dim && x._1 >= 0 && a._2 >= 0)); |
|
33 |
|
34 val finalList = for(pos<-allPossibleMoves if(is_legal(dim,path)(pos))) yield pos; |
|
35 |
|
36 // println("Space in board: " + dim*dim + " for dim: " + dim) |
|
37 |
|
38 |
|
39 finalList.toList; |
49 |
40 |
50 count_tours(dim,m::path) |
|
51 } |
|
52 x.sum |
|
53 |
41 |
54 } |
42 } |
55 |
43 |
56 def enum_tours(dim: Int, path: Path): List[Path] = { |
44 println(legal_moves(8, Nil, (2,2))) |
57 if (path.length == dim * dim) List(path) |
45 println(legal_moves(8, Nil, (7,7))) |
58 else |
46 println(legal_moves(8, List((4,1), (1,0)), (2,2))) |
59 (for (x <- legal_moves(dim, path, path.head)) yield enum_tours(dim, x::path)).flatten |
47 println(legal_moves(8, List((6,6)), (7,7))) |
|
48 println(legal_moves(1, Nil, (0,0))) |
|
49 println(legal_moves(2, Nil, (0,0))) |
|
50 println(legal_moves(3, Nil, (0,0))) |
|
51 |
|
52 println("=================================================================================") |
|
53 println("================================Comparision output===============================") |
|
54 println("=================================================================================") |
|
55 |
|
56 println(legal_moves(8, Nil, (2,2)) == List((3,4), (4,3), (4,1), (3,0), (1,0), (0,1), (0,3), (1,4))) |
|
57 println(legal_moves(8, Nil, (7,7)) == List((6,5), (5,6))) |
|
58 println(legal_moves(8, List((4,1), (1,0)), (2,2)) == List((3,4), (4,3), (3,0), (0,1), (0,3), (1,4))) |
|
59 println(legal_moves(8, List((6,6)), (7,7)) == List((6,5), (5,6))) |
|
60 println(legal_moves(1, Nil, (0,0)) == Nil) |
|
61 println(legal_moves(2, Nil, (0,0)) == Nil) |
|
62 println(legal_moves(3, Nil, (0,0)) == List((1,2), (2,1))) |
|
63 |
|
64 |
|
65 def count_tours(dim: Int, path: Path) : Int = { |
|
66 |
|
67 val allMovesFromCurrentPosition = legal_moves(dim, path, path.head); |
|
68 |
|
69 if (path.length == dim*dim) 1 else { |
|
70 |
|
71 if (allMovesFromCurrentPosition.size == 0 ) 0 else { |
|
72 |
|
73 allMovesFromCurrentPosition.map( element => count_tours(dim, element::path)).sum |
|
74 |
|
75 |
|
76 } |
|
77 |
|
78 } |
|
79 |
|
80 } |
|
81 |
|
82 |
|
83 |
|
84 println ( count_tours(5, List((0,0))) ) |
|
85 |
|
86 def enum_tours(dim: Int, path: Path) : List[Path] = { |
|
87 |
|
88 val allMovesFromCurrentPosition = legal_moves(dim, path, path.head); |
|
89 |
|
90 if (path.length == dim*dim) List(path) else { |
|
91 |
|
92 allMovesFromCurrentPosition.map( element => enum_tours(dim, element::path)).flatten ; |
|
93 |
|
94 |
|
95 } |
|
96 } |
|
97 println ( enum_tours(6, List((0,2))).size) |
60 } |
98 } |
61 |
99 |
62 def count_all_tours(dim: Int) = { |
|
63 for (i <- (0 until dim).toList; |
|
64 j <- (0 until dim).toList) yield count_tours(dim, List((i, j))) |
|
65 } |
|
66 |
100 |
67 def enum_all_tours(dim: Int): List[Path] = { |
|
68 (for (i <- (0 until dim).toList; |
|
69 j <- (0 until dim).toList) yield enum_tours(dim, List((i, j)))).flatten |
|
70 } |
|
71 |
101 |
72 /* |
|
73 for (dim <- 1 to 5) { |
|
74 println(s"${dim} x ${dim} " + count_tours(dim, List((0, 0)))) |
|
75 } |
|
76 |
102 |
77 for (dim <- 1 to 5) { |
|
78 println(s"${dim} x ${dim} " + count_all_tours(dim)) |
|
79 } |
|
80 |
103 |
81 for (dim <- 1 to 5) { |
104 |
82 val ts = enum_tours(dim, List((0, 0))) |
105 |
83 println(s"${dim} x ${dim} ") |
106 //(1b) Complete the function that calculates for a position |
84 if (ts != Nil) { |
107 // all legal onward moves that are not already in the path. |
85 print_board(dim, ts.head) |
108 // The moves should be ordered in a "clockwise" manner. |
86 println(ts.head) |
109 |
87 } |
110 //def legal_moves(dim: Int, path: Path, x: Pos) : List[Pos] = ... |
88 } |
|
89 */ |
|
90 |
111 |
91 } |
112 |
|
113 |
|
114 |
|
115 //some test cases |
|
116 // |
|
117 //assert(legal_moves(8, Nil, (2,2)) == |
|
118 // List((3,4), (4,3), (4,1), (3,0), (1,0), (0,1), (0,3), (1,4))) |
|
119 //assert(legal_moves(8, Nil, (7,7)) == List((6,5), (5,6))) |
|
120 //assert(legal_moves(8, List((4,1), (1,0)), (2,2)) == |
|
121 // List((3,4), (4,3), (3,0), (0,1), (0,3), (1,4))) |
|
122 //assert(legal_moves(8, List((6,6)), (7,7)) == List((6,5), (5,6))) |
|
123 |
|
124 |
|
125 //(1c) Complete the two recursive functions below. |
|
126 // They exhaustively search for knight's tours starting from the |
|
127 // given path. The first function counts all possible tours, |
|
128 // and the second collects all tours in a list of paths. |
|
129 |
|
130 //def count_tours(dim: Int, path: Path) : Int = ... |
|
131 |
|
132 |
|
133 //def enum_tours(dim: Int, path: Path) : List[Path] = ... |