javascript - 如何在 JS 中调试递归函数

Question

我编写了以下递归代码，用于解决数独难题。

网格：一个全局矩阵，代表拼图。
可能的功能：对于给定的数字和位置返回 true 或 false
解决：填充网格的递归。

但是我有一个错误，如何在不陷入无限循环的情况下对其进行调试。

是否有某种强制退出？你能发现错误吗？

let grid = [
  [5, 3, 0, 0, 7, 0, 0, 0, 0],
  [6, 0, 0, 1, 9, 5, 0, 0, 0],
  [0, 9, 8, 0, 0, 0, 0, 6, 0],
  [8, 0, 0, 0, 6, 0, 0, 0, 3],
  [4, 0, 0, 8, 0, 3, 0, 0, 1],
  [7, 0, 0, 0, 2, 0, 0, 0, 6],
  [0, 6, 0, 0, 0, 0, 2, 8, 0],
  [0, 0, 0, 4, 1, 9, 0, 0, 5],
  [0, 0, 0, 0, 8, 0, 0, 7, 9]];

function possible(x, y, n) {
  for (let i = 0; i < 9; i++) {
    if (grid[y][i] === n) {
      return false
    }
  }
  for (let i = 0; i < 9; i++) {
    if (grid[i][x] === n) {
      return false
    }
  }
  let x0 = Math.floor(x / 3) * 3;
  let y0 = Math.floor(y / 3) * 3;
  for (let i = 0; i < 3; i++) {
    for (let j = 0; j < 3; j++) {
      if (grid[y0 + i][x0 + j] === n) {
        return false
      }
    }
  }
  return true;
}

function solve() {
  for (let y = 0; y < 9; y++) {
    for (let x = 0; x < 9; x++) {
      if (grid[y][x] === 0) {
        for (let n = 1; n < 10; n++) {
          if(possible(y,x,n)){
            grid[y][x] = n;
            solve();
            grid[y][x] = 0;
          }
        }
        return;
      }
    }
  }
}

solve();

Answer 1

标准调试技术通常应该在这里工作。学习使用环境的调试器。例如，如果它在您的浏览器中运行，您应该能够在浏览器的开发人员工具中设置断点，并逐行浏览代码以尝试了解发生了什么。

递归总是需要一些导致递归结束的基本条件。在您的情况下，如果没有未解决的方块，您可以通过返回 true 来指示，然后将该“成功”状态传递到调用链。

此外，您对 possible 的调用已经切换了xand的预期参数位置y。

function solve() {
  for (let y = 0; y < 9; y++) {
    for (let x = 0; x < 9; x++) {
      if (grid[y][x] === 0) {
        for (let n = 1; n < 10; n++) {
          if(possible(x,y,n)){
            grid[y][x] = n;
            var solved = solve();
            if(solved) {
                return true;
            }
            grid[y][x] = 0;
          }
        }
        return false;
      }
    }
  }
  return true; // We didn't find any unsolved squares.
}

let grid = [
  [5, 3, 0, 0, 7, 0, 0, 0, 0],
  [6, 0, 0, 1, 9, 5, 0, 0, 0],
  [0, 9, 8, 0, 0, 0, 0, 6, 0],
  [8, 0, 0, 0, 6, 0, 0, 0, 3],
  [4, 0, 0, 8, 0, 3, 0, 0, 1],
  [7, 0, 0, 0, 2, 0, 0, 0, 6],
  [0, 6, 0, 0, 0, 0, 2, 8, 0],
  [0, 0, 0, 4, 1, 9, 0, 0, 5],
  [0, 0, 0, 0, 8, 0, 0, 7, 9]];

function possible(x, y, n) {
  for (let i = 0; i < 9; i++) {
    if (grid[y][i] === n) {
      return false
    }
  }
  for (let i = 0; i < 9; i++) {
    if (grid[i][x] === n) {
      return false
    }
  }
  let x0 = Math.floor(x / 3) * 3;
  let y0 = Math.floor(y / 3) * 3;
  for (let i = 0; i < 3; i++) {
    for (let j = 0; j < 3; j++) {
      if (grid[y0 + i][x0 + j] === n) {
        return false
      }
    }
  }
  return true;
}

function solve() {
  // find the first unsolved square.
  for (let y = 0; y < 9; y++) {
for (let x = 0; x < 9; x++) {
  if (grid[y][x] === 0) {
    // try every possible number in that square
    for (let n = 1; n < 10; n++) {
      if(possible(x,y,n)){
        grid[y][x] = n;
        var solved = solve();
        // if this led to a valid board, leave the board as-is and return success.
        if(solved) {
            return true;
        }
        grid[y][x] = 0;
      }
    }
    return false;
  }
}
  }
  console.log("all squares are solved");
  return true; // We didn't find any unsolved squares.
}

console.log(solve());
console.log(grid);

Answer 2

You Can Use Google Chrome Debug For Java Script

For Example You Can Creat Break Point In That:

Or Set Watch For Vars :

For Use It Press F12 And Select "Source" And Find Your JS File For Debug


For See More Go And Read https://www.w3schools.com/js/js_debugging.asp

Answer 3

在编写递归函数时，如果它一次又一次地重复完全相同，很有可能最终会调用无限并引发堆栈溢出。

在您的代码中，您正在调用solve将从头到尾循环的函数grid。再次solve调用自身的函数导致一次又一次地循环......所以它永远不会停止，直到堆栈溢出发生。

在下面的代码中，我确信我没有解决您的数独难题，但至少它显示了如何通过告诉在哪里重新启动循环来避免无限调用，这样它就不会再次循环。同样，我没有解决您的数独难题.. 只是递归性质的演示。我还添加了console.log这样的内容，以便您能够看到solve每次使用不同参数调用函数的方式。

function solve(ystart, xstart) {
  console.log('solve(', ystart + ',' + xstart, ')');
  for (let y = ystart; y < 9; y++) {
    for (let x = xstart; x < 9; x++) {
      if (grid[y][x] === 0) {
        for (let n = 1; n < 10; n++) {
          if(possible(y,x,n)){
            grid[y][x] = n;
            solve(y, x);
            grid[y][x] = 0;
          }
        }
        return;
      }
    }
  }
}

solve(0, 0);