1 // Preliminary Part about finding Knight's tours |
1 // Preliminary Part about finding Knight's tours |
2 //=============================================== |
2 //=============================================== |
3 |
3 |
4 |
4 |
5 object CW8a { |
5 object CW9a { |
6 |
6 |
7 // If you need any auxiliary function, feel free to |
7 // If you need any auxiliary function, feel free to |
8 // implement it, but do not make any changes to the |
8 // implement it, but do not make any changes to the |
9 // templates below. Also have a look whether the functions |
9 // templates below. Also have a look whether the functions |
10 // at the end are of any help. |
10 // at the end are of any help. |
15 type Path = List[Pos] // a path...a list of positions |
15 type Path = List[Pos] // a path...a list of positions |
16 |
16 |
17 //(1) Complete the function that tests whether the position x |
17 //(1) Complete the function that tests whether the position x |
18 // is inside the board and not yet element in the path. |
18 // is inside the board and not yet element in the path. |
19 |
19 |
20 //def is_legal(dim: Int, path: Path, x: Pos) : Boolean = ... |
20 def is_legal(dim: Int, path: Path, x: Pos) : Boolean = ??? |
21 |
21 |
22 |
22 |
23 |
23 |
24 //(2) Complete the function that calculates for a position x |
24 //(2) Complete the function that calculates for a position x |
25 // all legal onward moves that are not already in the path. |
25 // all legal onward moves that are not already in the path. |
26 // The moves should be ordered in a "clockwise" manner. |
26 // The moves should be ordered in a "clockwise" manner. |
27 |
27 |
28 |
28 def legal_moves(dim: Int, path: Path, x: Pos) : List[Pos] = ??? |
29 //def legal_moves(dim: Int, path: Path, x: Pos) : List[Pos] = ... |
|
30 |
29 |
31 |
30 |
32 //some testcases |
31 //some testcases |
33 // |
32 // |
34 //assert(legal_moves(8, Nil, (2,2)) == |
33 //assert(legal_moves(8, Nil, (2,2)) == |
42 //(3) Complete the two recursive functions below. |
41 //(3) Complete the two recursive functions below. |
43 // They exhaustively search for knight's tours starting from the |
42 // They exhaustively search for knight's tours starting from the |
44 // given path. The first function counts all possible tours, |
43 // given path. The first function counts all possible tours, |
45 // and the second collects all tours in a list of paths. |
44 // and the second collects all tours in a list of paths. |
46 |
45 |
47 //def count_tours(dim: Int, path: Path) : Int = ... |
46 def count_tours(dim: Int, path: Path) : Int = ??? |
48 |
47 |
49 //def enum_tours(dim: Int, path: Path) : List[Path] = ... |
48 def enum_tours(dim: Int, path: Path) : List[Path] = ??? |
50 |
49 |
51 |
50 |
52 //(4) Implement a first-function that finds the first |
51 //(4) Implement a first-function that finds the first |
53 // element, say x, in the list xs where f is not None. |
52 // element, say x, in the list xs where f is not None. |
54 // In that case Return f(x), otherwise None. If possible, |
53 // In that case Return f(x), otherwise None. If possible, |
55 // calculate f(x) only once. |
54 // calculate f(x) only once. |
56 |
55 |
57 //def first(xs: List[Pos], f: Pos => Option[Path]) : Option[Path] = ... |
56 def first(xs: List[Pos], f: Pos => Option[Path]) : Option[Path] = ??? |
58 |
57 |
59 |
58 |
60 // testcases |
59 // testcases |
61 // |
60 // |
62 //def foo(x: (Int, Int)) = if (x._1 > 3) Some(List(x)) else None |
61 //def foo(x: (Int, Int)) = if (x._1 > 3) Some(List(x)) else None |
67 |
66 |
68 //(5) Implement a function that uses the first-function from (5) for |
67 //(5) Implement a function that uses the first-function from (5) for |
69 // trying out onward moves, and searches recursively for a |
68 // trying out onward moves, and searches recursively for a |
70 // knight tour on a dim * dim-board. |
69 // knight tour on a dim * dim-board. |
71 |
70 |
72 |
71 def first_tour(dim: Int, path: Path) : Option[Path] = ??? |
73 //def first_tour(dim: Int, path: Path) : Option[Path] = ... |
|
74 |
72 |
75 |
|
76 |
|
77 |
|
78 |
73 |
79 |
74 |
80 /* Helper functions |
75 /* Helper functions |
81 |
76 |
82 |
77 |
93 // time_needed(count_tours(dim, List((0, 0)))) |
88 // time_needed(count_tours(dim, List((0, 0)))) |
94 // in order to print out the time that is needed for |
89 // in order to print out the time that is needed for |
95 // running count_tours |
90 // running count_tours |
96 |
91 |
97 |
92 |
98 |
|
99 |
|
100 // for printing a board |
93 // for printing a board |
101 def print_board(dim: Int, path: Path): Unit = { |
94 def print_board(dim: Int, path: Path): Unit = { |
102 println |
95 println() |
103 for (i <- 0 until dim) { |
96 for (i <- 0 until dim) { |
104 for (j <- 0 until dim) { |
97 for (j <- 0 until dim) { |
105 print(f"${path.reverse.indexOf((j, dim - i - 1))}%3.0f ") |
98 print(f"${path.reverse.indexOf((j, dim - i - 1))}%3.0f ") |
106 } |
99 } |
107 println |
100 println() |
108 } |
101 } |
109 } |
102 } |
110 |
103 |
111 |
104 |
112 */ |
105 */ |