使用 JavaScript 预填充数独网格-解网

问：

我正在用普通的JS写一个小数独游戏。现在我正在为我的代码而苦苦挣扎。我看到了一些示例，但我无法像其他示例一样调整我的代码。也许我的想法是错误的。我的主要问题是填充函数的递归调用。我不确定何时再次调用它以及何时返回布尔值。我尝试了一些不同的方法，但我遇到了无穷无尽的循环或部分填充的网格。

function fillGrid(grid) {

    // Run through grid to get next 0 to fill
    let filled = grid.every((row, rowIndex) => {
        // Row contains 0?
        let colIndex = row.indexOf(0);
        if (colIndex !== -1) {
            let randNumb = randomNumberBetween(1, 9);
            // Set random number where first 0 is found
            grid[rowIndex][colIndex] = randNumb;

            // Check validity
            let gridValid = gridIsValid(grid);

            // When valid continue with the new set number
            if (gridValid) {
                return fillGrid(grid);
            } else {
                // When not valid, reset number and have another try
                grid[rowIndex][colIndex] = 0;
                return fillGrid(grid);
            }
        }
    });

    return filled;
}

该函数采用每个位置为 0 的预填充网格，并应使用拟合数字填充整个网格。我看到的其他示例是迭代数字 1 - 9 并在每次调用函数时跟踪当前的列和行。我更喜欢立即设置一个随机数并计算下一个字段。

JavaScript 回溯数独

function shuffle(array) {
    for (let i = array.length - 1; i > 0; i--) {
        let j = Math.floor(Math.random() * (i + 1));
        let temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
    return array;
}

function range(a, b) {
    return Array.from({length: b - a + 1}, (_, i) => i + a);
}

function gridIsValid(grid) {
    function column(colIndex) {
        return grid.map(row => row[colIndex]); 
    }

    function block(blockIndex) {
        const colIndex = (blockIndex % 3) * 3;
        const rowIndex = Math.floor(blockIndex / 3) * 3;
        return grid.slice(rowIndex, rowIndex + 3).flatMap(row => row.slice(colIndex, colIndex + 3));
    }

    function groupIsValid(group) {
        group = group.filter(Boolean);
        return new Set(group).size === group.length;
    }
    
    return [
        ...grid,
        ...grid.map((_, i) => column(i)),
        ...grid.map((_, i) => block(i))
    ].every(groupIsValid);
}

function fillGrid(grid) {
    // Run through grid to get next 0 to fill
    const row = grid.find((row) => row.includes(0));
    if (!row) return true; // The grid has been filled.
    const colIndex = row.indexOf(0);
    // Loop over the 9 possible values we can put, in random order
    for (let randNumb of shuffle(range(1, 9))) {
        // Set random number where first 0 is found
        row[colIndex] = randNumb;
        // Check validity: When valid continue with the new set number
        if (gridIsValid(grid) && fillGrid(grid)) return true; // Found!: get out of recursion
        // When not valid, reset number and have another try (iteration)
        row[colIndex] = 0;
    }
    // All possible values for this cell failed... so backtrack!
    return false;
}

// Demo run:
const grid = Array.from({length: 9}, () => Array(9).fill(0));
fillGrid(grid);
for (const row of grid) console.log(...row);

使用 JavaScript 预填充数独网格

Prefill Sudoku Grid with JavaScript

评论

评论