Sudoku Solver

Fill every empty cell of a tiny 4 × 4 Sudoku (four 2 × 2 boxes) so each row, column and box holds 1 to 4 once each.

The idea

Find the first empty cell and try digits 1 to 4 in it. A digit is valid only if it is not already in that row, that column, or that cell’s 2 × 2 box. Place a valid digit and solve the rest of the board; if that fails everywhere further on, erase the digit and try the next one.

Code

public static bool Solve(int[][] board) {
    for (int r = 0; r < 4; r++)
        for (int c = 0; c < 4; c++)
            if (board[r][c] == 0) {
                for (int v = 1; v <= 4; v++) {
                    if (!IsValid(board, r, c, v)) continue;
                    board[r][c] = v;
                    if (Solve(board)) return true;
                    board[r][c] = 0; // backtrack
                }
                return false;
            }
    return true;
}

static bool IsValid(int[][] b, int r, int c, int v) {
    for (int i = 0; i < 4; i++)
        if (b[r][i] == v || b[i][c] == v) return false;
    int br = r / 2 * 2, bc = c / 2 * 2;
    for (int i = 0; i < 2; i++)
        for (int j = 0; j < 2; j++)
            if (b[br + i][bc + j] == v) return false;
    return true;
}

Tips

• IsValid only has to check the row, the column and one small box, never the whole board, which is what makes each attempt cheap.
• When every digit at a cell fails, the function returns false and the caller’s own loop moves to its next digit. That is the backtrack, one call frame at a time.

In the .NET library

A wrong digit can look locally valid (its own row, column and box are fine) and still make a later cell unsolvable. That is exactly what forces a real backtrack here, unlike N-Queens, where IsSafe alone is often enough to avoid dead ends.