37. Sudoku Solver - jiejackyzhang/leetcode-note GitHub Wiki

Write a program to solve a Sudoku puzzle by filling the empty cells.

Empty cells are indicated by the character '.'.

You may assume that there will be only one unique solution.

解题思路为backtracking。这道题和皇后问题类似。 可以看作是9 Queen问题，而且有9种不同的皇后。 思想为一行一行来填数字，在一行中，将1-9依次填入，如果valid，则继续，如果不valid，则尝试不同位置。 若这一行无法valid，则返回上一行，改变上一行的数字位置。

public class Solution {
    
    int[] row;
    int[] col;
    int[] blk;
    
    public void solveSudoku(char[][] board) {
        row = new int[9];
        col = new int[9];
        blk = new int[9];
        for(int i = 0; i < 9; i++) {
            for(int j = 0; j < 9; j++) {
                if(board[i][j] == '.') continue;
                int num = 1 << (board[i][j] - '0');
                row[i] |= num;
                col[j] |= num;
                blk[i/3*3+j/3] |= num;
            }
        }
        for(int i = 1; i <= 9; i++) {
            if(solver(board, 0, 0, i)) return;
        }
    }
    
    private boolean solver(char[][] board, int i, int j, int number) {
        if(j == 9) {
            j = 0;
            i++;
        }
        if(i == 9) return true;
        while(board[i][j] != '.') {
            j = (j + 1) % 9;
            if(j % 9 == 0) i++;
            if(i == 9) return true;
        }
        int num = (1 << number);
        int k = i/3*3 + j/3;
        if(isValid(i, j, num)) {
            row[i] |= num;
            col[j] |= num;
            blk[k] |= num;
            board[i][j] = (char)('0' + number);
        } else return false;
        for(int n = 1; n <= 9; n++) {
            if(solver(board, i, j+1, n)) return true;
        }
        row[i] ^= num;
        col[j] ^= num;
        blk[k] ^= num;
        board[i][j] = '.';
        return false;
    }
    
    private boolean isValid(int i, int j, int num) {
        if((row[i] & num) > 0 || (col[j] & num) > 0 || (blk[i/3*3+j/3] & num) > 0) return false;
        return true;
    }
}