"To iterate is human, to recurse divine."

-- L. Peter Deutsch

-- L. Peter Deutsch

Due: Wednesday, November 3rd, 11:00am CDT

Submit: Turn in all both of your Java source files using the D2L Dropbox:`Project7.java ChessBoard.java`.

Work may be completed in teams of two. (These should be freshly allocated teams for the second half of the term.) The names of both partners must appear in a comment block at the top of your files for credit to be given.

Submit: Turn in all both of your Java source files using the D2L Dropbox:

Work may be completed in teams of two. (These should be freshly allocated teams for the second half of the term.) The names of both partners must appear in a comment block at the top of your files for credit to be given.

A millenia old chess riddle challenges a person to move a knight on an empty board such that every square on the board is visited exaclty once. For more on the history and significance of this problem, see the Wikipedia entry on the Knight's Tour.

Your task for this project is build a general solution finder for the problem that recursively searches for a successful tour on an n x m board, given as input the board size and the starting position of the knight.

The chess piece called, "the knight," moves in a unique L-shaped pattern. From a square near the middle of a chessboard, a single move consists of either two horizontal spaces and a single vertical space, or two vertical spaces and a horizontal space. Like all chess pieces, the knight cannot move out of the boundaries of the chessboard. Thus, a knight can have up to 8 moves from a given starting location, fewer if it is near the board edge.

A chessboard has 64 squares, organized into eight rows and eight columns, alternating in color. The color of a square is of no importance when moving a knight. For the purposes of this problem, we're going to generalize to allow rectangular chessboards of any dimension.

For a given board size, various clever algorithms exist for quickly
detecting or constructing a successful knight's tour; none of these are
necessary or appropriate for this project. Your task is to construct a
simple, recursive, brute-force search of the possibilities. A modern
computer can find solutions for an 8x8 board with some starting positions
in under five seconds. This problem has exponential complexity as specified,
so solutions for bigger boards can take **a lot** longer.

I recommend solving this problem with two classes, one to represent the
chessboard, and one to encode the solution strategy. My `ChessBoard`
class contains a private, two-dimensional array of integers to represent the
board, and includes the following methods:

In the examples below, I use text in blue to distinguish the output of the program from the input I typed. This is for purpose of clarity only; your program will not print text in different colors.

Enter number of columns: 8

Enter starting row: 0

Enter starting column: 0

52 47 56 45 54 5 22 13

57 44 53 4 23 14 25 6

48 51 46 55 26 21 12 15

43 58 3 50 41 24 7 20

36 49 42 27 62 11 16 29

59 2 37 40 33 28 19 8

38 35 32 61 10 63 30 17

1 60 39 34 31 18 9 64

Enter number of columns: 4

Enter starting row: 1

Enter starting column: 3

No solution found for 4x4 board, starting at (1,3).

Back

[Revised 2010 Oct 26 20:48 DWB]