Sudoku Series

Valid Sudoku

Question

Determine if a Sudoku is valid, according to: Sudoku Puzzles - The Rules.

The Sudoku board could be partially filled, where empty cells are filled with the character ‘.’.

Analysis

数独规则：

每行每列及每个九宫格内不可有相同的数字（一共九个九宫格）

故针对每行每列及每个九宫格初始化一个hashset，当前格内数字不是’.’且无法插入到hashset时代表已经存在了重复的数字，返回false，否则直到最后返回true

int rowindex=3(i/3);
int colindex=3(i%3);

row_base, col_base的计算需要*3

Code

public class Solution {
    public boolean isValidSudoku(char[][] board) {
        for(int i=0;i<9;i++){
            HashSet<Character> row=new HashSet<Character>();
            HashSet<Character> col=new HashSet<Character>();
            HashSet<Character> cube=new HashSet<Character>();
            for(int j=0;j<9;j++){
                if(board[i][j]!='.'&&!row.add(board[i][j]))
                    return false;
                if(board[j][i]!='.'&&!col.add(board[j][i]))
                    return false;
                int rowindex=3*(i/3);
                int colindex=3*(i%3);
                if(board[rowindex+j/3][colindex+j%3]!='.'&&!cube.add(board[rowindex+j/3][colindex+j%3]))
                    return false;
            }
        }
        return true;
    }
}

Sudoku Solver

Question

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.

Analysis

上题已知如何检查一个sudoku是否valid，该题只需在当前格内为’.’的情况下，枚举1-9的情况后判断是否依旧valid，假如符合要求，进行填充，继续填充其他空格；假如不符要求，则返回false，回退继续尝试。

row_base, col_base的计算需要*3

Code

public class Solution {
    public void solveSudoku(char[][] board) {
        if(board==null||board.length==0)    
            return;
        solve(board);
    }
    
    private boolean solve(char[][] board){
        for(int i=0;i<9;i++){
            for(int j=0;j<9;j++){
                if(board[i][j]=='.'){
                    for(char c='1';c<='9';c++){
                        if(isValid(board,i,j,c)){
                            board[i][j]=c;
                            
                            if(solve(board))
                                return true;
                            else
                                board[i][j]='.';
                        }
                    }
                    return false;
                }
            }
        }
        return true;
    }
    
    private boolean isValid(char[][] board,int row, int col, char c){
        int rowbase=3*(row/3);
        int colbase=3*(col/3);
        for(int i=0;i<9;i++){
            if(board[i][col]!='.'&&board[i][col]==c)    return false;
            if(board[row][i]!='.'&&board[row][i]==c)    return false;
            if(board[rowbase+i/3][colbase+i%3]!='.'&&board[rowbase+i/3][colbase+i%3]==c)    return false;
        }
        return true;
    }
}