无法回溯以处理递归 javascript 数独求解器

Question

我绞尽脑汁，但我看不出哪里出了问题，从控制台日志看来，回溯无法正常工作是个问题，我认为这与我如何使用位置对象，如有任何帮助，我们将不胜感激，

它一直工作到回溯应该起作用，我可以看到它实际上回溯了 6 次，但位置实际上并没有回溯并改变以前的数字

let grid = [];

const solve = function (pos) {
  while (pos.x < 9 && pos.y < 9 && grid[pos.x][pos.y].value) {
    pos = incrementPos(pos);
  } // skip non-empty cells
  if (pos.y == 9) return true;

  for (let m = 1; m < 10; m++) {
    grid[pos.x][pos.y].value = m;
    console.log(pos, m);
    if (isValid(m, pos)) {
      if (solve(incrementPos(pos))) {
        return true;
      }
    }
  }
  console.log("start backtrack", pos);
  grid[pos.x][pos.y].value = "";
  return false;
};

function isValid(n, pos) {
  let valid = true;
  let row = checkRow(n, pos);
  let col = checkCol(n, pos);
  let block = checkBlock(n, pos);
  if (!row || !col || !block) {
    return false;
  } else {
    return true;
  }
}

function checkBlock(n, pos) {
  let startX = parseInt(pos.x / 3) * 3;
  let startY = parseInt(pos.y / 3) * 3;

  for (let x = startX; x < startX + 3; x++) {
    for (let y = startY; y < startY + 3; y++) {
      if ((grid[x][y].value === n) & (x !== pos.x) & (y !== pos.y)) {
        return false;
      }
    }
  }
  return true;
}

function checkRow(n, pos) {
  for (let t = 0; t < 9; t++) {
    if (grid[t][pos.y].value === n && t !== pos.x) {
      return false;
    }
  }
  return true;
}

function checkCol(n, pos) {
  for (let t = 0; t < 9; t++) {
    if ((grid[pos.x][t].value === n) & (t !== pos.y)) {
      return false;
    }
  }
  return true;
}

function incrementPos(pos) {
  if (pos.x < 8) {
    pos.x++;
  } else {
    pos.y++;
    pos.x = 0;
  }

  return pos;
}

const initGrid = function () {
  for (let x = 0; x < 9; x++) {
    let col = [];

    for (let y = 0; y < 9; y++) {
      let el = {};
      el.locked = false;
      el.value = "";
      el.location = document.querySelector("#r" + (y + 1) + "c" + (x + 1));
      col.push(el);
    }

    grid.push(col);
  }
  displayGrid();
};

const displayGrid = function () {
  for (let x = 1; x < 10; x++) {
    for (let y = 1; y < 10; y++) {
      document.querySelector("#r" + y + "c" + x).textContent =
        grid[x - 1][y - 1].value;
    }
  }
};

Answer 1

我真的搞不懂你在做什么，太多了，但是我看不到你实际上在哪里重置位置。我正在寻找这样的东西：

const getBlock = (block) => {
  if (block === 9) {
    return true
  }
  // you can use a total variable here to try it a couple of times before backtracking
  const valid = false

  ...

  if (valid) {
    getBlock(++block)
  } else {
    getBlock(--block)
  }
}

该代码一点也不完美，但它只是向您展示了这个想法，如果它是有效的，您应该增加块，并且在几次迭代之后您找不到另一个块之后您应该重置块回到前一个，然后再试一次。回溯的结果是，如果你控制台记录块，你应该看到类似的东西： 1 -> 2 -> 3 -> 4 -> 3 -> 4 -> 5 -> 4 -> 3 -> 4 -> 5 - > 6 -> ... 来来回回，直到您最终找到解决方案。

在您自己的代码中，我希望它类似于：

if (solve(incrementPos(pos))) {          
  return true
} else {
  solve(decrementPos(pos)) // or something
  // otherwise you're not actually backtracking
}

旁注，您可以使用模块化算法而不是循环。如果你知道你在一个特定的块中，那么你可以立即 validate/invalidate 并检查值是否存在于相关的 rows/columns/diagonals 中，而无需任何循环。小费。

无法回溯以处理递归 javascript 数独求解器

Can't get backtrack to work on recursive javascript sudoku sovler

javascript

recursion

sudoku

backtracking

recursive-backtracking