Problem Statement:

Given a partially filled 9×9 2D array ‘board[9][9]’, the goal is to assign digits (from 1 to 9) to the empty cells so that every row, column, and subgrid of size 3×3 contains exactly one instance of the digits from 1 to 9. 

Example:

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: The input board is shown above and the only valid solution is shown below:

Code:

class Innoskrit {
    
    int N = 9;
    int rows[][] = new int[N][N + 1];
    int cols[][] = new int[N][N + 1];
    int boxes[][] = new int[N][N + 1];
    char[][] board;
    boolean sudokuSolved = false;
    
    public int findBoxIndex(int row, int col) {
        return ((row/3) * 3 + col/3);
    }
    
    public boolean canBePlaced(int digit, int row, int col) {
        return rows[row][digit] + cols[col][digit] + boxes[findBoxIndex(row, col)][digit] == 0;
    }
    
    public void saveNumber(int digit, int row, int col) {
        rows[row][digit] = 1;
        cols[col][digit] = 1;
        boxes[findBoxIndex(row, col)][digit] = 1;
    }
    
    public void placeNextNumber(int row, int col) {
        if ((row == N - 1) && (col == N - 1)) {
            sudokuSolved = true;
        } else {
            if (col == N - 1) {
                backtrack(row + 1, 0);
            } else {
                backtrack(row, col + 1);
            }
        }
    }
    
    public void backtrack(int row, int col) {
        if (board[row][col] == '.') {
            for(int d = 1; d <= 9; d++) {
                if(canBePlaced(d, row, col)) {
                    saveNumber(d, row, col);
                    board[row][col] = (char) (d + '0');
                    placeNextNumber(row, col);
                    if(!sudokuSolved) {
                        rows[row][d] = 0;
                        cols[col][d] = 0;
                        boxes[findBoxIndex(row, col)][d] = 0;
                        board[row][col] = '.';
                    }
                }
            }
        } else {
            placeNextNumber(row, col);
        }
    }
    
    public void solveSudoku(char[][] board) {
        this.board = board;
        for(int i = 0; i < 9; i++) {
            for(int j = 0; j < 9; j++) {
                if(board[i][j] != '.') {
                    saveNumber(Character.getNumericValue(board[i][j]), i, j);
                }
            }
        }
        backtrack(0, 0);
    }
    
    public static void main (String[] args) {
        Innoskrit obj = new Innoskrit();
        char 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'}};
        obj.solveSudoku(board);
        for (char lane[] : board) {
            for(char ch : lane)
                System.out.print(ch + " ");
            System.out.println();
        }
    }
}

from collections import defaultdict

class Innoskrit:
    def solveSudoku(self, board):
        """
        Do not return anything, modify board in-place instead.
        """
        def find_box_index(row, col):
            return ((row//3) * 3 + col//3)
        
        def save_number(digit, row, col):
            rows[row][digit] += 1
            cols[col][digit] += 1
            boxes[find_box_index(row, col)][digit] += 1
            
        def can_be_placed(digit, row, col):
            if digit not in rows[row] and digit not in cols[col] and digit not in boxes[find_box_index(row, col)]:
                return True
            return False
            
        def place_next_number(row, col):
            if row == N - 1 and col == N - 1:
                nonlocal suduko_solved
                suduko_solved = True
            
            else:
                if col == N - 1:
                    backtrack(row + 1, 0)
                else:
                    backtrack(row, col + 1)
            
        def backtrack(row, col):
            
            if board[row][col] == ".":
                for d in range(1, 10):
                    if can_be_placed(d, row, col):
                        save_number(d, row, col)
                        board[row][col] = str(d)
                        place_next_number(row, col)
                        if not suduko_solved:
                            board[row][col] = "."
                            del rows[row][d]
                            del cols[col][d]
                            del boxes[find_box_index(row, col)][d]                      
            else:
                place_next_number(row, col)
            
        suduko_solved = False
        N = 9
        rows = [defaultdict(int) for i in range(N)]
        cols = [defaultdict(int) for i in range(N)]
        boxes = [defaultdict(int) for i in range(N)]
        
        for i in range(N):
            for j in range(N):
                if board[i][j] != ".":
                    digit = int(board[i][j])
                    save_number(digit, i, j)
                    
        backtrack(0, 0)
        
if __name__ == '__main__':
    obj = Innoskrit()
    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"]]
    obj.solveSudoku(board)
    for lane in board:
        for ch in lane:
            print(ch, end = " ")
        print()

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 

Time and Space Complexity:

Complexity Analysis

  • Time complexity is constant here since the board size is fixed and there is no N-parameter to measure. Though let’s discuss the number of operations needed : (9!)9. Let’s consider one row, i.e. not more than 9 cells to fill. There are not more than 9 possibilities for the first number to put, not more than 9×8 for the second one, not more than 9×8×7 for the third one, etc. In total that results in not more than 9! possibilities for just one row, which means no more than (9!)9 operations in total. Let’s compare:
    • 981 = 196627050475552913618075908526912116283103450944214766927315415537966391196809 for the brute force,
    • and (9!)9 = 109110688415571316480344899355894085582848000000000 for the standard backtracking, i.e. the number of operations is reduced by 1027 times!
  • Space Complexity: the board size is fixed, and the space is used to store board, rows, columns, and boxes structures, each containing 81 elements.