1 // Core Part about finding a single tour for a board using the |
1 // Core Part about finding a single tour for a board using the |
2 // Warnsdorf Rule |
2 // Warnsdorf Rule |
3 //============================================================== |
3 //============================================================== |
4 |
4 |
5 object M4b { |
5 object M4b { |
6 |
|
7 |
6 |
8 // !!! Copy any function you need from file knight1.scala !!! |
7 // !!! Copy any function you need from file knight1.scala !!! |
9 // |
8 // |
10 // If you need any auxiliary functions, feel free to |
9 // If you need any auxiliary functions, feel free to |
11 // implement them, but do not make any changes to the |
10 // implement them, but do not make any changes to the |
12 // templates below. |
11 // templates below. |
13 |
12 |
14 type Pos = (Int, Int) // a position on a chessboard |
13 type Pos = (Int, Int) // a position on a chessboard |
15 type Path = List[Pos] // a path...a list of positions |
14 type Path = List[Pos] // a path...a list of positions |
16 |
15 |
|
16 // ADD YOUR CODE BELOW |
|
17 //====================== |
17 |
18 |
18 //(6) Complete the function that calculates a list of onward |
19 //(6) |
19 // moves like in (2) but orders them according to Warnsdorf’s |
|
20 // rule. That means moves with the fewest legal onward moves |
|
21 // should come first. |
|
22 |
|
23 |
|
24 def ordered_moves(dim: Int, path: Path, x: Pos) : List[Pos] = ??? |
20 def ordered_moves(dim: Int, path: Path, x: Pos) : List[Pos] = ??? |
25 |
21 |
26 |
22 |
27 //(7) Complete the function that searches for a single *closed* |
23 //(7) |
28 // tour using the ordered_moves function from (6). This |
|
29 // function will be tested on a 6 x 6 board. |
|
30 |
|
31 |
|
32 def first_closed_tour_heuristics(dim: Int, path: Path) : Option[Path] = ??? |
24 def first_closed_tour_heuristics(dim: Int, path: Path) : Option[Path] = ??? |
33 |
25 |
34 |
26 |
35 //(8) Same as (7) but searches for *non-closed* tours. This |
27 //(8) Same as (7) but searches for *non-closed* tours. This |
36 // version of the function will be called with dimensions of |
28 // version of the function will be called with dimensions of |