回溯对于开发人员的重要性

//We start with a partially filled Sudoku board (for empty cells) and we want to find the possible numbers that can be used to fill the board


const board = [
    ["5", "3", ".", "6", "7", "8", "9", "1", "2"],
    ["6", "7", "2", "1", "9", "5", "3", "4", "8"],
    ["1", "9", "8", "3", "4", "2", "5", "6", "7"],
    ["8", "5", "9", "7", "6", "1", "4", "2", "3"],
    ["4", "2", "6", "8", ".", "3", "7", "9", "1"],
    ["7", "1", "3", "9", "2", "4", "8", "5", "6"],
    ["9", "6", "1", "5", "3", "7", "2", "8", "4"],
    ["2", "8", "7", "4", "1", "9", "6", "3", "5"],
    ["3", "4", "5", "2", "8", "6", "1", ".", "9"]
];
//'.' represents an empty cell


// Possible numbers for Sudoku
const possibleNumbers = ["1", "2", "3", "4", "5", "6", "7", "8", "9"];

// Function to check if placing a number is valid
function isValid(number, row, col, board) {
    // Check row and column
    for (let i = 0; i < board.length; i++) {
        if (board[row][i] === number || board[i][col] === number) {
            return false;
        }
    }

    // Check the 3x3 sub-grid
    let startRow = Math.floor(row / 3) * 3;
    let startCol = Math.floor(col / 3) * 3;

    for (let i = startRow; i < startRow + 3; i++) {
        for (let j = startCol; j < startCol + 3; j++) {
            if (board[i][j] === number) {
                return false;
            }
        }
    }

    return true; // The number is valid for this position
}

// Function to solve the Sudoku board
function solveSudoku(board) {
    const emptySpaces = [];

    // Find all empty spaces on the board
    for (let i = 0; i < 9; i++) {
        for (let j = 0; j < 9; j++) {
            if (board[i][j] === ".") {
                emptySpaces.push({ row: i, col: j });
            }
        }
    }

    // Recursive function to fill empty spaces
    function recurse(emptySpaceIndex) {
        if (emptySpaceIndex >= emptySpaces.length) {
            return true; // All spaces filled successfully
        }

        const { row, col } = emptySpaces[emptySpaceIndex];

        for (let i = 0; i < possibleNumbers.length; i++) {
            const num = possibleNumbers[i];
            if (isValid(num, row, col, board)) {
                board[row][col] = num; // Place the number

                if (recurse(emptySpaceIndex + 1)) {
                    return true; // Solution found
                }

                // Backtrack if placing the number doesn't lead to a solution
                board[row][col] = ".";
            }
        }

        return false; // No valid number found for this position
    }

    recurse(0); // Start solving from the first empty space
    return board;
}

// Solve the Sudoku puzzle
solveSudoku(board);
console.log(board);