JS求解数独算法

function getNext(board){
    var result=null;
    for(let i=0;i<9;i++){
        if(!result){
            for(let j=0;j<9;j++){ 
                if(board[i][j]=='.' && !result){
                    result={x:i,y:j};
                }
            }
        }
    }
    return result
}

function check(board,row,col,k){
    let result=true;
    if(board[row].find(item=>item==k)){
        result=false
    }
    for(var i=0;i<9;i++){
       if(board[i][col]==k){
           result=false;
       }
    }
    let _areai=Math.floor(row/3)*3
    let _areaj=Math.floor(col/3)*3
    for(let _i=0;_i<3;_i++){
        for(let _j=0;_j<3;_j++){
            if(board[_areai+_i][_areaj+_j]==k){
                result=false;
            }
        }
    }
    return result;
}

function solveSudoku(board) {
    let next=getNext(board);
    if(!next){
        return 'success'
    }else{
        let {x,y}=next;
        for(var k=1;k<10;k++){
            if(check(board,x,y,k+'')){
                board[x][y]=k+'';
                let flag=solveSudoku(board)
                if(flag=='success'){
                    console.log(board);
                }else if(flag=='error'){
                    board[x][y]='.'
                }
            }
        }
        if(board[x][y]=='.'){
           return 'error'
        }
        
    }
};

var testData=[
    ["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"]
]
solveSudoku(testData)

评论

暂无评论