骑士之旅/递归

发布于 2024-09-01 19:50:49 字数 2098 浏览 7 评论 0原文

我正在尝试更多地了解递归，但不知何故我无法解决骑士之旅，我希望有人能指出我的逻辑错误。

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

编辑：希望这没问题。我尝试运行该程序，但无法获得超过 22 个有效动作。

原文

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.

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

风筝有风，海豚有海 2024-09-08 19:50:49

我能够通过做两件事来修复您的代码：

仅使用 for (int i = 0; i < 8; i++) 单级循环来检查接下来的 8 种可能性
- 为什么这里有两个嵌套循环？您只想检查这 8 种可能性，仅此而已。
- 每个级别只有 8 个动作，而不是 64 个
使 board[x][y] = -1; 成为 Solve 中的最后一个语句
- 无论 if 条件如何，您都希望执行此操作
- 在退出此关卡之前，您必须撤消board[x][y] = move_number;

解决这些问题后，你的作业就完成了，正确的，完成了。恭喜！

现在

，这就是您所拥有的：

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!!!
    }
}

要修复此代码，您只需执行以下操作：

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!
}

额外建议

将逻辑分解为辅助方法，即板打印和检查有效坐标

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

回复收藏 0 原文

请叫√我孤独 2024-09-08 19:50:49

事情是这样的 - 即使第一次尝试的移动成功了（导致了解决方案），您仍在尝试不同的有效移动。我会让该函数返回一个布尔值，该值指定它是否达到了解决方案。因此，当您从函数本身调用该函数时，您应该仅在返回 false 时尝试下一个有效的移动。另外，当您尝试不同的移动时，您应该清除之前的移动（因为数组已更改）。

编辑：

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

}

这将返回：

 0 15 20  9 24

 19 10 23 14 21

 16  1 18  5  8

 11  6  3 22 13

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

回复收藏 0 原文

贱贱哒 2024-09-08 19:50:49

嗯，所以我尝试了一下并试图弄清楚发生了什么事。这是我能收集到的。

sprung_x 和 sprung_y 应该一起移动，因为它们代表骑士的移动。您将 c 和 i 作为用于移动这些数组的独立索引，但实际上它应该只有 1 个变量。我触发了内部 for 循环，并在看到 c 的任何地方都使用了 i。
在方法 SucheWeg 结束时，您将调用它的单元格重置回 -1。这导致了我的无限循环。删除该线使其能够在单元格 1、2 处的 19 步移动中正常完成。根据骑士之旅的定义，这是距离您从 (0, 0) 开始的单元格 1 次攻击移动，因此代表一次完整的旅行。
根据维基百科，您的 fsize 5 可能不完整。我用 6 代替进行测试。
你需要考虑到达最后时会发生什么。在您的代码中，最后一步有打印输出，但方法 SucheWeg 仍将继续运行，并且需要一种正常终止的方法。如果你遇到了死胡同，你必须允许展开决策（我假设-1重置是从#2开始的），但也要意识到，如果你不小心，同样的展开会让事情永远进行下去。 **当您从该方法返回时，您应该在撤消步骤之前检查棋盘是否未满。如果已满，则您已到达终点。

只是为了向您展示我使用的代码：

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
}

然后在 main 中我为我们打印了它：

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

输出是：

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

我想说最后一件事 - 该算法的良好实现将捕获无限循环。如果这实际上是家庭作业，您应该修改它，直到可以在任何大小的板上运行它，而不必担心无限循环。目前如果没有解决方案，它可能会永远运行。

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

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.
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.
Your fsize of 5 may not complete, according to Wikipedia. I used 6 instead for testing.
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.

回复收藏 0 原文