Knight's Least Amount of Moves Debug Java

Question

Basically I need to find the smallest amount of moves it would take for a knight to reach a certain position on a 8x8 grid numbered 0-63 inclusive.

I have cross checked all test cases that I could think of and every test case is exactly what I am looking for. I used an elimination and placement algorithm modeled after an O(1) solution but for a knight instead.

The test cases I receive for the problem are confidential and I am left to guess what I have missed. When I try to verify my code I receive an output of:

Test 1 passed!
Test 2 failed.
Test 3 passed!
Test 4 failed.
Test 5 failed.
Test 6 failed.
Test 7 failed.
Test 8 failed.
Test 9 failed.
Test 10 failed.

Code:

public class Test {

public static boolean found = false;

public static void main (String[] args) {

    int[][] arr = { // 0   1   2   3   4   5   6   7
                     { 0,  1,  2,  3,  4,  5,  6,  7}, // 0
                     { 8,  9, 10, 11, 12, 13, 14, 15}, // 1
                     {16, 17, 18, 19, 20, 21, 22, 23}, // 2
                     {24, 25, 26, 27, 28, 29, 30, 31}, // 3
                     {32, 33, 34, 35, 36, 37, 38, 39}, // 4
                     {40, 41, 42, 43, 44, 45, 46, 47}, // 5
                     {48, 49, 50, 51, 52, 53, 54, 55}, // 6
                     {56, 57, 58, 59, 60, 61, 62, 63}, // 7 
                  };
    int src = 63; // Changed to parameters values later on in testing
    int dest = 30; // Changed to parameters values later on in testing

    int[] loc = pos(arr, src);
    int[][] productMatrix;
    int finalNumber = 0;

    while(!found && arr[loc[0]][loc[1]] != dest)
    {
        productMatrix = createknights(arr, loc[0], loc[1], dest);
        printMatrix(productMatrix);
        System.out.println("--------------------");
        finalNumber++;
    }

    System.out.println(finalNumber);


}

public static int[][] createknights(int[][] arr, int r, int c, int goal)
{
    arr[r][c] = -1;
    int[][] knightLoc = getKnightLoc(arr);

    for(int i = 0; i < knightLoc.length; i++)
    {
        int[][] possiblePositions = {
                                      {knightLoc[i][0] - 2, knightLoc[i][1] - 1}, //Up Left
                                      {knightLoc[i][0] - 2, knightLoc[i][1] + 1}, //Up Right
                                      {knightLoc[i][0] + 2, knightLoc[i][1] - 1}, //Down Left
                                      {knightLoc[i][0] + 2, knightLoc[i][1] + 1}, //Down Right
                                      {knightLoc[i][0] - 1, knightLoc[i][1] - 2}, //Left Up
                                      {knightLoc[i][0] + 1, knightLoc[i][1] - 2}, //Left Down
                                      {knightLoc[i][0] - 1, knightLoc[i][1] + 2}, //Right Up
                                      {knightLoc[i][0] + 1, knightLoc[i][1] + 2}  //Right Down
                                   };


        for( int[] row : possiblePositions)
        {
            if( checkLoc(arr, row[0], row[1]) )
            {
                if( arr[row[0]][row[1]] == goal )
                {
                    found = true;
                    break;
                }

                arr[row[0]][row[1]] = -1;
            }
        }
    }

    return arr;
}

public static int[][] getKnightLoc(int[][] arr)
{
    int knightNum = getKnightNum(arr);
    int[][] knightLocArray = new int[knightNum][2];

    for(int i = 0; i < arr.length; i ++)
    {
        for(int a = 0; a < arr[i].length; a++)
        {
            if(arr[i][a] == -1)
            {
                knightLocArray[(knightNum - 1)] = new int[]{i,a};
                knightNum--;
            }
        }
    }

    return knightLocArray;
}

public static int getKnightNum(int[][] arr)
{
    int knightNum = 0;

    for(int i = 0; i < arr.length; i ++)
    {
        for(int a = 0; a < arr[i].length; a++)
        {
            if(arr[i][a] == -1)
            {
                knightNum++;
            }
        }
    }       

    return knightNum;
}

public static boolean checkLoc(int[][] arr, int r, int c)
{
    if(r >= 0 && c >= 0 && r < arr.length && c < arr[r].length && arr[r][c] != -1)
    {
        return true;
    }

    return false;
}



public static int[] pos(int[][] arr, int src)
{
    for(int i = 0; i < arr.length; i ++)
    {
        for(int a = 0; a < arr[i].length; a++)
        {
            if(arr[i][a] == src)
            {
               return new int[]{i , a};
            }
        }

    }   

    return null;
}

public static void printMatrix(int[][] arr)
{
    for(int i = 0; i < arr.length; i ++)
    {
        for(int a = 0; a < arr[i].length; a++)
        {
            System.out.print(arr[i][a] + " ");
        }

        System.out.println();
    }       
}
} 

The O(1) model I checked my answers with:

O(1) model

Output example (ending value is the answer: src=63, dest=30):

0 1 2 3 4 5 6 7 
8 9 10 11 12 13 14 15 
16 17 18 19 20 21 22 23 
24 25 26 27 28 29 30 31 
32 33 34 35 36 37 38 39 
40 41 42 43 44 45 -1 47 
48 49 50 51 52 -1 54 55 
56 57 58 59 60 61 62 -1 
--------------------
0 1 2 3 4 5 6 7 
8 9 10 11 12 13 14 15 
16 17 18 19 20 21 22 23 
24 25 26 27 28 -1 30 -1 
32 33 34 35 -1 37 -1 39 
40 41 42 -1 44 45 -1 -1 
48 49 50 51 -1 -1 54 55 
56 57 58 -1 60 -1 62 -1 
--------------------
0 1 2 3 4 5 6 7 
8 9 10 11 -1 13 -1 15 
16 17 18 -1 20 -1 22 -1 
24 25 -1 27 -1 -1 30 -1 
32 -1 34 -1 -1 -1 -1 -1 
40 41 -1 -1 -1 45 -1 -1 
48 -1 50 -1 -1 -1 54 -1 
56 57 -1 -1 -1 -1 -1 -1 
--------------------
3 <----Answer

Please tell me what I am missing. Thanks!

Edit:

int src & int dest will not be hard coded at run time. The values will be replaced with parameter values. The values are hard coded for testing purposes.

Answer 1

I’m afraid your program prints 3 every time. This is because you have hardcoded the source as square 63 and the destination as square 30. Coincidentally the answers to two of the test cases are indeed 3. This is a reasonable guess. So you pass those two and fail the rest.

Instead you should of course read the input in whatever way is specified with your assignment.

Answer 2

It turns out that this block of code is a perfect solution except for the fact that apparently the test cases are tested in one continuous section of code.

For example, making a separate method allowed for me to call this section of code:

public static void main (String[] args) {
    //Test Cases
    System.out.println(answer(63,5));
    System.out.println(answer(19,4));
    System.out.println(answer(63,0));
}

This would print out:

5
0
0

After further debugging, I found what had caused the leading zeros is disregarding the found variable at the top of the code. Thus, leading to completely incorrect answers.

Previous Code:

while(!found && arr[loc[0]][loc[1]] != dest)
{
    productMatrix = createknights(arr, loc[0], loc[1], dest);
    printMatrix(productMatrix);
    System.out.println("--------------------");
    finalNumber++;
}

System.out.println(finalNumber);

New Code:

while(!found && arr[loc[0]][loc[1]] != dest)
{
    productMatrix = createknights(arr, loc[0], loc[1], dest);
    printMatrix(productMatrix);
    System.out.println("--------------------");
    finalNumber++;
}

found = false;

System.out.println(finalNumber);

Thus now relaying the correct answers.

Thank you Ole V.V. for brainstorming a solution! I guess just needed some time away from the problem and a couple of ideas.