CS 311 Fall 2009
Assignment 4

Assignment 4 is due at 5 p.m. Tuesday, October 13. It is worth 25 points.

Procedures

This assignment is to be done individually.

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

• Your answers should consist of two files: counthsw.h and counthsw.cpp, from Exercise A. The two 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 (25 pts total)

Exercise A — Counting Holey Spider Walks

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. Mark one square as forbidden, another square as start and yet another square as end. We will call the result a board.

We consider a spider that is placed on the start square. The spider can walk to an adjacent square: north, south, east, west, or any of the four diagonal directions. It does this repeatedly until it reaches the finish square. A way of doing this that does not touch the forbidden square, and touches each other square exactly once, is called a holey spider walk (HSW).

For more information on boards and HSWs, along with illustrations, see slides 9–12 from the Monday, October 5 lecture slides.

Instructions

Write a C++ package that counts the number of holey spider walks on a given board. Be sure to follow the coding standards. Standard 3A (“Requirements on template parameter types must be documented.”) and standard 3B (“If a function is not a template and not a member of a class template, then the exceptions it throws must be documented.”) now apply. You do not need to follow standards 3C or 3D.

• Your package should be contained in files counthsw.h and counthsw.cpp.
• The public interface of this package consists of a single function: countHSW, which returns the number of HSWs on a given board (details below).
• Function countHSW should do the bulk of its work via a call to a function countHSW_recurse, which is a recursive function (global or member) that counts the number of tilings based on a given partial solution.
  • Note: Function countHSW_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 countHSW to do most of the required computational work, and perform the correct computations for the partial solution it is given.

Here are the details for function countHSW.

• It should be prototyped as

  int countHSW(int size_x, int size_y,
               int forbid_x, int forbid_y,
               int start_x, int start_y,
               int finish_x, int finish_y);

  Coordinates for the forbidden, start, and finish squares range from 0 to size–1 in both the x and y directions. Thus we must have 0 <= forbid_x < size_x, and similarly for the y-coordinate and the other values.
• For legal parameter values, function countHSW returns the number of HSWs on a size_x × size_y board, with forbidden square (forbid_x, forbid_y), start square (start_x, start_y), and finish square (finish_x, finish_y).
  • For example, as noted in the lecture slides, countHSW(4,2, 1,1, 0,1, 3,0) should return 4.
• The function should work properly for all meaningful parameter values (ignoring stack overflows due to excessive recursion depth).
  • Function countHSW will only be called with parameter values that make sense. In particular, size_x and size_y will always be positive, the forbidden, start, and finish squares will always lie on the board, and these three will always be distinct.
  • Your documentation should include information about what parameter values the function will accept (preconditions).
• The function should run in a “reasonable” time (say, less than two minutes on a recent machine) whenever (a) the total number of squares on the board is at most 20, or (b) either the x or the y size is 1, and the other is less than 1000. Note: Do not expect your function to run in a reasonable time for larger values. For example, if you make the board 15 × 15, be prepared to wait a long time for an answer.

Notes:

• Your function is only required to be fast for boards with at most 20 squares, or with either the x or the y size being 1. However, it is still required to work for larger boards. Do not arbitrarily limit the size of a board!
• The October 5 lecture slides contain suggestions for how to do this assignment. See slides 13–19.

Test Program

I have written a test program: counthsw_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 counthsw_test.cpp.

Notes:

• When your homework is graded, function countHSW may be called with different parameters from those in the test program.
• The test program does not check whether function countHSW_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 Fall 2009: Assignment 4 / Updated: 8 Oct 2009 / Glenn G. Chappell / ffggc@uaf.edu