Warning: Outdated Content

This lab is from a previous version of CS 125. Click here to access the latest version.

A Knight's Tour

This lab continues our discussion of recursion—a powerful new problem solving tool. You’ll develop a recursive algorithm to explore a chess board and implement it in Java.

1. Recursion (110 Minutes)

Recursion is an important and powerful programming tool. At times, it can be the only way to elegantly solve a particular programming problem. But it is also a hard concept to wrap your head around.

In class we’ve seen recursion on trees, and will soon see the same idea applied to lists and arrays. MP4 introduces you to recursion on graphs—another powerful and ubiquitous data structure.

1.1. The Knight’s Tour

But today’s lab introduces you to recursion on a chess board. The problem we’ll be solving today is a classic known as the Knight’s Tour. The goal is to visit every square on a rectangular board once using the knight from chess, which moves in a distinctive L shape. (Please review the Wikipedia article if you aren’t familiar with chess or with this particular piece—or ask a neighbor.)

We’re doing this problem for two reasons. First, it’s really interesting. But second, and most importantly, it will help you get started on MP4, since touring the chess board is akin to graph exploration.

This may seem like a strange problem to approach recursively. But let’s apply our usual strategy.

1.1.1. Base case

There are actually two bases cases, one indicating success and one indicating failure:

Success: if we have successfully visited all squares we are done and can stop.
Failure: if we end up on a square where all moves would take us to squares that we have already visited, we are stuck and this particular path did not work out.

1.1.2. Recursive step

How do we make the problem smaller? Well, given an MxN board, a tour has to take M * N steps. So if we take one move in any direction we are a bit closer to finishing the tour! Given a position on the board, we have several smaller subproblems to solve—we need to see if we can visit all remaining squares from each of our neighbors. Since we have visited our current location, each subproblem also represents a board with fewer squares to visit, and so a smaller problem.

1.1.3. Combine results

How do we combine results from multiple moves in different directions? Here the idea is simple: just use the first direction that results in a valid tour of the board.

1.1.4. Pseudocode

Before we start with our Java code let’s jot down some pseudocode for our tour algorithm:

if all squares are visited:
  return the board with the current successful tour
for all valid moves we can make:
  if the move takes us to a square we've visited:
    continue
  copy the current board
  make the move on the copied board
  restart the tour on the copied board
  if the tour completes succesfully:
    return that board
  otherwise:
    try the next move
if we reach here we didn't find a move that worked, so return failure

1.2. Open and Closed Tours

We can also distinguish between two kinds of Knight’s tours. An open tour can end anywhere. But a closed tour has to link up with the start—meaning that it forms a loop that the knight could continue forever 1.

As a challenge problem on today’s lab homework we’ll have you try and implement a closed tour starting with your solution to the open tour algorithm. It’s not a huge change, but you may find it tricky.

1.3. Warnsdorff’s Rule

Finally, even though our recursive algorithm works reasonably well, we can help optimize it using a heuristic called Warnsdorff’s rule. It states that, if we have multiple options of valid moves, we should choose the one that results in the smallest number of next moves. While counterintuitive, it allows us to solve the Knight’s Tour in linear time and makes even large boards tractable.

So as a final challenge problem on today’s lab we’ll let you give Warnsdorff’s rule a try.

2. MP4 (Remaining Time)

If you have any time left over use it to work on MP4. It’s due in less than two weeks and it’s not easy.

3. Before You Leave

Don’t leave lab until:

You’ve completed our in-lab recursion homework problem.
You’ve made some more progress on MP4…
And so has everyone else in your lab!

If you need more help completing the tasks above please come to office hours or post on the {forum}.