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 (50 Minutes)

Recursion is an important and powerful programming tool. In class we’ve seen recursion on trees, and will soon see the same idea applied to lists and arrays. 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.

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.)

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.

2. Before You Leave

Don’t leave lab until:

You’ve completed our in-lab recursion homework problem.
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}.