Knight's tour backtracking

Question

I am working on knight's tour problem, and using backtracking algorithm. My code doesn't produce the right output in the end it just repeats the last two entries over and over until n^2 -1 is not reached.

This is my code. I am following this pseudocode http://www.wou.edu/~broegb/Cs345/KnightTour.pdf

visited = [[False for x in range(5)] for y in range(5)]

def move(x,y,m):

    result=False
    if x<0 or x>=5 or y<0 or y>=5:
        return False
    if visited[x][y]==True:
        return False
    if m==24:
        print "a solution has been found"
        print x,",",y


        visited[x][y]=True
        return True

    else:
        result=result or move(x+2,y+1,m+1)
        result=result or  move(x+2,y-1,m+1)
        result=result or move(x-2,y+1,m+1)
        result=result or move(x-2,y-1,m+1)
        result=result or move(x+1,y+1,m+1)
        result=result or move(x+1,y-1,m+1)
        result=result or move(x-1,y+1,m+1)
        result=result or move(x-1,y-1,m+1)
    if result==True:
        print x,",",y

        return True
    else:
        visited[x][y]=False
        return False

Answer 1

You are settings visited[x][y]=True to true at the end of your algorithm. It has to be set after you check you've bin there. I also made a couple of enhancements for your code:

N = 5 # This way you can test it with 5 or 6 and even 100 if you want to.
visited = [[False for x in range(N)] for y in range(N)]

def move(x,y,m):

    result=False
    if x<0 or x>=N or y<0 or y>=N or visited[x][y]==True: # You may merge these two ifs.
        return False
    visited[x][y]=True
    if m==(N * N - 1):
        print "a solution has been found"
        visited[x][y]=True # Set visited here tot true.
        return True
    else:
        print x,",",y
        if (move(x+2,y+1,m+1) or move(x+2,y-1,m+1)
            or move(x-2,y+1,m+1) or move(x-2,y-1,m+1)
            or move(x+1,y+1,m+1) or move(x+1,y-1,m+1)
            or move(x-1,y+1,m+1) or move(x-1,y-1,m+1)): # Place them in one if.
            print x,",",y

            return True
    return False # If the algorithm comes here it may return false

print move(2,1,0)

Answer 2

You appear to have made a mistake in the second half of the moves. You are adding/subtracting 1 to/from y, whereas this should be 2. The complete set of moves therefore looks like this:

    result=result or move(x+2,y+1,m+1)
    result=result or move(x+2,y-1,m+1)
    result=result or move(x-2,y+1,m+1)
    result=result or move(x-2,y-1,m+1)
    result=result or move(x+1,y+2,m+1)
    result=result or move(x+1,y-2,m+1)
    result=result or move(x-1,y+2,m+1)
    result=result or move(x-1,y-2,m+1)

Answer 3

The pseudocode algorithm you're implementing has an error. In the recursive case, you're never setting any of the visited values to True.

Try moving the line visited[x][y]=True from the if block to the following else block, before you do any of the recursive calls. (You could also just copy it, but it doesn't really do anything useful where it is.)

Answer 4

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();
    }
   }

 }