The knight’s tour

The game of chess provides many interesting diversions that are independent of the game itself. Many of these diversions are based on the strange L-shaped move of the knight. A classical example is the knight’s tour.

The knight’s tour, which has captured the attention of both mathematicians and puzzle aficionados since the beginning of the eighteenth century, places a knight on any one of a chessboard’s 64 squares, and then proceeds to move that knight to each one of the remaining 63 squares, landing on each square exactly once.

This installment of Java Fun and Games presents a KT applet that demonstrates a restricted version of the knight’s tour. Instead of starting from any square, the knight starts in one of the corner squares. This applet’s GUI appears in Figure 1.

Before launching the tour, choose the knight’s initial corner by selecting one of the items from the choice component. In response, the knight appears in the appropriate corner. (The knight defaults to the upper-left corner.) Then click the Take the Tour button to start the knight on its tour. Both the button and the choice component are disabled during the tour.

What does the tour look like? Figure 2 reveals a sequence of lines (a trail), where each line is drawn from the center of the previous square to the center of the current square as the knight moves around the chessboard.

Now that you have seen both the applet’s GUI and what a tour looks like, study its source code in Listing 1.

Listing 1. KT.java

 
// KT.java
import java.applet.Applet;
import java.awt.*;
import java.awt.event.*;
import java.net.URL;
import java.util.ArrayList;
public class KT extends Applet
{
   // Thread delay measured in milliseconds.
   public final static int DELAY = 500;
   // Thread that runs the knight's tour.
   private Thread thd;
   // Initialize that applet.
   public void init ()
   {
      // Create a Label object that identifies the applet's title.
      Label lblTitle = new Label ("Knight's Tour", Label.CENTER);
      lblTitle.setFont (new Font ("Arial", Font.BOLD, 18));
      // Add the Label object to the applet's Panel container.
      add (lblTitle);
      // Create a ChessBoard object that represents a component capable of
      // displaying a chessboard and moving a knight to any square, leaving a
      // trail from the previous square.
      final ChessBoard cb = new ChessBoard (this);
      // Add the ChessBoard object to the applet's Panel container.
      add (cb);
      // Create a Panel object to hold a Label object, a Choice object, and a
      // Button object.
      Panel pnl = new Panel ();
      // Create a Label object that describes the Choice object. Add that
      // object to the Panel.
      pnl.add (new Label ("Choose starting position:"));
      // Create a Choice object that represents a component capable of
      // presenting starting positions for the tour. Add that object to the
      // Panel.
      final Choice c = new Choice ();
      c.add ("Upperleft corner");
      c.add ("Upperright corner");
      // Create the Choice's item listener. The listener resets the knight's
      // starting position based on the choice.
      c.addItemListener (new ItemListener ()
                         {
                             public void itemStateChanged (ItemEvent e)
                             {
                                Choice c = (Choice) e.getSource ();
                                if (c.getSelectedIndex () == 0)
                                    cb.moveKnight (1);
                                else
                                    cb.moveKnight (8);
                                cb.reset ();
                             }
                         });
      pnl.add (c);
      // Add the Panel to the applet's Panel container.
      add (pnl);
      // Create a Button object that represents a component for taking the
      // knight's tour.
      final Button btn = new Button ("Take the Tour");
      // Create the Button's action listener. The listener identifies the
      // tour in terms of board positions. Moving the knight from position to
      // position constitutes the knight's tour.
      ActionListener al;
      al = new ActionListener ()
           {
               public void actionPerformed (ActionEvent e)
               {
                  Runnable r;
                  r = new Runnable ()
                      {
                          int [] boardPositions1 =
                          {
                              1, 18, 33, 50, 60, 54, 64, 47,
                             32, 15,  5, 11, 17, 34, 49, 59,
                             53, 63, 48, 31, 16,  6, 12,  2,
                             19, 25, 42, 57, 51, 61, 55, 40,
                             23,  8, 14,  4, 10, 27, 44, 38,
                             21, 36, 46, 29, 35, 41, 58, 52,
                             62, 56, 39, 24,  7, 13,  3,  9,
                             26, 43, 37, 22, 28, 45, 30, 20
                          };
                          int [] boardPositions2 =
                          {
                              8, 23, 40, 55, 61, 51, 57, 42,
                             25, 10,  4, 14, 24, 39, 56, 62,
                             52, 58, 41, 26,  9,  3, 13,  7,
                             22, 32, 47, 64, 54, 60, 50, 33,
                             18,  1, 11,  5, 15, 30, 45, 35,
                             20, 37, 43, 28, 38, 48, 63, 53,
                             59, 49, 34, 17,  2, 12,  6, 16,
                             31, 46, 36, 19, 29, 44, 27, 21
                          };
                          public void run ()
                          {
                             cb.reset ();
                             // thd != null is our check for stopping the
                             // applet should the user move away from applet's
                             // Webpage.
                             for (int i = 0; i < boardPositions1.length &&
                                  thd != null; i++)
                             {
                                  if (c.getSelectedIndex () == 0)
                                      cb.moveKnight (boardPositions1 [i]);
                                  else
                                      cb.moveKnight (boardPositions2 [i]);
                                  try
                                  {
                                      Thread.sleep (DELAY);
                                  }
                                  catch (InterruptedException e2)
                                  {
                                  }
                             }
                             c.setEnabled (true);
                             btn.setEnabled (true);
                          }
                      };
                  c.setEnabled (false);
                  btn.setEnabled (false);
                  thd = new Thread (r);
                  thd.start ();
               }
           };
      btn.addActionListener (al);
      // Add the Button object to the applet's Panel container.
      add (btn);
   }
   // Stop the applet.
   public void stop ()
   {
      // Must stop the "knight's tour" thread if user moves away from Webpage.
      thd = null;
   }
}
final class ChessBoard extends Canvas
{
   // Color of non-white squares.
   private final static Color SQUARECOLOR = new Color (195, 214, 242);
   // Dimension of chessboard square.
   private final static int SQUAREDIM = 40;
   // Dimension of chessboard -- includes black outline.
   private final static int BOARDDIM = 8 * SQUAREDIM + 2;
   // Left coordinate of chessboard's upper-left corner.
   private int boardx;
   // Top coordinate of chessboard's upper-left corner.
   private int boardy;
   // Board width.
   private int width;
   // Board height.
   private int height;
   // Image buffer.
   private Image imBuffer;
   // Graphics context associated with image buffer.
   private Graphics imG;
   // Knight's image.
   private Image imKnight;
   // Knight image width.
   private int knightWidth;
   // Knight image height.
   private int knightHeight;
   // Coordinates of knight's trail.
   private ArrayList trail;
   // Left coordinate of knight rectangle origin (upper-left corner).
   private int ox;
   // Top coordinate of knight rectangle origin (upper-left corner).
   private int oy;
   // Applet that created ChessBoard object -- we call its getImage() and
   // getDocumentBase() methods; and we use it as an image observer for
   // drawImage().
   Applet a;
   // Construct the ChessBoard.
   ChessBoard (Applet a)
   {
      // Determine the component's size.
      width = BOARDDIM+1;
      height = BOARDDIM+1;
      // Initialize chessboard's origin, so that board is centered.
      boardx = (width - BOARDDIM) / 2 + 1;
      boardy = (height - BOARDDIM) / 2 + 1;
      // Use a media tracker to ensure that knight's image completely loads
      // before we get its height and width.
      MediaTracker mt = new MediaTracker (this);
      // Load knight's image.
      imKnight = a.getImage (a.getDocumentBase (), "knight.gif");
      mt.addImage (imKnight, 0);
      try
      {
         mt.waitForID (0);
      }
      catch (InterruptedException e) {}
      // Obtain knight's width and height, which helps to center the knight
      // image within a square.
      knightWidth = imKnight.getWidth (a);
      knightHeight = imKnight.getHeight (a);
      // Initialize knight image's starting origin so that knight is centered
      // in the square located in the top row and left column.
      ox = boardx + (SQUAREDIM - knightWidth) / 2 + 1;
      oy = boardy + (SQUAREDIM - knightHeight) / 2 + 1;
      // Create a datastructure to hold knight's trail as knight moves
      // around the board.
      trail = new ArrayList ();
      // Save applet reference for later use in call to drawImage().
      this.a = a;
   }
   // This method is called when the ChessBoard component's peer is created.
   // The code in this method cannot be called in the ChessBoard constructor
   // because the createImage() method returns null at that point. It doesn't
   // return a meaningful value until the ChessBoard component has been added
   // to its container. The addNotify() method is not called until the first
   // time ChessBoard is added to a container.
   public void addNotify ()
   {
      // Given this object's Canvas "layer" a chance to create a Canvas peer.
      super.addNotify ();
      // Create image buffer.
      imBuffer = createImage (width, height);
      // Retrieve graphics context associated with image buffer.
      imG = imBuffer.getGraphics ();
   }
   // This method is called by the applet's layout manager when positioning
   // its components. If at all possible, the component is displayed at its
   // preferred size.
   public Dimension getPreferredSize ()
   {
      return new Dimension (width, height);
   }
   // Move the knight to the specified board position. Throw an exception if
   // the position is less than 1 or greater than 64.
   public void moveKnight (int boardPosition)
   {
      if (boardPosition < 1 || boardPosition > 64)
          throw new IllegalArgumentException ("invalid board position: " +
                                              boardPosition);
      int rebasedBoardPosition = boardPosition-1;
      int col = rebasedBoardPosition % 8;
      int row = rebasedBoardPosition / 8;
      ox = boardx + col * SQUAREDIM + (SQUAREDIM - knightWidth) / 2 + 1;
      oy = boardy + row * SQUAREDIM + (SQUAREDIM - knightHeight) / 2 + 1;
      trail.add (new Point (ox + knightWidth / 2, oy + knightHeight / 2));
      repaint ();
   }
   // Paint the component -- first the chessboard and then the knight.
   public void paint (Graphics g)
   {
      // Paint the chessboard.
      paintChessBoard (imG, boardx, boardy);
      // Paint the knight.
      paintKnight (imG, ox, oy);
      // Paint the knight's trail.
      paintTrail (imG);
      // Draw contents of image buffer.
      g.drawImage (imBuffer, 0, 0, this);
   }
   // Paint the chessboard -- (x, y) is the upper-left corner.
   void paintChessBoard (Graphics g, int x, int y)
   {
      // Paint chessboard outline.
      g.setColor (Color.black);
      g.drawRect (x, y, 8 * SQUAREDIM + 1, 8 * SQUAREDIM + 1);
      // Paint checkerboard.
      for (int row = 0; row < 8; row++)
      {
           g.setColor (((row & 1) != 0) ? SQUARECOLOR : Color.white);
           for (int col = 0; col < 8; col++)
           {
                g.fillRect (x + 1 + col * SQUAREDIM, y + 1 + row * SQUAREDIM,
                            SQUAREDIM, SQUAREDIM);
                g.setColor ((g.getColor () == SQUARECOLOR) ? Color.white :
                            SQUARECOLOR);
           }
      }
   }
   // Paint the knight -- (x, y) is the upper-left corner.
   void paintKnight (Graphics g, int x, int y)
   {
      g.drawImage (imKnight, x, y, a);
   }
   // Paint the knight's trail.
   void paintTrail (Graphics g)
   {
      g.setColor (Color.black);
      int len = trail.size ();
      if (len == 0)
          return;
      Point pt = (Point) trail.get (0);
      int ox = pt.x;
      int oy = pt.y;
      for (int i = 1; i < len; i++)
      {
           pt = (Point) trail.get (i);
           g.drawLine (ox, oy, pt.x, pt.y);
           ox = pt.x;
           oy = pt.y;
      }
   }
   // Reset the chessboard by clearing the ArrayList.
   public void reset ()
   {
      trail.clear ();
   }
   // The AWT invokes the update() method in response to the repaint() method
   // call that is made as a knight is moved. The default implementation of 
   // this method, which is inherited from the Container class, clears the
   // applet's drawing area to the background color prior to calling paint().
   // This clearing followed by drawing causes flicker. KT overrides
   // update() to prevent the background from being cleared, which eliminates
   // the flicker.
   public void update (Graphics g)
   {
      paint (g);
   }
}

Listing 1 shows KT as an Abstract Window Toolkit-based applet. I have nothing against Swing—I just wanted to focus KT on the AWT.

The applet’s public void init() method constructs the GUI. This GUI includes an instance of the ChessBoard class that describes a chessboard.

Class ChessBoard subclasses java.awt.Canvas, making ChessBoard instances custom AWT components.

The constructor is responsible for determining the size of the component, for loading the image of a knight, for establishing the upper-left corner as the knight’s initial position, and for creating a datastructure to hold the trail during the tour.

The overridden public Dimension getPreferredSize() method returns the component’s size, to inform the layout manager that the ChessBoard wants to maintain these dimensions as its preferred size during layout operations.

I have also overridden the public void addNotify() method so that null is not returned when createImage() is called. This method returns null until the Canvas peer (or perhaps I should say the ChessBoard peer) has been created. After invoking super.addNotify() from within addNotify(), null will not return.

The public void moveKnight(int boardPosition) method moves a knight to the position specified via boardPosition. This argument must range from 1 through 64, otherwise an exception is thrown. In addition to drawing the knight’s image in the center of the positioned square, this method stores that image’s location in the previously created datastructure (see the constructor).

The public void reset() method clears out the contents of the datastructure. If this method did not exist, successive tours would display previous trails in addition to the new trail. Furthermore, the datastructure would keep growing in size, wasting memory and eventually causing an out-of-memory error.

Remaining methods are responsible for painting the chessboard, painting the knight image, and painting the trail. Also, the update() method is overridden to prevent flicker.

After compiling Listing 1, you will want to run this applet. Before you can do that, however, you must describe the applet to appletviewer via HTML. Listing 2 provides the needed HTML.

Listing 2. KT.html

 <applet code=KT.class width=345 height=435>
</applet>

While studying Listing 1, you have probably noticed an omission: You can start a tour from the upper-left or upper-right corners, but not from the lower-left or lower-right corners. I have deliberately omitted these corners to give you some work to accomplish. Because each tour mirrors another tour, it shouldn’t prove too difficult to figure out the positions for the remaining tours.

I have another exercise for you: Why do I specify cb.reset (); following a call to moveKnight() in the choice component’s item listener (see the init() method)?

Review

Chess offers many interesting diversions, such as the knight’s tour. This tour requires a knight to be moved from any starting square to each of the other 63 squares without landing on the same square more than once.

The KT applet took the easy way out, by restricting the starting square to the upper-left and upper-right corner squares. After you complete this applet, research a general solution where a tour can begin from any square.