修改 Knight's Tour 算法以打印所有解决方案

Question

我最近拉取了一个 C 程序 (https://repl.it/Klpv)，它在 8 x 8 的棋盘上搜索骑士之旅。我在 JavaScript 中重新编写了程序（因为我更了解 JS），然后我修改了程序，以便可以在任何给定的电路板尺寸上搜索解决方案。

目前，它使用带回溯的递归算法来打印它找到的第一个解决方案。然后它停止了。原始 C 程序的评论之一说该程序将打印一个可行的解决方案，但我的目标是打印所有（或可自定义数量的）解决方案。我试过稍微修改程序的 'return' 命令，这样我就可以打印多个解决方案，但我似乎做不到。谁能帮帮我？

// JavaScript Knight's Tour Algorithm

/* A utility function to check if i,j are valid indexes
   for width*height chessboard */
var isSafe = function(x, y, sol) {
  return (x >= 0 && x < width && y >= 0 && y < height && sol[x][y] == -1);
}

/* A utility function to print solution matrix sol[width][height] */
var printSolution = function(sol) {
  var solution = "Knight's Tour for "+width+" by "+height+" board:\n";
  for (i = 0; i < width; i++) {
    for (j = 0; j < height; j++) {
      solution += sol[i][j] + "\t";
    }
    solution += "\n";
  }

  console.log(solution)
}

/* This function solves the Knight Tour problem using
   Backtracking.  This function mainly uses solveKTUtil()
   to solve the problem. It returns false if no complete
   tour is possible, otherwise return true and prints the
   tour.
   Please note that there may be more than one solutions,
   this function prints one of the feasible solutions.  */
var solveKT = function() {
  /* Create two-dimentional array */
  var sol = new Array(width);
  for (i = 0; i < sol.length; i++) {
    sol[i] = new Array(height)
  }

  /* Initialization of solution matrix - set all to -1 */
  for (i = 0; i < width; i++) {
    for (j = 0; j < height; j++) {
      sol[i][j] = -1
    }
  }

  /* xMove[] and yMove[] define next move of Knight.
     xMove[] is for next value of x coordinate
     yMove[] is for next value of y coordinate */
  var xMove = [2, 1, -1, -2, -2, -1, 1, 2];
  var yMove = [1, 2, 2, 1, -1, -2, -2, -1];

  // Since the Knight is initially at the first block
  sol[0][0] = 0;

  /* Start from 0,0 and explore all tours using
     solveKTUtil() */
  if (solveKTUtil(0, 0, 1, sol, xMove, yMove) == 0) {
    console.log("Solution does not exist");
    return 0;
  } else {
    printSolution(sol);
  }
}

/* A recursive utility function to solve Knight Tour
   problem */
var solveKTUtil = function(x, y, movei, sol, xMove, yMove) {
  var k, next_x, next_y;
  if (movei == width * height) {
    return 1;
  }

  /* Try all next moves from the current coordinate x, y */
  for (k = 0; k < 8; k++) {
    next_x = x + xMove[k];
    next_y = y + yMove[k];
    if (isSafe(next_x, next_y, sol)) {
      sol[next_x][next_y] = movei;
      if (solveKTUtil(next_x, next_y, movei + 1, sol, xMove, yMove) == 1) {
        return 1;
      } else {
        sol[next_x][next_y] = -1; // backtracking
      }
    }
  }

  return 0;
}

var width = 5;
var height = 6;
solveKT();

这将打印到控制台：

Knight's Tour for 5 by 6 board:
0   27  22  15  6   11  
23  16  7   12  21  14  
28  1   26  19  10  5   
17  24  3   8   13  20  
2   29  18  25  4   9

编辑：我发现了一个 C++ 程序可以做到这一点。 https://repl.it/L4Pf 不再需要帮助了！

Answer 1

这个问题有很多解决方案（根据 this question 的答案，超过 10^16 个）所以您将不得不满足于其中的几个。

一个简单的方法是填充一个路径数组，直到它足够大而不是返回 1。

...
if (solveKTUtil(next_x, next_y, movei + 1, sol, xMove, yMove) == 1) {
    return 1;
  }
...

应该变成类似

的样子

...
if (solveKTUtil(next_x, next_y, movei + 1, sol, xMove, yMove) == 1) {
    results.push(deepCopy(sol)) //copy the sol
    if(results.length > desired_number_of_paths){
        return 1;
    }
  }
...

Answer 2

您还可以将您的解决方案修改为：

var solveKTUtil = function(x, y, movei, sol, xMove, yMove) {
    var k, next_x, next_y;

    if (movei === width * height) {
        //Solution found, print it
        printSolution(sol);
        //Backtrack
        sol[x][y] = -1;
    }
    ....

这是：当找到解决方案时，将其打印出来，并在返回之前回溯，以便继续搜索解决方案。

修改 Knight's Tour 算法以打印所有解决方案

Modify Knight's Tour Algorithm to Print All Solutions

javascript

algorithm

recursive-backtracking

knights-tour