题解 | #Sudoku#

const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;

void async function () {
    // 获取某个格子能填的数字，返回数组
    const getAvailableValue = (matrix,i,j) => {
        //_i和_j为3*3九宫格的起点
        const _i = Math.floor(i/3)*3;
        const _j = Math.floor(j/3)*3;
        const set = new Set();
        //i,j所在行
        for(const item of matrix[i]) set.add(item);
        //i,j所在列
        for(let x = 0; x < 9; x++) set.add(matrix[x][j]);
        //i,j所在3*3九宫格
        for(let x = 0; x < 3; x++){
            for(let y = 0; y < 3; y++){
                set.add(matrix[_i+x][_j+y]);
            }
        }
        let availableValue = [];
        for(let value = 1; value <= 9; value++){
            if(!set.has(value)) availableValue.push(value);
        }
        return availableValue;
    }
    //先把唯一值的格子填满
    const setUniqueValue = () => {
        let finished = true;
        for(let i = 0; i < 9; i++){
            for(let j = 0; j < 9; j++){
                if(matrix[i][j] === 0){
                    const availableValue = getAvailableValue(matrix,i,j);
                    if(availableValue.length === 1){
                        matrix[i][j] = availableValue[0];
                        finished = false;
                    }
                }
            }
        }
        if(!finished) setUniqueValue();
    }
    //然后采用回溯法填入其他值
    const setValueByDFS = (matrix) => {
        const arr = JSON.parse(JSON.stringify(matrix));//深拷贝，接下来操作arr而不影响matrix
        for(let i = 0; i < 9; i++){
            for(let j = 0; j < 9; j++){
                if(arr[i][j] === 0){
                    const availableValue = getAvailableValue(arr,i,j);
                    if(availableValue.length > 0) {
                        while(availableValue.length){
                            arr[i][j] = availableValue.shift();
                            if(i==8&&j==8) return arr;
                            let nextArr = setValueByDFS(arr);
                            if(nextArr) return nextArr;
                        }
                        return false;
                    }else{
                        return false;//当前情况无解
                    }
                }
            }
        }
        return arr;
    } 
    
    //处理输入以及输出格式
    const matrix = [];
    for (let i = 0; i < 9; i++) {
        matrix.push((await readline()).split(" ").map(Number));
    }
    setUniqueValue();//先把唯一值的格子填满
    // console.log(setValueByDFS(matrix));
    console.log(
        setValueByDFS(matrix).reduce((pre, cur) => pre + cur.join(" ") + "\n", "")
    );
}();