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.