# Sudoku Solver
Write a program to solve a Sudoku puzzle by filling the empty cells.
A sudoku solution must satisfy **all of the following rules**:
1. Each of the digits `1-9` must occur exactly once in each row.
2. Each of the digits `1-9` must occur exactly once in each column.
3. Each of the digits `1-9` must occur exactly once in each of the 9 `3x3` sub-boxes of the grid.
The `'.'` character indicates empty cells.
**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:
**Constraints:**
* `board.length == 9`
* `board[i].length == 9`
* `board[i][j]` is a digit or `'.'`.
* It is **guaranteed** that the input board has only one solution.
### Solutions
This problem can be solved using backtracking, which is a common technique for solving constraint satisfaction problems like Sudoku. The idea is to fill the cells one by one, and whenever we find that current cell cannot lead to a solution, we empty the cell (backtrack) and move on to the next cell.
```csharp
public class Solution {
public void SolveSudoku(char[][] board) {
Solve(board);
}
private bool Solve(char[][] board) {
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
if (board[i][j] == '.') {
for (char c = '1'; c <= '9'; c++) {
if (IsValid(board, i, j, c)) {
board[i][j] = c;
if (Solve(board)) {
return true;
} else {
board[i][j] = '.'; // undo the choice if it leads to no solution
}
}
}
return false; // return false if no valid numbers can be placed in the current cell
}
}
}
return true; // sudoku is solved
}
private bool IsValid(char[][] board, int row, int col, char c) {
for (int i = 0; i < 9; i++) {
if (board[i][col] == c) return false; // check column
if (board[row][i] == c) return false; // check row
if (board[3 * (row / 3) + i / 3][3 * (col / 3) + i % 3] == c) return false; // check 3*3 box
}
return true;
}
}
```
In this code, `Solve` is a recursive function that tries to fill the cells from top to bottom and left to right. For each empty cell, it tries all possible numbers from 1 to 9, and calls itself to fill the next cell. If it finds that the current cell cannot lead to a solution (no valid numbers can be placed or the recursive call returns false), it empties the cell (backtracks) and continues with the next number. If it has tried all numbers and none of them work, it returns false to backtrack to the previous cell. The process continues until all cells are filled.
`IsValid` is a helper function that checks if a number can be placed in a certain cell according to the Sudoku rules.
The time complexity of this solution is O(9^(n*n)), where n is the number of empty cells, because in the worst case we need to try 9 numbers for each empty cell. The space complexity is O(n*n) because of the recursion stack (depth-first search).
---
# Agent Instructions: Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.
Perform an HTTP GET request on the current page URL with the `ask` query parameter:
```
GET https://docs-57.gitbook.io/data-structure-and-algorithms/problems/backtracking/sudoku-solver.md?ask=
```
The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.
Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.