Java: How to move a knight on a chessboard until no possible moves are left

Question

I have an assignment to have a knight move around the chessboard until it either completes a full tour or has no where else to go.

im having a problem figuring out how to have it actually stop after there are no more moves. I have the algorithm for the movement down, as well as bounds checking on the chessboard.

setting the loop count to 64 just times out, because the program will try to continually find a spot that doesn't exist if a perfect tour isn't created.

two ideas I have had to fix this is to either increment a variable every time a certain position is checked around a certain spot, and if all possible moves are taken by a previous move, terminate the program. Problem is I have no idea how to actually do this.

A second idea I had is to have the program quit the for loop after 2 seconds(during which the for loop will check each position way more than once) but I feel like my professor would crucify me upside down if I did that

here is my code:

import apcslib.*; //this is only for Format()
public class ktour
{
  int[][] kboard = new int[9][9];
  int[] vert = new int[9];
  int[] horiz = new int[9];
  ktour()
  {
        vert[1] = -2;vert[2] = -1;vert[3] = 1;vert[4] = 2;vert[5] = 2;vert[6] = 1;vert[7] = -1;vert[8] = -2;
        horiz[1] = 1;horiz[2] = 2;horiz[3] = 2;horiz[4] = 1;horiz[5] = -1;horiz[6] = -2;horiz[7] = -2;horiz[8] = -1;
        path();
  }
  public void path()
  {
        int row = 1;
        int col = 1;
        int loops = 10; //i have this set to 10 for now
        int col2 = 1;
        int row2 = 1;
        int r = (int)(Math.random() * (8) +1); //returns a random from 1 to 9
        //System.out.println(r);
        kboard[col][row] = 1;
        for(int x = 2; x < loops; x++) //this runs the bounds check and places each number for the amount that loops is
        {
        r = (int)(Math.random() * (8) +1);
        col = col2;
        row = row2;
        col = col + vert[r];
        row = row + horiz[r];
        while(col <= 0 || col > 8 || row <= 0 || row > 8) //bounds check, will keep running until both row and columb is in the board
        {
          r = (int)(Math.random() * (8) + 1);
          col = col2;
          row = row2;
          col = col + vert[r];
          row = row + horiz[r]; 
        }
            if(kboard[col][row] == 0)
            {
                kboard[col][row] = x;
                row2 = row; 
                col2 = col;

            }
            else
            {
                x--; //if the above if is false and a number already occupies the generated spot, x is decremented and the program tries again


            }
        }
        printboard();
  }
  public void printboard()
  {
      for(int y = 1; y < 9; y++)
      {
       System.out.println();
        for(int x = 1; x < 9; x++)
        {
            System.out.print(Format.right(kboard[y][x],3));
        }
      }
  }
}

Answer 1

I was able to fix my lab with the following code. I created a variable called count which I used to check if at any move there were no more moves left. As there are only 8 moves, when the variable reached 9 the code terminated, and printed up to the point it got to.

I had to put multiple if statements excluding r = math.random if count was not 0, meaning I was checking r 1-9, aka every possible move. Therefore, I couldn't use a randomizer, I had to traverse all 8 possible moves.

I also ran into problems when I reached the line where it checks if kboard[col][row] == 0. if you were running through a loop with count greater than 1, it was possible that col or row could be out of bounds, due to lack of a randomizer in the bounds checker. If left without a break, the bounds checker would run forever without a random number generated every time. I fixed this by adding an if statement that allowed the program to proceed if col and row were inside the board. if they were not, x was decremented and count was increased again, signifying a failed attempt.

This way I was able to check all possible moves, disregarding whether or not they were inside the board.

public void path()
  {
        int row = 1;
        int col = 1;
        int loops = 64; //i have this set to 10 for now
        int col2 = 1;
        int row2 = 1;
        int count = 0;
        boolean end = false;
        int r = (int)(Math.random() * (8) +1); //returns a random from 1 to 9
        //System.out.println(r);
        kboard[col][row] = 1;
        for(int x = 2; x < loops; x++) //this runs the bounds check and places each number for the amount that loops is
        {
        if(count == 0)
            r = (int)(Math.random() * (8) +1);
        if(count >= 1 && r != 8)
            r++;
        col = col2;
        row = row2;
        col = col + vert[r];
        row = row + horiz[r];
        while(col <= 0 || col > 8 || row <= 0 || row > 8) //bounds check, will keep running until both row and columb is in the board
        {
          if(count == 0)
            r = (int)(Math.random() * (8) + 1);
          col = col2;
          row = row2;
          col = col + vert[r];
          row = row + horiz[r];
          if(count >= 1)
                break;
        }
        end = false;
        if(r == 8 || r == 9)
            r = 1;
        if(count >= 9)
        {
            System.out.println("Halting... no where else to go");
            loops = 0;
        }
        if(!(col <= 0 || row <= 0 || row > 8 || col > 8))
        {
            if(kboard[col][row] == 0)
            {
                kboard[col][row] = x;
                row2 = row; 
                col2 = col;
                count = 0;
            }
            else
            {
                count++;
                x--; //if the above if is false and a number already occupies the generated spot, x is decremented and the program tries again
            }


        }
        else
        {
            count++;
                x--;
        }

        }
        printboard();
  }