Sudoku Solver
Write a program to solve a Sudoku puzzle. The program should take a 2D array representing the puzzle as input, where empty cells are represented by 0. The program should fill in the empty cells with numbers from 1 to 9 such that each row, column, and 3x3 sub-grid contains each number exactly once.
Constraints:
- The input puzzle is a 9x9 2D array
- The input puzzle contains numbers from 0 to 9
- The input puzzle is valid (i.e., it is possible to solve it)
Examples:
Input: [[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]]
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 program fills in the empty cells with numbers from 1 to 9 such that each row, column, and 3x3 sub-grid contains each number exactly once.
Solutions
Backtracking
The backtracking approach is used to solve the Sudoku puzzle. The program tries to fill in the empty cells with numbers from 1 to 9. If a number is valid (i.e., it does not appear in the same row, column, or 3x3 sub-grid), the program recursively tries to fill in the rest of the puzzle. If it is not possible to fill in the rest of the puzzle, the program backtracks and tries a different number.
class Solution {
public:
void solveSudoku(vector<vector<char>>& board) {
solve(board);
}
bool solve(vector<vector<char>>& board) {
for (int i = 0;
i < 9;
i++) {
for (int j = 0;
j < 9;
j++) {
if (board[i][j] == '\u0000') {
for (int num = 1;
num <= 9;
num++) {
if (isValid(board, i, j, (char) (num + '0'))) {
board[i][j] = (char) (num + '0');
if (solve(board)) return true;
board[i][j] = '\u0000';
}
}
return false;
}
}
}
return true;
}
bool isValid(vector<vector<char>>& board, int row, int col, char num) {
for (int i = 0;
i < 9;
i++) {
if (board[row][i] == num) return false;
}
for (int i = 0;
i < 9;
i++) {
if (board[i][col] == num) return false;
}
int startRow = row - row % 3;
int startCol = col - col % 3;
for (int i = 0;
i < 3;
i++) {
for (int j = 0;
j < 3;
j++) {
if (board[i + startRow][j + startCol] == num) return false;
}
}
return true;
}
}
;Follow-up:
How would you optimize the solution to solve larger Sudoku puzzles?
