javascript - 在生成Sudoku板的回溯算法方面需要帮助

我已经写了一个生成Sudoku板的算法，但是失败了。我是根据this编写的，尽管它确实有所不同，因为在我偶然发现之前，我已经编写了很多代码。

代码

我有一个多维数组，用于保存称为matrix的值。 matrix由9个数组组成，这些数组是行，每个数组都包含9列。所以要获得第4行第7列的值，我将使用

matrix[3][6];

求解所有平方的函数:

var populateMatrix = function() {
    var possibles = generatePossibleNumbersArray();
    var found = false;
    for(var i=0; i< matrix.length; i++) {
        for(var j=0; j< matrix[i].length; j++) {
            while(possibles[i][j].length > 0) {
                var rnd = Math.floor(Math.random() * possibles[i][j].length);
                var num = possibles[i][j].splice(rnd, 1)[0];
                if(isValid(i, j, num)) {
                    matrix[i][j] = num;
                    found = true;
                    break;
                } else {
                    found = false;
                    continue;
                }
            }
            if(!found) {
                possibles[i][j] = [1,2,3,4,5,6,7,8,9];
                j -= 2;
            }
        }
    }
}

generatePossibleNumbersArray()只是一个帮助函数，用于创建与matrix完全相同的多维数组，只是它被初始化为每个单元格保存一个整数数组1-9。在populateMatrix()函数期间，每个单元格的这些可能数字都会减少。

问题

由于j最终成为-1，因此在每次完成矩阵之前都会失败。这是因为随着越来越多的单元格得到解决，该算法将很难为该单元格找到一个值，从而回溯。但是最终最终回溯到j == -1。

我真的以为这个算法会起作用，并且我花了一整天的时间试图解决这个问题，但是我很沮丧，所以任何人都可以对此有所了解的光辉将不胜感激。

我以为“我知道，我会写一个JavaScript函数来解决Sudoku。它能有多难？'。我错了

[解决方案]

基于@ Steve314的评论(他现在已被删除!)，我在matrix[i][j] = undefined中添加了if(!found) { ...，该算法现在可以正常工作并且快速运行。

如果有人感兴趣，这里是complete code。

最佳答案

回溯算法通常在分支失败时恢复状态，并进行下一个可能的移动。因此，如果字段的随机填充创建了失败的分支，则只需写回原来的内容。