Knight's Tour

The Knight's Tour is a classical chess thought experiment. It is obvious that some chess pieces can exists on any aribarary location on the chess board. For example, the Queen can definitely appear anywhere on the board. Other pieces, it is obvious that they cannot appear in some locations on the board. Bishops fit this bill, since they can only appear on their diagonals. The question is, can a knight travel to any arbitrary location on the board?

Setup

Create a directory assignment12 under assignments in your cs170 directory. All code for the assignment should be stored in this directory. 

cd ~/cs170/assignments
mkdir assignment12
cd assignment12

Details

You are going to represent a chess board as a graph, using an adjacency matrix. Your board should start out specifying all of the edges between any two locations on the chess board, using typical knight movement. Your goal is to find a traversal of this constructed graph such that every vertex is visited exactly once, the starting and ending verticies are the same.

Notice that you are building a graph that is very specific to a Knight chess piece. Each edge must represent a movement that is typical of a knight. Recall that a knight can only ever move in an "L" formation:

There are actually many different algorithms that can compute a solution to this problem. However, many of the algorithms are very computationally intensive. Instead, we can use a heuristic, which will allow use to solve the problem more quickly. When traversing the graph, we will always move to the unvisited vertex that has the least number of edges.

Your program should output a path similar to the one shown below. It does not have to be the exact path. 

[(0, 0), (2, 1), (4, 0), (6, 1), ..., (0, 0)]

Program Outline

Write down an outline of your program on paper. You should define what classes you need, what the attributes of thos classes are, and what methods each class will have. For each attribute, define the datatype being stored within and their purpose. For each method, define their Pre and Post conditions.

This is due Monday, Apr. 14th. All of what you define here can (and probably will) change by the time your final program is written. Consider this an "rough draft" for your program. This will help you get started thinking about the problem before Monday.

Submission

You are required to submit a tar file to http://cseval.roanoke.edu/. On cseval, there is a link for Assignment 12. You can create a tar file by issuing the following commands: 

cd ~/cs170/assignments
tar czvf assignment12.tgz assignment12/

"Hacker" Prompt

  1. Board Sizes: A typical chess board is 8 × 8. In mathematics, however, we don't always worry about the usual cases. Modify your program to work on arbitrary board dimensions and shapes. Can you find a shape that it is impossible to construct a knights tour on? What about a shape where there is exactly one knights tour?

    Overtaking: While this problem might seem a bit esoteric from the beginning, it actually does have some reasonable applications in the game of chess. Consider a chess board that has some opponent pieces on it. You want to find the shortest path that collects all of the pieces. Using Dijkstra's algorithm (Which we talked about on Friday), compute this shortest path.

    Your program will have to read some additional information. Namely the location of the opponent's pieces. Your path should cover these verticies, as well as any intermediate verticies in the way.

  2. Visualization: It has been a while since you've had to write a tkinter program from scratch. However, the visualization of a knight's tour is quite interesting. Write a tkinter program that displays a chess board. Then, connect the grid cells from the knight's tour using lines, so you can visualize the pattern you created.

Last modified: Fri Apr 11 12:53:46 EDT 2014