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:

Each of the digits 1-9 must occur exactly once in each row.
Each of the digits 1-9 must occur exactly once in each column.
Each of the the digits 1-9 must occur exactly once in each of the 9 3x3 sub-boxes of the grid.
Empty cells are indicated by the character '.'.

分析
For each empty cell, recursively try all possible options, maintaining that your choice does not violate the invariants of Sudoku

答案

class Solution {
    List<HashSet<Character>> sets;
    public void solveSudoku(char[][] board) {
        sets = new ArrayList<HashSet<Character>>();
        for(int i = 0; i < 27; i++)
            sets.add(new HashSet<>());
        int start_i = -1, start_j = -1;
        for(int i = 0; i < board.length; i++) {
            for(int j = 0; j < board[0].length; j++) {
                if(board[i][j] != '.') {
                    // Which square?
                    int k = (i / 3) * 3 + (j / 3);
                    sets.get(i).add(board[i][j]);
                    sets.get(9 + j).add(board[i][j]);
                    sets.get(18 + k).add(board[i][j]);
                }
                else {
                    if(start_i == -1) {
                        start_i = i;
                        start_j = j;
                    }
                }
            }
        }
        recur(board, start_i, start_j);
        System.out.println();
    }

    public boolean recur(char[][] board, int curr_i, int curr_j) {
        // For each empty cell, try all availiable options, if none can be used, then something is wrong
        for(int i = curr_i; i < board.length; i++) {
            int initial_j;
            if(i == curr_i) initial_j = curr_j;
            else initial_j = 0;
            for(int j = initial_j; j < board[0].length; j++) {

                if(board[i][j] != '.') continue;
                boolean good = false;
                // Which square?
                int k = (i / 3) * 3 + (j / 3);
                for(char p = '1'; p <= '9'; p++) {
                    if(!sets.get(i).contains(p) && !sets.get(9 + j).contains(p) && !sets.get(18 + k).contains(p)) {
                        // Find next i and j
                        int new_j = (j + 1) % 9, new_i = i;
                        if(new_j < j) new_i = new_i + 1;

                        board[i][j] = p;
                        sets.get(i).add(board[i][j]);
                        sets.get(9 + j).add(board[i][j]);
                        sets.get(18 + k).add(board[i][j]);



                        good = recur(board, new_i, new_j);
                        if(good) return true;

                        sets.get(i).remove(board[i][j]);
                        sets.get(9 + j).remove(board[i][j]);
                        sets.get(18 + k).remove(board[i][j]);
                        board[i][j] = '.';
                    }
                }
                if(!good) return false;
            }
        }
        return true;
    }
}