Knight's tour Problem - storing the valid moves then iterating

Question

I tried to code the knight's tour problem(8X8 board), but somehow I am not able to get it to work.

Instead of exploring all possible knight moves, I am storing it and iterating it one by one but the program gets terminated before printing the result.

tagged the buggy code and (shamelessly copied) working code in comments.

Thanks in advance :)

 *if the board is traversed, print answer and return
 * find all possible moves from given position
 * for everyPosition in possiblePosition
 *   place the knight at everyPosition
 *   call the same function for the new position
 *   remove the knight from that position

import java.util.*;
import java.util.Map.Entry;



class Solution {

    static int [][] res;
    static int N;
    static int row[];
    static int col[];
    public static void init(int n) { //initialize the array
        res=new int[n][n];//n or N is the size of board which is 8
        N=n;


        for(int i=0;i<res.length;i++) {
            for(int j=0;j<res[0].length;j++) {
                res[i][j]=-1;
            }

        }

    }
    public static void print(int[][] res) { //helper function to print the 2d array
        for(int i=0;i<res.length;i++) {
            for(int j=0;j<res[0].length;j++) {
                System.out.print(res[i][j]+" ");
            }
            System.out.println();

        }
        System.out.println();
    }


    static boolean isValid(int r,int c){//check if the knight's move is inside the board then return true(<8 && >0)
        return (r>=0 && c>=0 && r<N && c<N && res[r][c] == -1);
    }
    public static boolean solve(int a,int b,int sizeOfBoard,int count,int row[],int col[]) {

        if(count==64)//if the board is traversed

        {   
            System.out.println(":)");
            print(res);
            return true;
        }
        //**buggy code start** 
        ArrayList<ArrayList<Integer>>possibleKnightMoves=possibleKnightMoves(a,b,sizeOfBoard);
        for(int i=0;i<possibleKnightMoves.size();i++) {//iterate over every possible knight move and check if the knight can be placed there or not
            possibleKnightMoves=possibleKnightMoves(a,b,sizeOfBoard);
            int x= possibleKnightMoves.get(i).get(0);
            int y= possibleKnightMoves.get(i).get(1);

            if(isValid(x,y)) {
                res[x][y]=count;
                if(solve(x,y,sizeOfBoard,count+1,row,col)) {
                    return true;



                }else
                {res[x][y]=-1;

                }
            }
        }
        //**buggy code end**

        //**perfect working code, uncomment me and comment the buggy code(only for reference)**     
        //      for(int i=0;i<N;i++) {
        //          int x=a+row[i];
        //          int y=b+col[i];
        //          if(isValid(x,y)) {
        //              res[x][y]=count;
        //              if(solve(x,y,sizeOfBoard,count+1,row,col)) 
        //                  return true;//knight can be placed 
        //              else
        //                  res[x][y]=-1;
        //
        //          }
        //
        //      }
        //**perfect working code end**


        return false;//knight cant be placed at the square





    }
    public static ArrayList<ArrayList<Integer>> possibleKnightMoves(int a,int b,int sizeOfBoard) {
        int x=a;
        int y=b;

        ArrayList<ArrayList<Integer>> result= new ArrayList<ArrayList<Integer>>();

        for(int i=0;i<N;i++) {
            x=x+row[i];// x,y represent all the possible knight moves from knight's current position
            y=y+col[i];

            result.add(new ArrayList<Integer>(Arrays.asList(x,y)));//add the moves to all possible moves list

        }



        return result;
    }

    public static void knightTour(int n) {
        init(n);
        res[0][0]=0;//set starting position
        int array[]={2, 1, -1, -2, -2, -1, 1, 2 };//array 1 and array 2 represent the set of knight moves from (x,y) eg: x+2,y+1
        row=array;
        int array2[]={1, 2, 2, 1, -1, -2, -2, -1 };
        col=array2;
        solve(0,0,n,1,array,array2);//starting  from 0,0 with count =1 as knight is already paced on 0,0
    }

    public static void main(String args[]) {
        N=8;
        knightTour(8);
        init(8);
        res[3][3]=1;

    }
}

Answer 1

The problem is possibleKnightMoves method, where you wrote

for(int i=0;i<N;i++) {
     x=x+row[i];current position
     y=y+col[i];

     result.add(new ArrayList<Integer>(Arrays.asList(x,y)));
}

Should be

for(int i=0;i<N;i++) {
     x=a+row[i];//Changed here
     y=b+col[i];//and here

     result.add(new ArrayList<Integer>(Arrays.asList(x,y)));
}

Or else, the value of x and y adds on.
It is right now, but there is still one problem: your code runs too slow.
Consider this line

ArrayList<ArrayList<Integer>>possibleKnightMoves=possibleKnightMoves(a,b,sizeOfBoard);

And this line in the for loop:

possibleKnightMoves=possibleKnightMoves(a,b,sizeOfBoard);

You repeated doing the same thing several times, which if you just remove the line in the for loop, the result won't change but runs faster. So I think this is what you want:

import java.util.*;
import java.util.Map.Entry;



public class Main {

    static int [][] res;
    static int N;
    static int row[];
    static int col[];
    public static void init(int n) { //initialize the array
        res=new int[n][n];//n or N is the size of board which is 8
        N=n;


        for(int i=0;i<res.length;i++) {
            for(int j=0;j<res[0].length;j++) {
                res[i][j]=-1;
            }

        }

    }
    public static void print(int[][] res) { //helper function to print the 2d array
        for(int i=0;i<res.length;i++) {
            for(int j=0;j<res[0].length;j++) {
                if(res[i][j] == -1) {
                    System.out.print("n ");
                }else {
                    System.out.print(res[i][j]+" ");
                }
            }
            System.out.println();

        }
        System.out.println();
    }


    static boolean isValid(int r,int c){//check if the knight's move is inside the board then return true(<8 && >0)
        return (r>=0 && c>=0 && r<N && c<N && res[r][c] == -1);
    }
    public static boolean solve(int a,int b,int sizeOfBoard,int count,int row[],int col[]) {

        if(count==64){   
            System.out.println(":)");
            print(res);
            return true;
        }
  
        ArrayList<ArrayList<Integer>>possibleKnightMoves=possibleKnightMoves(a,b,sizeOfBoard);
        for(int i=0;i<possibleKnightMoves.size();i++) {//iterate over every possible knight move and check if the knight can be placed there or not
            int x= possibleKnightMoves.get(i).get(0);
            int y= possibleKnightMoves.get(i).get(1);

            if(isValid(x,y)) {
                res[x][y]=count;
                if(solve(x,y,sizeOfBoard,count+1,row,col)) {
                    return true;
                }else{
                    res[x][y]=-1;
                }
            }
        }

        return false;//knight cant be placed at the square





    }
    public static ArrayList<ArrayList<Integer>> possibleKnightMoves(int a,int b,int sizeOfBoard) {
        ArrayList<ArrayList<Integer>> result= new ArrayList<ArrayList<Integer>>();
        for(int i=0;i<N;i++) {
            int x=a+row[i];//Changed here
            int y=b+col[i];//and here

            result.add(new ArrayList<Integer>(Arrays.asList(x,y)));
       }



        return result;
    }

    public static void knightTour(int n) {
        init(n);
        res[0][0]=0;//set starting position
        int array[]={2, 1, -1, -2, -2, -1, 1, 2 };//array 1 and array 2 represent the set of knight moves from (x,y) eg: x+2,y+1
        row=array;
        int array2[]={1, 2, 2, 1, -1, -2, -2, -1 };
        col=array2;
        solve(0,0,n,1,array,array2);//starting  from 0,0 with count =1 as knight is already paced on 0,0
    }

    public static void main(String args[]) {
        N=8;
        knightTour(8);
        init(8);
        res[3][3]=1;

    }
}