The Knight's Tour

This is a rather well-known problem suggested by the mathematician Euler. The process is to put a Knight on a particular square of an 8x8 chessboard and let it wander, land on each square once and only once. The object is to have the knight land on everyone of the 64 squares. This problem (#7,22) has been very well described in the book Java, How to Program (fifth edition) published by Deitel and Deitel.

The approach is to represent the board by a two-dimensional matrix (b) and the eight possible moves by the matrix (m). These are class variables so they will be available to all methods. Each element of the board (b) matrix contains the number of empty squares or possible moves around it. The algorithm would choose the squares with the least number of available moves to maximize the chance of completing the board.

Here is the complete code. The number matrix displayed at the end represents the order in which the board was filled, for research and post-mortem purposes.

// Euler's Knight's tour problem
// Starting from a point from the 8x8 chessboard, a knight will travel through
// all possible squares, once and only once.
// The board is defined as 0-7 (rows) and 0-7 (columns)
// Each square is designated from 00 to 77
// PC, 2004-09-17
// Imports
import java.awt.*;
import java.awt.event.*;
import javax.swing.*;

class Tour extends Frame implements ActionListener{

   Button calculateButton = new Button("Go");
   TextField Number = new TextField(9);
   TextField Result = new TextField(9);

    // define the move matrix, m
    int m[][] = new int[8][2];
    // define board matrix, b
    int b[][] = new int[8][8];

   //constructor

   public Tour()
   {
      super("Euler's Knight's tour problem");

      setLayout(new GridLayout(7,2));

      //Put components on frame
      add(new Label("Starting square:"));
      add(Number);
      add(new Label(" "));
      add(new Label(" "));
      add(new Label("No. of squares visited:"));
      add(Result);
      add(new Label(" "));

      add(calculateButton);
      calculateButton.addActionListener(this);
      //set the size for the frame and display it.
      setSize(300, 400);

      pack();
      show();
  }

  public void InitMoves(){
      m[0][0]=-2; m[0][1]=-1;
      m[1][0]=-2; m[1][1]=1;
      m[2][0]=-1; m[2][1]=-2;
      m[3][0]=-1; m[3][1]=2;
      m[4][0]=1; m[4][1]=-2;
      m[5][0]=1; m[5][1]=2;
      m[6][0]=2; m[6][1]=-1;
      m[7][0]=2; m[7][1]=1;
  }

  public void InitBoard(){
      for(int i=0; i<8;i++)for(int j=0;j<8;j++)b[i][j]=0;
  }

  public void InitPriority(){
      for(int i=0; i<8;i++)for(int j=0;j<8;j++){    // each square
        int i1,j1;
        for(int k=0;k<8;k++){   // each possible move
            i1=i+m[k][0]; j1=j+m[k][1];
            if(i1>=0&&i1<=7 && j1>=0&&j1<=7){ // add move possibility
                b[i1][j1]=b[i1][j1]+1;
            }
        }
    }
  }

  public int ChooseMove(int Next){
      // value returned is 10y+x
      // returns -1 if no more legal moves
      int x,y;
      x=Next%10; y=(Next-x)/10; // convert Next to x,y
      int best=100; // start with low priority
      int i1,j1,x1=-1,y1=0;
      for(int i=0;i<8;i++){ // check all possible moves
         i1=y+m[i][0]; j1=x+m[i][1];
         if(i1>=0&&i1<=7 && j1>=0&&j1<=7){
            if(b[i1][j1]=0){
                y1=i1;x1=j1; best=b[i1][j1];
            }
         }
      }
      if(best==100)return -1;
      return y1*10+x1;
  }

  public void MakeMove(int Next, int Count){
      int x,y;
      x=Next%10; y=(Next-x)/10; // convert Next to x,y
      // modify b matrix to reflect points
      int i1,j1;
      for(int i=0;i<8;i++){ // check all possible moves
             i1=y+m[i][0]; j1=x+m[i][1];
             if(i1>=0&&i1<=7 && j1>=0&&j1<=7 && b[i1][j1]>0){
                (b[i1][j1])--;
             }
      }
      b[y][x]=-Count;
  }

  public String PadLeft(String s, int n){
      s = "                                                      "+s;
      return s.substring(s.length()-n);
  }

  public String GetImage(){
      String out="";
      String bij;
      for(int i=0;i<8;i++){
          for(int j=0;j<8;j++){
              bij=""+ (-b[i][j]);
            if(b[i][j]<0)out += PadLeft(bij,3);
            else out += PadLeft("*",3);
          }
          out += "\n";
      }
      return out;
  }

  public void actionPerformed(ActionEvent event){
    int start=Integer.parseInt(Number.getText());
    int x,y,Next;

    // Verify validity of starting square
    y=start%10;     // horizontal position
    x=(start-y)/10; // vertical position
    if(start<0||start>77||x>7||y>7){
        Result.setText("Invalid start square");
        return;
    }

    // initialize relative moves
    InitMoves();

    // initialize priorities/scores
    InitBoard();

    // now place knight at all squares to initialize priority
    InitPriority();

    // From given square x, y, choose move Next
    Next=start;
    int Count=0;
    while(Next>=0){
        Count++;
        MakeMove(Next,Count);
        Next=ChooseMove(Next);
        Result.setText(""+Next+" "+Count);
    }

    // Display result
    Result.setText(""+Count);

    // Graphic display of results
    String out="";
    out += GetImage();
    JTextArea outputArea = new JTextArea (15,30);
    outputArea.setFont(new Font("Courier",Font.BOLD,16));
    JScrollPane scroller = new JScrollPane(outputArea);
    outputArea.setText(out);
    String title="Complete Knight's Tour";
    if(Count<64)title="Knight's Tour with "+Count+" Moves";
    JOptionPane.showMessageDialog(null,scroller,title,JOptionPane.INFORMATION_MESSAGE);
  }

}

public class Euler {
  public static void main(String[] args){
  Tour t=new Tour();
  }
}