scala代写

Coursework 8 (Scala)

This coursework is worth 10%. It is about searching and backtracking. The first part is due on 29 November at 11pm; the second, more advanced part, is due on 20 December at 11pm. You are asked to implement Scala programs that solve various versions of the Knight’s Tour Problem on a chessboard. Note the second, more advanced, part might include material you have not yet seen in the first three lectures.

Important:

• Make sure the files you submit can be processed by just calling scala<<filename.scala>>onthecommandline.1 Usethetemplatefiles provided and do not make any changes to arguments of functions or to any types. You are free to implement any auxiliary function you might need.
• Do not leave any test cases running in your code because this might slow down your program! Comment test cases out before submission, otherwise you might hit a time-out.
• Do not use any mutable data structures in your submissions! They are not needed. This means you cannot create new Arrays or ListBuffers, for example.
• Do not use return in your code! It has a different meaning in Scala than in Java.
• Do not use var! This declares a mutable variable. Only use val!
• Do not use any parallel collections! No .par therefore! Our testing and

  marking infrastructure is not set up for it.

  Also note that the running time of each part will be restricted to a maximum of 30 seconds on my laptop: If you calculate a result once, try to avoid to calculate the result again. Feel free to copy any code you need from files knight1.scala, knight2.scala and knight3.scala.

  Disclaimer

  It should be understood that the work you submit represents your own effort! You have not copied from anyone else. An exception is the Scala code I showed during the lectures or uploaded to KEATS, which you can freely use.

  1All major OSes, including Windows, have a commandline. So there is no good reason to not download Scala, install it and run it on your own computer. Just do it!

  1

Background

The Knight’s Tour Problem is about finding a tour such that the knight visits every field on an n × n chessboard once. For example on a 5 × 5 chessboard, a knight’s tour is:

4

3 2 1 0

This tour starts in the right-upper corner, then moves to field (3, 2), then (4, 0) and so on. There are no knight’s tours on 2 × 2, 3 × 3 and 4 × 4 chessboards, but for every bigger board there is.

A knight’s tour is called closed, if the last step in the tour is within a knight’s move to the beginning of the tour. So the above knight’s tour is not closed because the last step on field (0, 4) is not within the reach of the first step on (4, 4). It turns out there is no closed knight’s tour on a 5 × 5 board. But there are on a 6 × 6 board and on bigger ones, for example

zzzzz 19162312 7

24 11 6 17 0

zzzzz 10 5 18 1 22

zzzzz 15 20 3 8 13

zzzzz

zzzzz

4 9 14 21 2

01234

zzzzzz 31 26 9 6 19 24

10 5 182516 7

zzzzzz 4 113017 8 15

zzzzzz 293227 0 2320

zzzzzz 12 3 342114 1

zzzzzz

zzzzzz

332813 2 3522

where the 35th move can join up again with the 0th move.
If you cannot remember how a knight moves in chess, or never played chess,

below are all potential moves indicated for two knights, one on field (2, 2) (blue moves) and another on (7, 7) (red moves):

7 6 5 4 3 2 1 0

zzzzzzz2N zzzzzzzz zzzzzzzz zzzzzzzz zzzzzzzz zz2Nzzzzz zzzzzzzz zzzzzzzz

01234567

2

Reference Implementation

This Scala assignment comes with three reference implementations in form of jar-files. This allows you to run any test cases on your own computer. For ex- ample you can call Scala on the command line with the option -cp knight1.jar and then query any function from the knight1.scala template file. As usual you have to prefix the calls with CW8a, CW8b and CW8c. Since some of the calls are time sensitive, I included some timing information. For example

scala> CW8a.print_board(8, CW8a.first_tour(8, List((0, 0))).get)

Hints

Part 1 useful list functions: .contains(..) checks whether an element is in a list, .flatten turns a list of lists into just a list, _::_ puts an element on the head of the list, .head gives you the first element of a list (make sure the list is not Nil); a useful option function: .isDefined returns true, if an option is Some(..); anonymous functions can be constructed using (x:Int) => …, this function takes an Int as an argument.

Part 2 a useful list function: .sortBy sorts a list according to a component given by the function; a function can be tested to be tail-recursive by annotation @tailrec, which is made available by importing scala.annotation.tailrec.

Part 1 (6 Marks)

You are asked to implement the knight’s tour problem such that the dimension of the board can be changed. Therefore most functions will take the dimension of the board as an argument. The fun with this problem is that even for small chessboard dimensions it has already an incredibly large search space—finding a tour is like finding a needle in a haystack. In the first task we want to see

3

how far we get with exhaustively exploring the complete search space for small chessboards.

Let us first fix the basic datastructures for the implementation. The board di- mension is an integer. A position (or field) on the chessboard is a pair of integers, like (0, 0). A path is a list of positions. The first (or 0th move) in a path is the last element in this list; and the last move in the path is the first element. For example the path for the 5 × 5 chessboard above is represented by

List((0, 4), (2, 3), ..., (3, 2), (4, 4))

􏰏􏰎􏰍􏰐 􏰏􏰎􏰍􏰐 􏰏􏰎􏰍􏰐 􏰏􏰎􏰍􏰐

24 23 1 0

Suppose the dimension of a chessboard is n, then a path is a tour if the length of the path is n × n, each element occurs only once in the path, and each move follows the rules of how a knight moves (see above for the rules).

Tasks (file knight1.scala)

1. (1)  Implement an is_legal function that takes a dimension, a path and a position as arguments and tests whether the position is inside the board and not yet element in the path. [1 Mark]
2. (2)  Implement a legal_moves function that calculates for a position all legal onward moves. If the onward moves are placed on a circle, you should produce them starting from “12-o’clock” following in clockwise order. For example on an 8 × 8 board for a knight at position (2, 2) and other- wise empty board, the legal-moves function should produce the onward positions in this order:

        List((3,4), (4,3), (4,1), (3,0), (1,0), (0,1), (0,3), (1,4))
   

   If the board is not empty, then maybe some of the moves need to be fil- tered out from this list. For a knight on field (7, 7) and an empty board, the legal moves are

                             List((6,5), (5,6))
   

   [1 Mark]

3. (3)  Implementtworecursivefunctions(count_toursandenum_tours).They each take a dimension and a path as arguments. They exhaustively search for tours starting from the given path. The first function counts all possi- ble tours (there can be none for certain board sizes) and the second collects all tours in a list of paths. These functions will be called with a path con- taining a single position—the starting field. They are expected to extend this path so as to find all tours starting from the given position.

4

[2 Marks]

Test data: For the marking, the functions in (3) will be called with board sizes up to 5 × 5. If you search for tours on a 5 × 5 board starting only from field (0, 0), there are 304 of tours. If you try out every field of a 5 × 5-board as a starting field and add up all tours, you obtain 1728. A 6 × 6 board is already too large to be searched exhaustively.2

Tasks (cont.)

(4) Implement a first-function. This function takes a list of positions and a function f as arguments; f is the name we give to this argument). The function f takes a position as argument and produces an optional path. So f ’s type is Pos => Option[Path]. The idea behind the first-function is as follows:

if f(x)̸=None otherwise

first(Nil, f ) first(x :: xs, f ) =

def

= None {

def

f(x) first(xs, f )

That is, we want to find the first position where the result of f is not None, if there is one. Note that ‘inside’ first, you do not (need to) know any- thing about the argument f except its type, namely Pos => Option[Path]. If you want to find out what the result of f is on a particular argument, say x, you can just write f (x). There is one additional point however you should take into account when implementing first: you will need to cal- culate what the result of f (x) is; your code should do this only once and for as few elements in the list as possible! Do not calculate f (x) for all elements and then see which is the first Some.

[1 Mark]

(5) Implement a first_tour function that uses the first-function from (4), and searches recursively for single tour. As there might not be such a tour at all, the first_tour function needs to return a value of type Option[Path].

[1 Mark] Testing: The first_tour function will be called with board sizes of up to 8 × 8.

Advanced Part 2 (4 Marks)

As you should have seen in Part 1, a naive search for tours beyond 8 × 8 boards and also searching for closed tours even on small boards takes too much time. There is a heuristic, called Warnsdorf’s Rule that can speed up finding a tour.

2For your interest, the number of tours on 6 × 6, 7 × 7 and 8 × 8 are 6637920, 165575218320, 19591828170979904, respectively.

5

This heuristic states that a knight is moved so that it always proceeds to the field from which the knight will have the fewest onward moves. For example for a knight on field (1, 3), the field (0, 1) has the fewest possible onward moves, namely 2.

7

6 5 4 3 2 1 0

Warnsdorf’s Rule states that the moves on the board above should be tried in the order

(0, 1), (0, 5), (2, 1), (2, 5), (3, 4), (3, 2)

Whenever there are ties, the corresponding onward moves can be in any order. When calculating the number of onward moves for each field, we do not count moves that revisit any field already visited.

Tasks (file knight2.scala)

6. (6)  Write a function ordered_moves that calculates a list of onward moves like in (2) but orders them according to Warnsdorf’s Rule. That means moves with the fewest legal onward moves should come first (in order to be tried out first). [1 Mark]
7. (7)  Implement a first_closed_tour_heuristic function that searches for a single closed tour on a 6 × 6 board. It should try out onward moves according to the ordered_moves function from (6). It is more likely to find a solution when started in the middle of the board (that is position (dimension/2, dimension/2)). [1 Mark]
8. (8)  Implementafirst_tour_heuristicfunctionforboardsupto30×30.It is the same function as in (7) but searches for tours (not just closed tours). It might be called with any field on the board as starting field.

   [1 Mark]

Task (file knight3.scala)

(9) Implement a function tour_on_mega_board which is the same function as in (8), but should be able to deal with boards up to 70 × 70 within 30

6

zzzzzzzz
zzzzzzzz

zzzzzzzz 7

37

zzzzzzzz z2Nzzzzzz

zzzzzzzz 25

7

zzzzzzzz
zzzzzzzz

01234567

seconds (on my laptop). This will be tested by starting from field (0, 0). You have to be careful to write a tail-recursive function otherwise you will get problems with stack-overflows. Please observe the requirements about the submissions: no tricks involving .par.

The timelimit of 30 seconds is with respect to the laptop on which the marking will happen. You can roughly estimate how well your imple- mentation performs by running knight3.jar on your computer. For ex- ample the reference implementation shows on my laptop:

7

[1 Mark]