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

Question

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

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

// 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;
    }
  }
...