22C:30, 22C:115 Homework 3

Problem 1
You are given positive integers m and n and the general problem is to produce as output a knight's tour on the m X n chessboard or output the fact that such a tour does not exist.

1. Define a class called location which has two integer data members to keep track of the location of the knight on the chessboard. Define an implement appropriate data members.

   What to turn in? Printouts of the class header file and the class implementation file.

2. Assume that the rows of the m X n chessboard are labeled 0 through m-1 from top to bottom and from 0 through n-1 from left to right. For any location (i, j), 0 <= i <= m-1 and 0 <= j <= n-1, define a neighbor of (i, j) as any location that a knight positioned in location (i, j) can move to in one hop. Write a function numberOfNeighbors that takes a location (i, j), 0 <= i <= m-1 and 0 <= j <= n-1 and returns the number of its neighbors.

   What to turn in? Printout of the function numberOfNeighbors.

3. Write a function getNeighbor that takes a location (i, j), a positive integer t and returns the t th neighbor of location (i, j). Assume that the neighbors of (i, j) are ordered in counterclockwise order and are number 1, 2, 3,... in that order. You can also assume that t is no greater than the number of neighbors of (i, j).

   What to turn in? Printout of the function getNeighbor.

4. Write a function called knightsTour that takes positive integers m and n and returns a vector of locations that represents a knight's tour on the m X n chessboard. If a knight's tour exists, then the vector should have length mn. It does not matter where the tour starts, so just assume that the tour always starts at location (1, 1). If no knight's tour exists, then the vector that is returned should have length 0. This function should implement a ``dfs-like'' backtracking procedure discussed in class.

   What to turn in?Printout of the function knightsTour.
   

   In addition, turn in answers to the following questions:

   1. Does a 10 X 10 chessboard have a knight's tour? If so attach a printout of a knight's tour in a 10 X 10 chessboard obtained by calling your knightsTour function and printing out the output.
   2. Roughly speaking, given one hour, what is the largest value of n for which your function can produce a knight's tour in an n X n chessboard in that time?
   3. Think about ways in which you can speed up your function. Write down a couple of ways (in 1-2 sentences) each. You do not have to implement any of these ideas.

   There is plenty of information on the knight's tour problem on the web; much of it will not be useful to you. However, if you do use web based sources for any of your answer please acknowledge these.

1.       for(int i = 0; i < n; i++)
             for(int j = 0; j < min(i, 10); j++)
                cout << i*j << endl;
   

   In the above code the function call min(i, 10) returns the smaller of i and 10.

2. The same code as above except that min(i, 10) is replaced by max(i, 10), which returns the larger of i and 10.

3.       for(int i = 0; i < n; i++)
             for(int j = 0; j < n; j = j + i)
                cout << i*j << endl;
   

   The sum 1 + 1/2 + 1/3 + ... + 1/n is called the harmonic series and it is well known that this is O(log n). Use this fact in your analysis.