This page explains Java solution to problem `Sudoku Solver`

using `Backtracking`

.

Write a program to solve a Sudoku puzzle by filling the empty cells. Empty cells are indicated by the character `.`

.

Input: A Sudoku Puzzle

Output: It's Solution number marked in Red

```
package com.vc.hard;
class SudokuSolver {
public void solveSudoku(char[][] board) {
solve(board);
}
private boolean solve(char[][] board) {
for(int row = 0; row < 9; row++) {
for(int col = 0; col < 9; col++) {
if(board[row][col] == '.') {
for(char num = '1'; num <= '9'; num++) {
if(isValid(board, row, col, num)) {
board[row][col] = num;
if(solve(board)) return true;
else board[row][col] = '.';
}
}
return false;
}
}
}
return true;
}
private boolean isValid(char[][] board, int row, int col, char num) {
int blkRow = (row / 3) * 3, blkCol = (col / 3) * 3;
for(int i = 0; i < 9; i++) {
if(board[i][col] == num) return false;
if(board[row][i] == num) return false;
if(board[blkRow + i / 3][blkCol + i % 3] == num) return false;
}
return true;
}
}
```

O(9!)

^{9}

For single Row there are 9 possibilities for first cell

8 possibilities for second cell

7 possibilities for third cell and so ....

So total there are 9! operations to fill in one row

There are 9 Rows in Sudoku, so total number of operations will be 9!^{9}

O(9 * 9) For storing 9 * 9 Grid