function solveSudoku(board){
    //get the first empty cell
    let [row, col] = findNextEmptyCell(board);

    //our base case
    //if there are no empty cells after going through the entire
    //board then we are done
    if(row == null){
        return true;
    }

    //in an empty cell we would try numbers from 1 to 9
    //if we find a valid number we would save it in the cell
    //-- we would need to test that the number will solve the entire board
    //-- so we recursively call the function inside an if statement with a new board
    //-- if the recursive call returns true then we know that the number
    //-- then we backtrack and try the next number
    for(let guess = 1; guess < 10; guess++){
        if(is_valid(board, guess.toString(), row, col)){
            board[row][col] = guess.toString();

            if(solveSudoku(board)){
                return true
            }
            board[row][col] = '.'
        }

    }
    return false;
}

function findNextEmptyCell(board){
    for(let r = 0; r < 9; r++){
        for(let c = 0; c < 9; c++){
            if(board[r][c] == '.'){
                return [r,c];
            }
        }
    }
    return [null, null];
}

function is_valid(board, guess, row, col){
    //check rows and the columns
    for(let i = 0; i < 9; i++){
        if(board[row][i] == guess || board[i][col] == guess){
            return false;
        }
    }
    //check the sub-boxes
    let rowStart = Math.floor(parseInt(row / 3)) * 3;
    let colStart = Math.floor(parseInt(col / 3)) * 3;

    for(let r = rowStart; r < rowStart + 3; r++){
        for(let c = colStart; c < colStart + 3; c++){
            if(board[r][c] == guess){
                return false;
            }
        }

    }
  
    //if we pass all the checks it means the number is
    return true
}

const board = [["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"]]

console.log(solveSudoku(board));