CS 311 Spring 2008
Assignment 4

Assignment 4 is due at 5 p.m. Tuesday, March 4. It is worth 20 points.

Procedures

E-mail answers to the exercises below to ffggc@uaf.edu, using the subject “DA4”.

• Your answers should consist of two files: spidertours.h and spidertours.cpp, from Exercise A. These files (or a single archive file containing them) should be attached to your e-mail message.
• Be sure to include your name in your e-mail.
• I may not read your homework e-mail immediately. If you wish to discuss the assignment (or anything else) with me, send me a separate message with a different subject line.

Exercises (20 pts total)

Exercise A — Counting “Spider Tours”

Purpose

In this exercise, you will implement recursive search with backtracking.

This exercise does not emphasize implementation details and language features nearly as much as earlier programming exercises did. You still need to write high-quality code and follow the coding standards; however, this should be relatively easy, for those that did a decent job on the previous assignments.

The key part of this exercise is the logic that the code must follow. When you do this exercise, it is probably worthwhile to spend more time planning, and less time coding, than you have before.

Background

Consider a rectangle divided into squares, like a checkerboard or chessboard. Call one square the “start” square and another square the “end” square. We will call the result a board.

A spider is placed on the start square. It steps to an adjacent square north, south, east, west, or in one of the four diagonal directions, then does this again, etc. We want the spider to visit every square on the board exactly once, never leave the board, and finish on the end square. We call the path it follows a spider tour.

For more information on boards and spider tours, along with illustrations, see the Monday, February 25 lecture slides [PDF], slides 9–12.

Instructions

Write a C++ package that counts the number of spider tours on a given board. Be sure to follow the coding standards. Standard 3A (“Requirements on template parameter types must be documented.”) and standard 3B (“Exceptions thrown by each function must be documented.”) now apply. You do not need to follow standard 3C.

• Your package should be contained in files spidertours.h and spidertours.cpp.
• The public interface of this package consists of a single function: countSpiderTours, which returns the number of spider tours on a given board (details below).
• Function countSpiderTours should do the bulk of its work via a call to function countSpiderTours_recurse, which is a recursive function (global or member) that counts the number of spider tours based on a given partial solution.
  • Note: Function countSpiderTours_recurse is not part of the public interface of the package. Prototype and implement it however you want; I will not test it. However, it must exist, be recursive, be used by countSpiderTours, and perform the correct computations for the partial solution it is given.

Here are the details for function countSpiderTours.

• It should be prototyped as

  int countSpiderTours(int size_x, int size_y,
                       int start_x, int start_y,
                       int end_x, int end_y);

  Coordinates range from 0 to size-1 in both the x and y directions. Thus, for example, we must have 0 <= start_x < size_x, and similarly for the end square and the y-coordinates.
• For legal parameter values, function countSpiderTours returns the number of spider tours on a size_x × size_y board, with start square (start_x, start_y) and end square (end_x, end_y).
  • So, for example, based on the 2/25 lecture slides, countSpiderTours(3, 2, 0, 1, 2, 0) should return 6.
• The function should work properly for all “reasonable” parameter values.
  • I will only test function countSpiderTours with parameter values that make sense: in particular, size_x and size_y will always be positive, and the start and end squares will always lie on the board and will not be the same square.
  • Your documentation should include information about what parameter values the function will accept.
• The function should run in a “reasonable” time (say less than a minute on a recent machine) whenever the total number of squares on the board is less than twenty. Note: Do not expect your function to run in a reasonable time for larger values. For example, if you make the board 10 × 10, be prepared to wait a long time for an answer.

Notes:

• Your function is only required to be fast for boards with less than 20 squares. However, it is still required to work for larger boards. Do not arbitrarily limit the size of a board!
• The February 25 lecture slides contain suggestions for how to do this assignment. See slides 13–19.

Test Program

I have written a test program: spidertours_test.cpp. If you compile and run your package with this program (unmodified!), then it will test whether your package works properly.

Do not turn in spidertours_test.cpp.

Notes:

• When your homework is graded, function countSpiderTours may be called with different parameters from those in the test program.
• The test program does not check whether function countSpiderTours_recurse meets the requirements of the assignment; nor does it check whether your code is fast enough.

What about Speed?

This exercise emphasizes logic, not efficiency. For grading purposes, running in a reasonable time is all I ask; you will not be given extra credit for super-fast code.

However, for those who like a challenge, once you get your code working, see how fast you can get it to run. I will do timing tests on all working implementations; the names of top performers will be announced in class some time after the homework is graded.

CS 311 Spring 2008: Assignment 4 / Updated: 26 Feb 2008 / Glenn G. Chappell / ffggc@uaf.edu