Problem Statement: Write a program to solve a given 9×9 Sudoku puzzle using a backtracking algorithm. The Sudoku grid contains integers from 1 to 9, with 0 representing empty cells that need to be filled. The solution should satisfy the following conditions: Approach: Example Code Implementations: C: #include <stdio.h>#include <stdbool.h>#define N 9bool isValid(int grid[N][N], int row, int col, int num) { for (int x = 0; x < N; x++) { if (grid[row][x] == num || grid[x][col] == num || grid[row – row % 3 + x / 3][col – col % 3 + x % 3] == num) { return false; } } return true;}bool solveSudoku(int grid[N][N]) { int row, col; bool emptyCell = false; for (row = 0; row < N; row++) { for (col = 0; col < N; col++) { if (grid[row][col] == 0) { emptyCell = true; break; } } if (emptyCell) break; } if (!emptyCell) return true; for (int num = 1; num <= 9; num++) { if (isValid(grid, row, col, num)) { grid[row][col] = num; if (solveSudoku(grid)) return true; grid[row][col] = 0; } } return false;}void printGrid(int grid[N][N]) { for (int r = 0; r < N; r++) { for (int d = 0; d < N; d++) { printf(“%d “, grid[r][d]); } printf(“\n”); }}int main() { int grid[N][N] = { {5, 3, 0, 0, 7, 0, 0, 0, 0}, {6, 0, 0, 1, 9, 5, 0, 0, 0}, {0, 9, 8, 0, 0, 0, 0, 6, 0}, {8, 0, 0, 0, 6, 0, 0, 0, 3}, {4, 0, 0, 8, 0, 3, 0, 0, 1}, {7, 0, 0, 0, 2, 0, 0, 0, 6}, {0, 6, 0, 0, 0, 0, 2, 8, 0}, {0, 0, 0, 4, 1, 9, 0, 0, 5}, {0, 0, 0, 0, 8, 0, 0, 7, 9} }; if (solveSudoku(grid)) { printGrid(grid); } else { printf(“No solution exists”); } return 0;} C++: #include <iostream>#include <vector>using namespace std;const int N = 9;bool isValid(vector<vector<int>>& grid, int row, int col, int num) { for (int x = 0; x < N; x++) { if (grid[row][x] == num || grid[x][col] == num || grid[row – row % 3 + x / 3][col – col % 3 + x % 3] == num) { return false; } } return true;}bool solveSudoku(vector<vector<int>>& grid) { int row, col; bool emptyCell = false; for (row = 0; row < N; row++) { for (col = 0; col < N; col++) { if (grid[row][col] == 0) { emptyCell = true; break; } } if (emptyCell) break; } if (!emptyCell) return true; for (int num = 1; num <= 9; num++) { if (isValid(grid, row, col, num)) { grid[row][col] = num; if (solveSudoku(grid)) return true; grid[row][col] = 0; } } return false;}void printGrid(vector<vector<int>>& grid) { for (int r = 0; r < N; r++) { for (int d = 0; d < N; d++) { cout << grid[r][d] << ” “; } cout << endl; }}int main() { vector<vector<int>> grid = { {5, 3, 0, 0, 7, 0, 0, 0, 0}, {6, 0, 0, 1, 9, 5, 0, 0, 0}, {0, 9, 8, 0, 0, 0, 0, 6, 0}, {8, 0, 0, 0, 6, 0, 0, 0, 3}, {4, 0, 0, 8, 0, 3, 0, 0, 1}, {7, 0, 0, 0, 2, 0, 0, 0, 6}, {0, 6, 0, 0, 0, 0, 2, 8, 0}, {0, 0, 0, 4, 1, 9, 0, 0, 5}, {0, 0, 0, 0, 8, 0, 0, 7, 9} }; if (solveSudoku(grid)) { printGrid(grid); } else { cout << “No solution exists” << endl; } return 0;} Java: public class SudokuSolver { public static boolean isValid(int[][] board, int row, int col, int num) { for (int x = 0; x < 9; x++) { if (board[row][x] == num || board[x][col] == num || board[row – row % 3 + x / 3][col – col % 3 + x % 3] == num) { return false; } } return true; } public static boolean solveSudoku(int[][] board) { for (int row = 0; row < 9; row++) { for (int col = 0; col < 9; col++) { if (board[row][col] == 0) { for (int num = 1; num <= 9; num++) { if (isValid(board, row, col, num)) { board[row][col] = num; if (solveSudoku(board)) return true; board[row][col] = 0; } } return false; } } } return true; } public static void printBoard(int[][] board) { for (int[] row : board) { for (int num : row) { System.out.print(num + ” “); } System.out.println(); } } public static void main(String[] args) { int[][] board = { {5, 3, 0, 0, 7, 0, 0, 0, 0}, {6, 0, 0, 1, 9, 5, 0, 0, 0}, {0, 9, 8, 0, 0, 0, 0, 6, 0}, {8, 0, 0, 0, 6, 0, 0, 0, 3}, {4, 0, 0, 8, 0, 3, 0, 0, 1}, {7, 0, 0, 0, 2, 0, 0, 0, 6}, {0, 6, 0, 0, 0, 0, 2, 8, 0}, {0, 0, 0, 4, 1, 9, 0, 0, 5}, {0, 0, 0, 0, 8, 0, 0, 7, 9} }; if (solveSudoku(board)) { printBoard(board); } else { System.out.println(“No solution exists”); } }} Python: def is_valid(board, row, col, num): for x in range(9): if board[row][x] == num or board[x][col] == num or \ board[row – row % 3 + x // 3][col – col % 3 + x % 3] == num: return False return Truedef solve_sudoku(board): for row in range(9): for col in range(9): if board[row][col] == 0: for num in range(1, 10): if is_valid(board, row, col, num): board[row][col] = num if solve_sudoku(board): return True board[row][col] = 0 return False return Truedef print_board(board): for row in board: print(” “.join(map(str, row)))if __name__ == “__main__”: board = [ [5, 3, 0, 0, 7, 0, 0, 0, 0], [6, 0, 0, 1, 9, 5, 0, 0, 0], [0, 9, 8, 0, 0, 0, 0, 6, 0], [8, 0, 0, 0, 6, 0, 0, 0, 3], [4, 0, 0, 8, 0, 3, 0, 0, 1], [7, 0, 0, 0, 2, 0, 0,