Backtracking is a general algorithm for finding all solutions to some computational problems. Here are the basic rules of sudoku.

1. It is a 9x9 grid. It is divided into 6 3x3 blocks.
2. Each block must contain all number numbers from 1 to 9.
3. There must be no same number in the same row, column, block.
4. Initially, every block is filled with 0s.
   

An unfilled board looks like this.

So, the algorithm is that for each block in a 3x3 block; we check if the number we're placing is safe or not. If it is, we place it, or else, we remove and put back 0.

Is it Safe?

To know if a position is safe or not, we must check the row and the column if the number we're placing is not already present. Also, we must check that the block also doesn't contain the element. How do we know which 3x3 block we're in? To know that we just need to do update the row and column values as

row = row - (row % 3)

column = column - (column % 3)

The reason to do this is that we need the starting index of the 3x3 block. So we need the difference between the current row and mod of row and 3.

bool isSafe(int r, int c, int v) {
    for (int t=0;t<9;++t)
        if (board[r][t] == v) return false;         // Check every column of the given row.

    for (int t=0;t<9;++t)
        if (board[t][c] == v) return false;         // Check every row of the given column.

    r = r - (r % 3);
    c = c - (c % 3);
    for (int t=0;t<3;++t) {
        for (int j=0;j<3;++j) {
            if (board[t + r][j + c] == v) return false;
        }
    }
    return true;
}

Done?

To every recursive problem, there must be a base-case. So, in this case; the base-case would be if all the blocks are filled with numbers. Checking this is simple. As we have initialized all the blocks with 0 and we place numbers starting from 1 to 9, if there is some 0 present anywhere in the board, it means that the board is not filled yet.

bool isBoardFilled(int &t, int &j) {
    for (t=0;t<9;++t) {
        for (j=0;j<9;++j) {
            if (!board[t][j]) return false;        // Non-filled cell found.
        }
    }
    return true;        // All cells filled.
}

You can see that the parameters t and j have been passed as a reference. It is because we start filling from the topmost row-leftmost column to the bottom-most row last column. So going from left to right is a good idea.

Backtrack

So now we've got the functions we need. All we need to do is search for the solution.

• If we find that the board is filled, we return True. It will be always true as we only call this function recursively when the position we're placing is SAFE.

• We need to check all 9 at that position. So, we'll need a loop running from 1 to 9.

• For every iteration, check if the position(row, column, i) is safe or not. If so, place the number at position (r, c).

• Now, we recursively call the function to go to the next position. Most importantly, if that recursive call returns true, we return true. Else, backtrack and replace the (r, c) value with 0. Just because we didn't get the solution we need.

• Finally, the function will return false as if the function came out of the loop means that we've to change previous values. So we return false and backtrack our mistakes.

bool Solve() {
    int r, c;
    if (isBoardFilled(r, c)) return true;

    for (int t=1;t<10;++t) {
        if (isSafe(r, c, t)) {
            board[r][c] = t;        // Place number at current cell.
            if (Solve()) return true;        // If it leads to correct solution, return true.
            board[r][c] = 0;        // Else, backtrack the cell state and choose next number.
        }
    }
    return false;        // No numbers from 1-9 gave a correct solution. So, some fault with previous positions. Correct them and come back.
}

The Final result

Complete Solution here