Description:
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-9must occur exactly once in each row. - Each of the digits
1-9must occur exactly once in each column. - Each of the digits
1-9must occur exactly once in each of the 93x3sub-boxes of the grid.
The '.' character indicates empty cells.
Examples:
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: The input board is shown above and the only valid solution is shown below:Solution in Python:
To solve a Sudoku puzzle, we need to fill the empty cells in such a way that each row, each column, and each of the nine 3×3 sub-boxes contains the digits from 1 to 9 exactly once. This problem can be effectively solved using a backtracking algorithm.
Python
class Solution:
def solveSudoku(self, board: List[List[str]]) -> None:
"""
Solve the Sudoku puzzle by modifying the input board in-place.
"""
def is_valid(board, row, col, num):
# Check if the number is not repeated in the current row, column and 3x3 sub-box
for i in range(9):
if board[row][i] == num:
return False
if board[i][col] == num:
return False
if board[3 * (row // 3) + i // 3][3 * (col // 3) + i % 3] == num:
return False
return True
def solve(board):
for row in range(9):
for col in range(9):
if board[row][col] == '.':
for num in map(str, range(1, 10)): # Check digits '1' to '9'
if is_valid(board, row, col, num):
board[row][col] = num
if solve(board):
return True
board[row][col] = '.'
return False
return True
solve(board)Explanation:
is_validfunction: This function checks whether placing a number in a specific cell is valid. It ensures that the number does not already exist in the current row, column, and the 3×3 sub-box of the board.solvefunction: This is the core of the backtracking algorithm. It iterates through each cell of the board. When it encounters an empty cell (denoted by'.'), it tries placing each digit from ‘1’ to ‘9’. For each valid placement, it recursively attempts to solve the rest of the board. If a placement leads to a dead end (i.e., no valid moves left), it backtracks by resetting the cell to'.'and trying the next digit.solveSudokumethod: This method is the entry point. It initializes the backtracking process by calling thesolvefunction on the board.
Solution in Javascript:
JavaScript
/**
* @param {character[][]} board
* @return {void} Do not return anything, modify board in-place instead.
*/
var solveSudoku = function(board) {
// Function to check if a number can be placed in the given cell
function isValid(board, row, col, num) {
// Check the row and column
for (let i = 0; i < 9; i++) {
if (board[row][i] === num) return false;
if (board[i][col] === num) return false;
// Check the 3x3 sub-box
if (board[3 * Math.floor(row / 3) + Math.floor(i / 3)][3 * Math.floor(col / 3) + (i % 3)] === num) return false;
}
return true;
}
// Function to solve the board using backtracking
function solve(board) {
for (let row = 0; row < 9; row++) {
for (let col = 0; col < 9; col++) {
if (board[row][col] === '.') {
for (let num = 1; num <= 9; num++) {
let charNum = num.toString();
if (isValid(board, row, col, charNum)) {
board[row][col] = charNum;
if (solve(board)) {
return true;
}
board[row][col] = '.';
}
}
return false;
}
}
}
return true;
}
// Start solving from the initial state of the board
solve(board);
};Solution in Java:
Java
class Solution {
public void solveSudoku(char[][] board) {
solve(board);
}
// Function to check if a number can be placed in the given cell
private boolean isValid(char[][] board, int row, int col, char num) {
for (int i = 0; i < 9; i++) {
// Check the row
if (board[row][i] == num) return false;
// Check the column
if (board[i][col] == num) return false;
// Check the 3x3 sub-box
if (board[3 * (row / 3) + i / 3][3 * (col / 3) + i % 3] == num) return false;
}
return true;
}
// Function to solve the board using backtracking
private boolean solve(char[][] board) {
for (int row = 0; row < 9; row++) {
for (int col = 0; col < 9; col++) {
// If the cell is empty
if (board[row][col] == '.') {
for (char num = '1'; num <= '9'; num++) {
// If placing num is valid
if (isValid(board, row, col, num)) {
board[row][col] = num;
// Recursively try to solve the rest of the board
if (solve(board)) {
return true;
}
// Backtrack if num doesn't lead to a solution
board[row][col] = '.';
}
}
// If no valid number can be placed, return false
return false;
}
}
}
// If all cells are filled correctly, return true
return true;
}
}Solution in C#:
C#
public class Solution {
public void SolveSudoku(char[][] board) {
Solve(board);
}
// Function to check if a number can be placed in the given cell
private bool IsValid(char[][] board, int row, int col, char num) {
for (int i = 0; i < 9; i++) {
// Check the row
if (board[row][i] == num) return false;
// Check the column
if (board[i][col] == num) return false;
// Check the 3x3 sub-box
if (board[3 * (row / 3) + i / 3][3 * (col / 3) + i % 3] == num) return false;
}
return true;
}
// Function to solve the board using backtracking
private bool Solve(char[][] board) {
for (int row = 0; row < 9; row++) {
for (int col = 0; col < 9; col++) {
// If the cell is empty
if (board[row][col] == '.') {
for (char num = '1'; num <= '9'; num++) {
// If placing num is valid
if (IsValid(board, row, col, num)) {
board[row][col] = num;
// Recursively try to solve the rest of the board
if (Solve(board)) {
return true;
}
// Backtrack if num doesn't lead to a solution
board[row][col] = '.';
}
}
// If no valid number can be placed, return false
return false;
}
}
}
// If all cells are filled correctly, return true
return true;
}
}