class Solution:
def solveSudoku(self, board):
self.solve(board)
def solve(self, board):
for i in range(9):
for j in range(9):
if board[i][j] == ".":
for num in "123456789":
if self.isValid(board, i, j, num):
board[i][j] = num
if self.solve(board):
return True
board[i][j] = "."
return False
return True
def isValid(self, board, row, col, num):
for i in range(9):
if board[i][col] == num:
return False
if board[row][i] == num:
return False
if board[3 * (row // 3) + i // 3][3 * (col // 3) + i % 3] == num:
return False
return True
Explanation (Python):
The Python solution uses a backtracking algorithm to solve the Sudoku puzzle.
It defines two main functions: solveSudoku and solve.
The solveSudoku function acts as a helper function to initiate the solving process.
The solve function is a recursive function that tries different numbers from 1 to 9 in each empty cell of the board until a solution is found.
It iterates through each cell of the board using nested loops.
If the cell is empty (denoted by "."), it tries each number from "1" to "9" and checks if it is valid using the isValid helper function.
If a number is valid, it places it in the cell and recursively calls the solve function.
If the solve function returns true, it means a solution is found, and the process stops.
If the solve function returns false, it backtracks by restoring the cell to empty (".") and continues trying other numbers.
The isValid function checks if a number is valid in a particular row, column, and 3x3 box.
It iterates through the rows, columns, and boxes, checking if the number is already present.
If the number is found in any row, column, or box, it returns false.
If the number is not found in any row, column, or box, it returns true.
class Solution {
public void solveSudoku(char[][] board) {
solve(board);
}
public boolean solve(char[][] board) {
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
if (board[i][j] == '.') {
for (char num = '1'; num <= '9'; num++) {
if (isValid(board, i, j, num)) {
board[i][j] = num;
if (solve(board)) {
return true;
}
board[i][j] = '.';
}
}
return false;
}
}
}
return true;
}
public boolean isValid(char[][] board, int row, int col, char num) {
for (int i = 0; i < 9; i++) {
if (board[i][col] == num) {
return false;
}
if (board[row][i] == num) {
return false;
}
if (board[3 * (row / 3) + i / 3][3 * (col / 3) + i % 3] == num) {
return false;
}
}
return true;
}
}
Explanation (Java):
The Java solution follows a similar approach to the Python solution using a backtracking algorithm.
It defines two main functions: solveSudoku and solve.
The solveSudoku function acts as a helper function to initiate the solving process.
The solve function is a recursive function that tries different numbers from '1' to '9' in each empty cell of the board until a solution is found.
It iterates through each cell of the board using nested loops.
If the cell is empty (denoted by '.'), it tries each number from '1' to '9' and checks if it is valid using the isValid helper function.
If a number is valid, it places it in the cell and recursively calls the solve function.
If the solve function returns true, it means a solution is found, and the process stops.
If the solve function returns false, it backtracks by restoring the cell to empty ('.') and continues trying other numbers.
The isValid function checks if a number is valid in a particular row, column, and 3x3 box.
It iterates through the rows, columns, and boxes, checking if the number is already present.
If the number is found in any row, column, or box, it returns false.
If the number is not found in any row, column, or box, it returns true.
class Solution {
public:
void solveSudoku(vector>& board) {
solve(board);
}
bool solve(vector>& board) {
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
if (board[i][j] == '.') {
for (char num = '1'; num <= '9'; num++) {
if (isValid(board, i, j, num)) {
board[i][j] = num;
if (solve(board)) {
return true;
}
board[i][j] = '.';
}
}
return false;
}
}
}
return true;
}
bool isValid(vector>& board, int row, int col, char num) {
for (int i = 0; i < 9; i++) {
if (board[i][col] == num) {
return false;
}
if (board[row][i] == num) {
return false;
}
if (board[3 * (row / 3) + i / 3][3 * (col / 3) + i % 3] == num) {
return false;
}
}
return true;
}
};
Explanation (C++):
The C++ solution follows the same backtracking approach as the Python and Java solutions.
It defines two main functions: solveSudoku and solve.
The solveSudoku function acts as a helper function to initiate the solving process.
The solve function is a recursive function that tries different numbers from '1' to '9' in each empty cell of the board until a solution is found.
It iterates through each cell of the board using nested loops.
If the cell is empty (denoted by '.'), it tries each number from '1' to '9' and checks if it is valid using the isValid helper function.
If a number is valid, it places it in the cell and recursively calls the solve function.
If the solve function returns true, it means a solution is found, and the process stops.
If the solve function returns false, it backtracks by restoring the cell to empty ('.') and continues trying other numbers.
The isValid function checks if a number is valid in a particular row, column, and 3x3 box.
It iterates through the rows, columns, and boxes, checking if the number is already present.
If the number is found in any row, column, or box, it returns false.
If the number is not found in any row, column, or box, it returns true.
These solutions utilize backtracking to solve the Sudoku puzzle by trying different numbers in each cell until a valid solution is found. The Python, Java, and C++ implementations share the same underlying logic, but the syntax and language-specific details may vary.