自动解数独

直接上代码

/* 编写一个程序，通过已填充的空格来解决数独问题。

一个数独的解法需遵循如下规则：

数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。
空白格用 '.' 表示。 */

// 两个样本
// const data = [
//     ['5', '3', '.', '.', '7', '.', '.', '.', '.'],
//     ['6', '.', '.', '1', '9', '5', '.', '.', '.'],
//     ['.', '9', '8', '.', '.', '.', '.', '6', '.'],
//     ['8', '.', '.', '.', '6', '.', '.', '.', '3'],
//     ['4', '.', '.', '8', '.', '3', '.', '.', '1'],
//     ['7', '.', '.', '.', '2', '.', '.', '.', '6'],
//     ['.', '6', '.', '.', '.', '.', '2', '8', '.'],
//     ['.', '.', '.', '4', '1', '9', '.', '.', '5'],
//     ['.', '.', '.', '.', '8', '.', '.', '7', '9'],
// ]
const data =[
    [".",".","9","7","4","8",".",".","."],
    ["7",".",".",".",".",".",".",".","."],
    [".","2",".","1",".","9",".",".","."],
    [".",".","7",".",".",".","2","4","."],
    [".","6","4",".","1",".","5","9","."],
    [".","9","8",".",".",".","3",".","."],
    [".",".",".","8",".","3",".","2","."],
    [".",".",".",".",".",".",".",".","6"],
    [".",".",".","2","7","5","9",".","."]
]
// 启动函数
function solction(board) {
    let finalResult = {return: undefined};
    fullfillTable(board, finalResult);
    console.log(finalResult)
}
// 填字函数
function fullfillTable(board, finalResult) {
    // 候选人数组
    let candidate = new Array(9);
    // 当前处理的位置
    let x = -1;
    let y = -1;
    // 还有没有空位（tip： 还有空， 但是缺找不到地方能填字，说明之前有填错了，就放弃这个分支）
    let zeroCount = 0;
    // 扫描一遍空格， 找出最好填的那个
    for (let i = 0; i < board.length; i++) {
        for (let j = 0; j < board.length; j++) {
            if (board[i][j] === '.') {
                zeroCount++
                const temp = getCandidate(board, i, j);
                if (temp.length < candidate.length && temp.length!==0) {
                    candidate = temp
                    x = i
                    y = j
                }
            }
        }
    }
    // 找到了可以填的
    if (x !== -1 && y !== -1) {
        // 如果只有一个候选的，那就填那个数字
        if (candidate.length === 1) {
            board[x][y] = candidate[0]
        // 多个的就需要用多多递归了
        } else {
            // 这里开启了多个分支
            for (let i = 0; i<candidate.length; i++) {
                const newBoard = new Array(board.length);
                for (let i = 0; i < board.length; i++) {
                    newBoard[i] = new Array(board.length)
                }
                for (let i = 0; i < board.length; i++) {
                    for (let j = 0; j < board.length; j++) {
                        newBoard[i][j] = board[i][j]
                    }
                }
                newBoard[x][y] = candidate[i]
                fullfillTable(newBoard, finalResult)
            }
            return;
        }
    } else if(zeroCount > 0) {
        return false;
    }
    // 还有空就继续递归
    if (zeroCount > 0) {
        console.log(x,y)
        console.log(candidate)
        fullfillTable(board, finalResult)
    } else {
        // 已经完成了
        finalResult.return = board;
    }
}
// 根据数独的规则找出 最好填的那个数，或者多个数
function getCandidate(board, x, y) {
    const queue = new Array(board.length).fill(0);
    for (let i = 0; i < board.length; i++) {
        if (board[x][i] !== '.') {
            queue[+board[x][i] - 1] = queue[+board[x][i] - 1]? queue[+board[x][i] - 1] : board[x][i]
        }
        if (board[i][y] !== '.')
            queue[+board[i][y] - 1] = queue[+board[i][y] - 1]? queue[+board[i][y] - 1] : board[i][y]
    }
    const startX = x - x % 3;
    const startY = y - y % 3;
    for (let i = startX; i < startX + 3; i++) {
        for (let j = startY; j < startY + 3; j++) {
            if (board[i][j] !== '.') {
                queue[+board[i][j] - 1] = queue[+board[i][j] - 1]? queue[+board[i][j] - 1] : board[i][j];
            }
        }
    }
    const returnData = [];
    queue.forEach((item, index) => {
        if (item === 0) {
            returnData.push((index+1).toString())
        }
    })
    return returnData
}
// console.log(getCandidate(data, 7,7))
solction(data);
// console.log(data)