|
1 // Part 1 about finding and counting Knight's tours |
|
2 //================================================== |
|
3 |
|
4 object CW7a { |
|
5 |
|
6 type Pos = (Int, Int) // a position on a chessboard |
|
7 type Path = List[Pos] // a path...a list of positions |
|
8 |
|
9 //(1a) Complete the function that tests whether the position |
|
10 // is inside the board and not yet element in the path. |
|
11 |
|
12 //def is_legal(dim: Int, path: Path)(x: Pos) : Boolean = ... |
|
13 |
|
14 |
|
15 //(1b) Complete the function that calculates for a position |
|
16 // all legal onward moves that are not already in the path. |
|
17 // The moves should be ordered in a "clockwise" manner. |
|
18 |
|
19 //def legal_moves(dim: Int, path: Path, x: Pos) : List[Pos] = ... |
|
20 |
|
21 |
|
22 //some test cases |
|
23 // |
|
24 //assert(legal_moves(8, Nil, (2,2)) == |
|
25 // List((3,4), (4,3), (4,1), (3,0), (1,0), (0,1), (0,3), (1,4))) |
|
26 //assert(legal_moves(8, Nil, (7,7)) == List((6,5), (5,6))) |
|
27 //assert(legal_moves(8, List((4,1), (1,0)), (2,2)) == |
|
28 // List((3,4), (4,3), (3,0), (0,1), (0,3), (1,4))) |
|
29 //assert(legal_moves(8, List((6,6)), (7,7)) == List((6,5), (5,6))) |
|
30 |
|
31 |
|
32 //(1c) Complete the two recursive functions below. |
|
33 // They exhaustively search for knight's tours starting from the |
|
34 // given path. The first function counts all possible tours, |
|
35 // and the second collects all tours in a list of paths. |
|
36 |
|
37 //def count_tours(dim: Int, path: Path) : Int = ... |
|
38 |
|
39 //def enum_tours(dim: Int, path: Path) : List[Path] = ... |
|
40 |
|
41 |
|
42 } |