4

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

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 个有效动作。

4

4 回答 4

2

我可以通过做两件事来修复你的代码：

  • 仅使用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!
}

额外建议

  • 将逻辑分解为辅助方法，即板打印和检查有效坐标
于 2010-05-15T12:13:00.790 回答
1

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

  1. sprung_x并且sprung_y应该一起移动，因为它们代表了骑士的移动。你有c和i作为移动这些数组的独立索引，但实际上它应该只是 1 个变量。我击中了内for循环并i在我看到的任何地方使用c。
  2. 在您的方法结束时，您SucheWeg将调用它的单元格重置为 -1。这给我造成了无限循环。删除那条线使其在单元格 1、2 的 19 次移动中正常完成。根据 Knight's Tour 的定义，即从您从 (0, 0) 开始的单元格移动 1 次攻击，因此代表完整的巡回赛。
  3. fsize根据维基百科，您的 5 个可能无法完成。我用 6 代替了测试。
  4. 你需要考虑到最后会发生什么。在您的代码中，在最后一步有一个打印输出，但该方法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

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

于 2010-05-15T11:44:02.387 回答
1

事情是这样的 - 即使第一次尝试的移动成功（导致解决方案），您也在尝试不同的有效移动。我会让函数返回一个布尔值，指定它是否达到了解决方案。因此，当您从自身调用该函数时，您应该只在它返回时尝试下一个有效的移动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
于 2010-05-15T12:05:10.277 回答
0

因为它看起来有点像一个家庭作业问题，所以我只是从一个提示开始。

move_x并且move_y是骑士可能的x，y移动。但是，这些可以独立索引（i和c）。您可能希望重新考虑这一点。

于 2010-05-15T11:45:54.810 回答