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:
Java
C++
Python
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.