Write a program to solve a Sudoku puzzle by filling the empty cells.

A sudoku solution must satisfy all of the following rules:


	Each of the digits 1-9 must occur exactly once in each row.
	Each of the digits 1-9 must occur exactly once in each column.
	Each of the digits 1-9 must occur exactly once in each of the 9 3x3 sub-boxes of the grid.


The '.' character indicates empty cells.

&nbsp;
Example 1:

Input: 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"]]
Output: [["5","3","4","6","7","8","9","1","2"],["6","7","2","1","9","5","3","4","8"],["1","9","8","3","4","2","5","6","7"],["8","5","9","7","6","1","4","2","3"],["4","2","6","8","5","3","7","9","1"],["7","1","3","9","2","4","8","5","6"],["9","6","1","5","3","7","2","8","4"],["2","8","7","4","1","9","6","3","5"],["3","4","5","2","8","6","1","7","9"]]
Explanation:&nbsp;The input board is shown above and the only valid solution is shown below:




&nbsp;
Constraints:


	board.length == 9
	board[i].length == 9
	board[i][j] is a digit or '.'.
	It is guaranteed that the input board has only one solution.


class Solution:
    def solveSudoku(self, board: List[List[str]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """
        full = set('123456789')
		# lets keep rows, columns and boxes sets in hashmaps
        rows = [set() for _ in range(9)]
        cols = [set() for _ in range(9)]
        boxes = [[set() for _ in range(3)] for _ in range(3)]
		# and remember empty cell to fill them in
        empty = set()

        for i in range(9):
            for j in range(9):
                if board[i][j] == '.':
                    empty.add((i,j))
                    continue
                rows[i].add(board[i][j])
                cols[j].add(board[i][j])
                boxes[i//3][j//3].add(board[i][j])
                
        def options(i, j):
			"""returns possible options for i,j intersecting options from row, col and box"""
            return (
                (full - rows[i]) &
                (full - cols[j]) &
                (full - boxes[i//3][j//3])
            )

        psingle = True # did we have single option decisions in previos traverse
        while empty:
            single = False # for single option decisions in this traverse
            
            for i, j in deepcopy(empty):
                opts = options(i, j)
                if len(opts) == 0:
					# we've made a wrong assumption - sudoku is unsolvable
                    return None, None
                elif len(opts) == 2 and not psingle: # we have no single-option decisions so have to take an assumption
                    board1 = deepcopy(board)
                    board1[i][j] = opts.pop()
                    board1, empty1 = self.solveSudoku(board1)
                    if board1 != None: # if solved - we're done
                        empty = empty1
                        for i, b1 in enumerate(board1):
                            board[i] = b1 # have to modify initial list, not just replace the reference
                        return board, empty
                if len(opts) == 1: # hey, we have a predetermined choice. nice
                    single = True
                    board[i][j] = opts.pop()
                    empty.remove((i, j))
                    rows[i].add(board[i][j])
                    cols[j].add(board[i][j])
                    boxes[i//3][j//3].add(board[i][j])
                    
            psingle = single

        return board, empty
        ```
class Solution {
    public void solveSudoku(char[][] board) {
       solve(board);
    }
    boolean solve(char board[][]){
        for(int i = 0; i<board.length; i++){
            for(int j = 0; j<board[0].length; j++){
                if(board[i][j] == '.') {
                    for(char c = '1'; c<='9'; c++){
                        if(isValid(board, c, i, j) == true){
                            board[i][j] = c;

                            if(solve(board) == true) return true;
                            else board[i][j] = '.';
                        }
                    }
                    return false;
                }
            }
        }
        return true;
    }

    boolean isValid(char board[][], char c, int row, int col){
        for(int i = 0; i<9; i++){
            if(board[row][i] == c) return false;
            if(board[i][col] == c) return false;
            if(board[3 * (row/3) + (i/3)][3 * (col/3) + (i % 3)] == c) return false;
        }
        return true;
    }
}
class Solution {
public:
    
    bool issafe(vector<vector<char>> &board,int row,int col,char c)
    {
        for(int i=0;i<9;i++)
        {
            if(board[row][i]==c)
                return 0;
            if(board[i][col]==c)
                return 0;
            if(board[3*(row/3)+i/3][3*(col/3)+i%3]==c)
                return 0;
        }
        return 1;
    }
    
    bool solve(vector<vector<char>> & board)
    {
        for(int i=0;i<9;i++)
        {
            for(int j=0;j<9;j++)
            {
                if(board[i][j]=='.')
                {
                    for(char c='1';c<='9';c++)
                    {
                        if(issafe(board,i,j,c))
                        {
                            board[i][j]=c;
                            if(solve(board)==1)
                                return 1;
                            else
                                board[i][j]='.';
                        }
                    }
                    return 0;   
                }
            }
        }
        return 1;
    }
    
    void solveSudoku(vector<vector<char>>& board) {
        solve(board);
    }
};
var solveSudoku = function(board) {
    let intBoard = convertBoardToInteger(board);

    let y = 0, x = 0;

    while (y <= 8){
        x = 0;
        while (x <= 8){
            if (isFreeIndex(board, x, y)){
                intBoard[y][x]++;
                while (!isPossibleValue(intBoard, x, y) && intBoard[y][x] < 10){
                    intBoard[y][x]++;
                };

                if (intBoard[y][x] > 9){
                    intBoard[y][x] = 0;
                    let a = retraceBoard(board, x, y);
                    x = a[0], y = a[1];
                    x--;
                }
            }
            x++;
        }
        y++;
    }
    
    convertIntBoardToString(intBoard, board);
}

var isFreeIndex = function(board, x, y){
    return (board[y][x] == '.');
}

var isPossibleValue = function(intBoard, x, y){
    return (isUniqueInColumn(intBoard, x, y) && isUniqueOnRow(intBoard, x, y) && isUniqueInBox(intBoard, x, y))
}
var isUniqueOnRow = function(intBoard, x, y){
    for (let i = 0;i<9;i++){
        if (intBoard[i][x] == intBoard[y][x] && i != y){
            return false;
        }
    }
    return true;
}
var isUniqueInColumn = function(intBoard, x, y){
    for (let i = 0;i<9;i++){
        if (intBoard[y][i] == intBoard[y][x] && i != x){
            return false;
        }
    }
    return true;
}
var isUniqueInBox = function(intBoard, x, y){
    let startX = x - (x % 3);
    let startY = y - (y % 3);

    for (let i = startX; i < startX+3; i++){
        for (let j = startY; j < startY+3; j++){
            if (intBoard[j][i] == intBoard[y][x] && (i != x || j != y)){
                return false;
            }
        }
    }
    return true;
}

var retraceBoard = function(board, x, y){
    do {
        if (x > 0){
            x--;
        } else {
            x = 8;
            y--;
        }
    } while (board[y][x] != '.');
    return [x,y]; 
}

var convertBoardToInteger = function(board){

    let intBoard = new Array(8);
    for (let y = 0;y<9;y++){
        intBoard[y] = new Array(8);
        for (let x =  0;x < 9;x++){
                intBoard[y][x] = parseInt(board[y][x]);
                if (!intBoard[y][x]) intBoard[y][x] = 0;
        }
    }
    return intBoard;
}
var convertIntBoardToString = function(intBoard, board){
    for (let y = 0;y<9;y++){
        for (let x =  0;x < 9;x++){
                board[y][x] = intBoard[y][x].toString();
        }
    }
    
    return board;
}
Sudoku Solver