Sudoku Solver

The problem, simply

You get a 9 by 9 sudoku board. Some squares have digits, and empty squares hold a .. Fill every empty square with a digit from 1 to 9 so that each row, each column and each of the nine 3 by 3 boxes has every digit exactly once.

Change the board in place. You may assume the puzzle has exactly one answer.

A story to remember it

Picture it

Examples

Way 1: the simple way

Find the first empty square. Try digits 1 to 9. For each digit, scan its row, its column and its box to see if it is already there. If it fits, write it and solve the rest. If the rest fails, erase it.

1. Look for the first . on the board. If there is none, the board is solved.
2. For each digit, check the 9 squares of the row, the 9 of the column and the 9 of the box.
3. If it fits, write it and solve again. If that works, return true.
4. If no digit works, erase and return false.

class Solution {
    public void solveSudoku(char[][] board) {
        solve(board);
    }

    private boolean solve(char[][] board) {
        for (int r = 0; r < 9; r++) {
            for (int c = 0; c < 9; c++) {
                if (board[r][c] != '.') continue;
                for (char d = '1'; d <= '9'; d++) {
                    if (fits(board, r, c, d)) {
                        board[r][c] = d;
                        if (solve(board)) return true;
                        board[r][c] = '.';               // erase the wrong guess
                    }
                }
                return false;                            // nothing fits here
            }
        }
        return true;                                     // no empty square left
    }

    private boolean fits(char[][] board, int r, int c, char d) {
        for (int i = 0; i < 9; i++) {
            if (board[r][i] == d || board[i][c] == d) return false;
            if (board[3 * (r / 3) + i / 3][3 * (c / 3) + i % 3] == d) return false;
        }
        return true;
    }
}

How long it takes: with m empty squares, up to 9 choices each, and each check reads 27 squares, so O(9^m * 27) in the worst case. It also rescans the board from the top to find the next empty square every time. Extra room: the call stack is at most m deep, O(m).

Way 2: the clever way

Two upgrades.

First, keep a note of which digits each row, column and box already has. Store each note as one number whose bits are switches: bit d is on when digit d is used. Then "does d fit here?" is one look at three numbers.

Second, list the empty squares once at the start, and walk that list by index instead of rescanning the board.

1. Read the board once. Turn on bit d in rows[r], cols[c] and boxes[b] for every given digit. Save every empty square in a list.
2. For empty square number k, the used digits are rows[r] | cols[c] | boxes[b].
3. Try each digit whose bit is off: switch its bits on, write it, solve square k + 1.
4. If that fails, switch the bits off and erase. This is the backtracking.

import java.util.*;

class Solution {
    private final int[] rows = new int[9], cols = new int[9], boxes = new int[9];
    private final List<int[]> empty = new ArrayList<>();

    public void solveSudoku(char[][] board) {
        for (int r = 0; r < 9; r++) {
            for (int c = 0; c < 9; c++) {
                if (board[r][c] == '.') empty.add(new int[]{r, c});
                else flip(r, c, board[r][c] - '0');      // note the given digit (givens never repeat)
            }
        }
        fill(0, board);
    }

    private boolean fill(int k, char[][] board) {
        if (k == empty.size()) return true;              // every empty square is filled
        int r = empty.get(k)[0], c = empty.get(k)[1];
        int used = rows[r] | cols[c] | boxes[(r / 3) * 3 + c / 3];
        for (int d = 1; d <= 9; d++) {
            if ((used >> d & 1) == 1) continue;          // d is taken nearby
            flip(r, c, d);
            board[r][c] = (char) ('0' + d);
            if (fill(k + 1, board)) return true;
            flip(r, c, d);                               // switch the bits back off
            board[r][c] = '.';
        }
        return false;
    }

    private void flip(int r, int c, int d) {
        int bit = 1 << d;
        rows[r] ^= bit;
        cols[c] ^= bit;
        boxes[(r / 3) * 3 + c / 3] ^= bit;
    }
}

How long it takes: still O(9^m) in the very worst case, but each try is now O(1), and there is no rescanning. Real puzzles finish in milliseconds. Extra room: three arrays of 9 numbers, the list of empty squares and the call stack, O(m).

Watch out for

• The box formula. The box of (r, c) starts at row 3 * (r / 3) and column 3 * (c / 3). Its number from 0 to 8 is (r / 3) * 3 + c / 3.
• Forgetting to undo the notes. Erasing the board square is not enough if the bit is still on.
• Characters versus numbers. board[r][c] - '0' turns '7' into 7, and (char) ('0' + d) turns it back.

What interviewers ask next

• How do you make it much faster? Always fill the empty square with the fewest digits left first. A square with one option is forced, and a square with zero options is a dead end you find at once. Integer.bitCount(~used & 0x3FE) counts the options. This is called the most constrained variable rule.
• Check if a board is valid, without solving it (LeetCode 36). One pass with the same three arrays: if a bit is already on when you add a digit, it is invalid.
• Count the solutions, to check a puzzle is fair. Do not stop at the first one. Keep searching and stop once you find a second.
• Can this be seen as graph coloring? Yes. Each square is a dot, squares that share a row, column or box are joined, and the 9 digits are 9 colors.

Remember this

Grown-up words: erasing a wrong guess is backtracking, the notes per row, column and box are bitmasks, filling the most limited square first is the minimum remaining values heuristic, and the whole thing is a constraint satisfaction problem.