Knight's tour / recursion

Question

Hey, I'm trying to learn a little bit more about recursion but somehow I can't solve the knight's tour and I'm hoping someone can point out my logic error.

class main {

    static int fsize = 5; // board size (5*5)
    static int board[][] = new int[fsize][fsize];
    static int[] move_x = {1, 2, 2, 1, -1, -2, -2, -1}; // possible moves (x-axis)
    static int[] move_y = {-2, -1, 1, 2, 2, 1, -1, -2}; // possible moves (y-axis)

    // x = current x coordinate
    // y = current y coordinate
    static void Solve(int move_number, int x, int y) {
        board[x][y] = move_number;

        // check whether the knight has been on all filds or not
        if (move_number == ((fsize * fsize) - 1)) {
            for (int i = 0; i < fsize; i++) {
                for (int c = 0; c < fsize; c++) {
                    System.out.printf("%3d", board[i][c]);
                }
                System.out.println("\n");
            }
        } 
        else {
            // calculate new board coordinates
            for (int i = 0; i < 8; i++) {
                for (int c = 0; c < 8; c++) {
                    // Check whether the new coordinates are valid or not
                    if ((x + move_x[i]) >= 0 && (x + move_x[i]) < fsize && (y + move_y[c]) >= 0 && (y + move_y[c]) < fsize) {
                        // check whether the knight has been on this field or not (-1 = hasn't been here)
                        if (board[x + move_x[i]][y + move_y[c]] == -1) {
                            System.out.println("Move: " + move_number + "\n");
                            // Find next field
                            Solve(move_number + 1, (x + move_x[i]), (y + move_y[c]));
                        }
                    }
                }
            }
            // couldn't find a valid move
            board[x][y] = -1;
        }
    }

    public static void main(String[] args) {
        for (int i = 0; i < fsize; i++) {
            for (int c = 0; c < fsize; c++) {
                board[i][c] = -1;
            }
        }

        Solve(0, 0, 0);
    }
}

Edit: hope this is ok. I tried to run this program but couldn't get more than 22 valid moves.

Answer 1

Hm, so I gave it a shot and tried to figure out what's going on. Here is what I could gather.

1. sprung_x and sprung_y are supposed to be moved together as they represent the movement of a Knight. You have c and i as the independent indices for moving over those arrays, but really it should be just 1 variable. I struck the inner for loop and used i everywhere I saw c.
2. At the end of your method SucheWeg you are resetting the cell you invoked it on back to -1. This caused the infinite loop for me. Removing that line allowed it to complete normally in 19 moves at cell 1, 2. According to the definition of Knight's Tour, that is 1 attack move away from the cell you started at (0, 0) and so represents a complete tour.
3. Your fsize of 5 may not complete, according to Wikipedia. I used 6 instead for testing.
4. You need to account for what will happen when you reach the very end. In your code, on the last step there is a print out, but the method SucheWeg will still continue running, and it needs a way to terminate normally. You have to allow for unrolling of decisions if you hit a dead end (what I assume the -1 reset is from #2) but also realize that the same unrolling will make it go forever if you aren't careful. **When you return from the method, you should check that the board is not full before undoing steps. If it is full, you reached the end.

---

Just to show you the code I used:

static boolean isFull(int b [][])
{
   for(int i = 0; i < b.length; i++)
   {
      for(int k = 0; k < b[i].length; k++)
      {
         if(b[i][k] == -1) return false;
      }
   }
   return true;
}

static void SucheWeg(int schrittnummer, int x, int y)
{
   board[x][y] = schrittnummer;
   if(schrittnummer == ((fsize * fsize) - 1)) return;

   for(int i = 0; i < 8; i++)
   {
      int nextX = x + sprung_x[i];
      int nextY = y + sprung_y[i];

      // if we can visit the square, visit it
      if(nextX >= 0 && nextX < fsize && nextY >= 0 && nextY < fsize)
      {
         if(board[nextX][nextY] == -1)
         {
            SucheWeg(schrittnummer + 1, nextX, nextY);
         }
      }
   }
   if(isFull(board)) return;  // this is how we avoid resetting to -1
   board[x][y] = -1;          // reset if you get this far, so you can try other routes
}

Then in main I printed it out for us:

for(int i = 0; i < fsize; i++)
{
   for(int c = 0; c < fsize; c++) System.out.format("%02d ", board[i][c]);
   System.out.println("");
}

And the output is:

00 33 28 17 30 35 
27 18 31 34 21 16 
32 01 20 29 10 05 
19 26 11 06 15 22 
02 07 24 13 04 09 
25 12 03 08 23 14

I would like to say one last thing - a good implementation of this algorithm would catch the infinite loops. If this is in fact homework, you should modify it until you can run it on any size board without worrying about infinite loops. Currently if there is no solution, it may run forever.

Answer 2

Since it looks a little like a homework question, I'll just start with a hint.

move_x and move_y are the possible x, y moves by the knight. However, these can be indexed independently (i and c). You may wish to reconsider that.

Answer 3

Here's the thing - you are trying different valid moves even if the first attempted move was successful (led to a solution). I would make the function return a boolean value that specifies whether it reached a solution. So when you call the function from itself you should only try the next valid move if it returned false. Also, when you try a different move, you should clear the previous move (since the array was changed).

---

Edit:

class main {

static int fsize = 5; // board size (5*5)
static int board[][] = new int[fsize][fsize];
static int[] move_x = {1, 2, 2, 1, -1, -2, -2, -1}; // possible moves (x-axis)
static int[] move_y = {-2, -1, 1, 2, 2, 1, -1, -2}; // possible moves (y-axis)

// x = current x coordinate
// y = current y coordinate
static boolean solve(int move_number, int x, int y)
{
    boolean ret = true;
    board[x][y] = move_number;
    if(move_number == ((fsize * fsize) - 1))
    {
        for(int i = 0; i < fsize; i++)
        {
            for(int c = 0; c < fsize; c++)
            {
                System.out.printf("%3d", board[i][c]);
            }
            System.out.println("\n");
        }
    }
    else
    {
        for(int i = 0; i < 8; i++)
        {
            if((x + move_x[i]) >= 0 && (x + move_x[i]) < fsize
                    && (y + move_y[i]) >= 0
                    && (y + move_y[i]) < fsize)
            {
                if(board[x + move_x[i]][y + move_y[i]] == -1)
                {
                    if (solve(move_number + 1, (x + move_x[i]), (y + move_y[i]))) {
                        break;
                    }
                }
            }
        }
        ret = false;
        board[x][y] = -1;
    }
    return ret;
}
public static void main(String[] args) {
    for (int i = 0; i < fsize; i++) {
        for (int c = 0; c < fsize; c++) {
            board[i][c] = -1;
        }
    }

    solve(0, 0, 0);
}

}

This returns:

 0 15 20  9 24

 19 10 23 14 21

 16  1 18  5  8

 11  6  3 22 13

Answer 4

I was able to fix your code by doing two things:

• Only use for (int i = 0; i < 8; i++) single-level loop to check for the next 8 possibilities
  • Why do you have two nested loops here? You just want to check those 8 possibilities, that's it.
  • There are only 8 moves at each level, not 64
• Make board[x][y] = -1; the last statement in Solve
  • You want this executed regardless of the if conditions
  • You HAVE to undo board[x][y] = move_number; before you exit from this level

After fixing those, your homework is done, correct, finished. Congratulations!

---

In pseudocode

Right now, this is what you have:

static void Solve(int move_number, int x, int y) {
    board[x][y] = move_number;

    if (DONE) {
       PRINT;
    } else {
        for (int i = 0; i < 8; i++) {
            for (int c = 0; c < 8; c++) {
                ATTEMPT_MOVE(i, c); // doesn't make sense!!!
            }
        }
        board[x][y] = -1; // this doesn't belong here!!!
    }
}

To fix this code, you just have to do this:

static void Solve(int move_number, int x, int y) {
    board[x][y] = move_number;

    if (DONE) {
       PRINT;
    } else {
        for (int i = 0; i < 8; i++) {
           ATTEMPT_MOVE(i); // now makes more sense!
        }
    }

    board[x][y] = -1; // must undo assignment in first line!
}

---

Extra suggestions

• Break down logic into helper methods, i.e. board printing, and checking for valid coordinates