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)
JS求解数独算法
点赞
收藏