Knight's Tour algorithm help

Question

Okay everybody, I know the knight's tour problem is popular for all cs students and I am having trouble getting mine to work. I use this recursive algorithm to progress through the moves, however, once I get to around move 50 I have to backtrack since no moves are available and I end up never completing the tour. I pass a ChessNode (holds things like if node has been visited, move it was visited, etc...), next row, next column, and previous node's move count.

private int moveRecur(ChessNode current, int row, int column, int moveV){
    current.moveVisited = moveV+1;
    if(current.moveVisited > 63){
        return 0;
    }
        if(current.position==13 && aboard[row-1][column+2].visited != 1){
            current.visited = 1;
            moveRecur(aboard[row-1][column+2], row-1, column+2, current.moveVisited);
        }
        else if(current.position==22 && aboard[row-2][column+1].visited != 1){
            current.visited = 1;
            moveRecur(aboard[row-2][column+1], row-2, column+1, current.moveVisited);
        }
        else if(current.position == 50 && aboard[row+1][column-2].visited != 1){
            current.visited = 1;
            moveRecur(aboard[row+1][column-2], row+1, column-2, current.moveVisited);
        }
        else if(current.position == 41 && aboard[row+2][column-1].visited != 1){
            current.visited =1;
            moveRecur(aboard[row+2][column-1], row+2, column-1, current.moveVisited);
        }
        else if(current.position == 46 && aboard[row+2][column+1].visited != 1){
            current.visited = 1;
            moveRecur(aboard[row+2][column+1], row+2, column+1, current.moveVisited);
        }
        else if(current.position == 53 && aboard[row+1][column+2].visited != 1){
            current.visited = 1;
            moveRecur(aboard[row+1][column+2], row+1, column+2, current.moveVisited);
        }
        else if(current.position == 10 && aboard[row-1][column-2].visited != 1){
            current.visited = 1;
            moveRecur(aboard[row-1][column-2], row-1, column-2, current.moveVisited);
        }
        else if (current.position == 17 && aboard[row-2][column-1].visited != 1){
            current.visited =1;
            moveRecur(aboard[row-2][column-1], row-2, column-2, current.moveVisited);
        }
        if(row+1>=0 && row+1<8 && column+2>=0 && column+2<8){
            if(aboard[row+1][column+2].visited != 1){
                current.visited = 1;
                moveRecur(aboard[row+1][column+2], row+1, column+2, current.moveVisited);
            }
        }
        if(row+2>=0 && row+2<8 && column+1>=0 && column+1<8){
            if(aboard[row+2][column+1].visited != 1){
                current.visited = 1;
                moveRecur(aboard[row+2][column+1], row+2, column+1, current.moveVisited);
            }
        }
        if(row-1>=0 && row-1<8 && column-2>=0 && column-2<8){
            if(aboard[row-1][column-2].visited != 1){
                current.visited = 1;
                moveRecur(aboard[row-1][column-2], row-1, column-2, current.moveVisited);
            }
        }
        if(row-2>=0 && row-2<8 && column-1>=0 && column-1<8){
            if(aboard[row-2][column-1].visited != 1){
                current.visited = 1;
                moveRecur(aboard[row-2][column-1], row-2, column-1, current.moveVisited);
            }
        }
        if(row+1>=0 && row+1<8 && column-2>=0 && column-2<8){
            if(aboard[row+1][column-2].visited != 1){
                current.visited = 1;
                moveRecur(aboard[row+1][column-2], row+1, column-2, current.moveVisited);
            }
        }
        if(row+2>=0 && row+2<8 && column-1>=0 && column-1<8){
            if(aboard[row+2][column-1].visited != 1){
                current.visited = 1;
                moveRecur(aboard[row+2][column-1], row+2, column-1, current.moveVisited);
            }
        }
        if(row-1>=0 && row-1<8 && column+2>=0 && column+2<8){
            if(aboard[row-1][column+2].visited != 1){
                current.visited = 1;
                moveRecur(aboard[row-1][column+2], row-1, column+2, current.moveVisited);
            }
        }
        if(row-2>=0 && row-2<8 && column+1>=0 && column+1<8){
            if(aboard[row-2][column+1].visited != 1){
                current.visited = 1;
                moveRecur(aboard[row-2][column+1], row-2, column+1, current.moveVisited);
            }
        }
    //System.out.println(current.position + " "+current.moveVisited);
    current.visited = 0;    
    return 0;
}

So, initially I check for the spots that can move to the corner board positions, and then I just make recursive calls based on available moves. So I guess my main question is am I doing something wrong? or is there another condition I can used to make the tour a little more intuitive?

Thanks in advance!

Answer 1

This is the Knight's tour code in java and has a brilliant layout. I did this using backtracking using recursion. This was my class assignment. Do contact me if you have any problem understanding or running this code.

package knights.tour;
import java.awt.*;
import java.awt.event.*;
import java.util.logging.*;
import javax.swing.*;


public class KnightsTour extends JFrame implements ActionListener{

//All the static variables used between action listeners and functions.
public static String path;
public static int btnPressed = 0;
public static int rowSelected;
public static String[] pathArray;
public static int[][] coordinatesArray;
public static int columnSelected;  
public static int flag =0;
public static int increment = 0;
public static JPanel panel1 = new JPanel();
public static JPanel panel3 ;
public static JButton btnStart = new JButton("Start Animation");
public static JButton btnClear = new JButton("Clear");
public static JTextArea lblPath = new JTextArea();
public static JLabel lblStartRow = new JLabel();
public static JLabel lblStartColumn = new JLabel();
public static JButton[][] button;
public static int variableForIncrement=0;
static int row ;
static int column ;
static int[][] array = new int[row][column];
public static int count = 1;


KnightsTour(){

    //Setting layout of the frame in the constructor and adding buttons to the panel and the frame.
     getContentPane().setLayout(new GridLayout(2,1));
    lblPath.setLineWrap(true);
    lblPath.setColumns(10);
    lblPath.setSize(700, 100);
    lblPath.setEditable(false);
    panel1.add(btnStart);
    panel1.add(btnClear);
    panel1.add(lblStartRow);
    panel1.add(lblStartColumn);
    panel1.add(lblPath);
    panel3 = new JPanel(new GridLayout(row,column));

    // Initializing Array of buttons for the user to click on the chess board.
    button= new JButton[row][column];
     array = new int[row][column];
     coordinatesArray = new int[row*column][2];  // This array stores the coordinates as the Knight                            
    for(int i=0;i<row;i++){
        for(int j=0;j<column;j++){
            button[i][j]  = new JButton();
        }
    }

    //Setting background of the buttons to black and white for chessboard layout.
     for(int i=0;i<row;i++){
        for(int j=0;j<column;j++){
            if(i%2 ==j%2){
                button[i][j].setBackground(Color.BLACK);
                button[i][j].setForeground(Color.WHITE);
        }
            else{
                button[i][j].setBackground(Color.WHITE);
            }
            panel3.add(button[i][j]);
            button[i][j].addActionListener(this);
        }
   }

     btnClear.addActionListener(this);
     btnStart.addActionListener(this);
     add(panel3);
     add(panel1); 
   setDefaultCloseOperation(EXIT_ON_CLOSE);

}

public static void main(String[] args) {
  // TODO code application logic here
    String input =JOptionPane.showInputDialog("Enter the rows and columns in the format             (row,column)");
    String[] ar = input.split(",");
    row = Integer.parseInt(ar[0]);   // Finding out row and column from the user input.
    column = Integer.parseInt(ar[1]);
    pathArray = new String[row*column];  // This array is kept to store the path of the knight.
    JFrame frame = new KnightsTour();    
   frame.setVisible(true);
   frame.setSize(700,700);

}


//All the computation takes place in this function. It checks the neighbour and recursively calls itself.
public static void neighbourRecursion(int a,int b){

    pathArray[increment] = Integer.toString(a) + "," + Integer.toString(b);  // Storing the path of the Knight
    increment++;
    array[a][b] = count;                                                     //Stroing value of count.
    button[a][b].setText(String.valueOf(count));
    coordinatesArray[variableForIncrement][0] = button[a][b].getX();         //Finding coordinates of buttons to show animation
    coordinatesArray[variableForIncrement][1] = button[a][b].getY();
    count++;
    variableForIncrement++;

    //Checking for valid neighbours and calling itself recursively.
    if(a <= row-3 && b<=column-2){
        if(alreadyVisited(a+2,b+1)){
        neighbourRecursion(a+2,b+1);
        }
    }
     if(a<=row-3 && b>=1){
        if(alreadyVisited(a+2,b-1)){
        neighbourRecursion(a+2,b-1);
    }
    }
     if(a>=2 && b<=column-2){
        if(alreadyVisited(a-2,b+1)){
        neighbourRecursion(a-2,b+1);
    }
    }

     if(a>=2 && b>=1){
        if(alreadyVisited(a-2,b-1)){

        neighbourRecursion(a-2,b-1);
    }

    }
     if(a<=row-2 && b>=2){
        if(alreadyVisited(a+1,b-2)){

        neighbourRecursion(a+1,b-2);
    }
    }

     if(a<=row-2 && b<=column-3){
        if(alreadyVisited(a+1,b+2)){

        neighbourRecursion(a+1,b+2);
    }
    }
     if(a>=1 && b>=2){
        if(alreadyVisited(a-1,b-2)){
        neighbourRecursion(a-1,b-2);
    }
    }
     if(a>=1 && b <=column-3){
        if(alreadyVisited(a-1,b+2)){
        neighbourRecursion(a-1,b+2);
    }
    }


     //Breaking condition of the function.
     if(count == (row*column)+1){
     }


     // Backtracking condition if there is no neighbour.
    else{
         button[a][b].setText(""); 
        array[a][b]=0;
         count--;
         variableForIncrement--;
         if(increment >0){
         increment--;
         }
         return ;

    }


}
 //This function checks if the neighbour is already visited.
public static boolean alreadyVisited(int a,int b){

if(array[a][b] != 0){
    return false;
}
else{
    return true;
}
}

@Override
public void actionPerformed(ActionEvent e) {
    //when clear is pressed all arrays  and global variables are set to initial conditon.
if(e.getSource() == btnClear){
        for(int i =0;i<row;i++){
            for(int j=0;j<column;j++){
                array[i][j] = 0;
                button[i][j].setText("");
                count = 1;
                lblPath.setText("");
                lblStartRow.setText("");
                lblStartColumn.setText("");
                flag =0;
                variableForIncrement=0;
                increment =0;
                path ="    ";

    }
        }

      }

 //If start animation button is pressed animation is started.
      else if(e.getSource() == btnStart){
          animate();
      }

      // When the button is pressed. 

      else{
        for(int i=0;i<row;i++){
        for(int j=0;j<column;j++){
        if(e.getSource() == button[i][j]){
            if(flag == 1){
                lblPath.setText("  Please press clear before clicking again");   // Button pressed      twice without reset.
            }
            else{
       rowSelected = i;
       columnSelected =j;
       // If odd * odd board and selected postion is odd then No path is possible.
       if(row%2 ==1 && column%2 == 1 && rowSelected%2 ==0 && columnSelected%2 == 1 || row%2 ==1 &&     column%2 == 1 && rowSelected%2 ==1 && columnSelected%2 == 0){
           lblPath.setText("   Path not possible from this point");
       }
       else{
           int count;
       lblStartRow.setText("Starting Row : "+String.valueOf(rowSelected + 1));
       lblStartColumn.setText("Starting Column : "+String.valueOf(columnSelected + 1));
       count = 1; 
       flag = 1;
       startTour();    //Start tour function called.
       for(int q=0;q<row;q++){
           for(int w=0;w<column;w++){
               if(array[i][j] == 0){
                   count++;
               }
           }

       }
       if(count > 2){
           lblPath.setText("   No Path found");
       }

       //Printing path of the knight here.
       else{
       for(int k=0;k<pathArray.length;k++){
           path = path+"->"+ pathArray[k];
       }
       lblPath.setText("   Path : \n"+ path.substring(5));   
       }
        btnPressed = 1;
        break;
   }

            }
        }

   }



 }
 }    }


//Function for the animation. 
 void animate(){
     if(btnPressed == 1){
     btnPressed =0;
    Graphics g = getGraphics();
    for(int i=0;i<(row*column)-1;i++){
     try {
         Thread.sleep(600);   // this function slows down drawing of lines.

     } catch (InterruptedException ex) {

     }
           g.setColor(Color.RED);   // setting colour or line to red.
          g.drawLine((coordinatesArray[i][0]+65),(coordinatesArray[i][1]+50),(coordinatesArray[i+1]   [0]+65),(coordinatesArray[i+1][1]+50));
    }
     }
    else{
         lblPath.setText("  Please clear, select a button to see the animation again");  //Animate    button pressed twice without clear.
     }

}

 //This function calls the neighbour function with the selected row and column by the user.
  static void startTour(){
         neighbourRecursion(rowSelected,columnSelected);
    for(int i=0;i<row;i++){
        for(int j=0;j<column;j++){
            System.out.print(array[i][j]+" ");
        }
        System.out.println();
    }
   }

 }

Answer 2

I have an implementation of this program in C#. You can find it here:

http://github.com/danieltian/KnightBoard

It will only find the first solution though. I'm not saying to copy it, but you can take a look at it and see if it helps.