36. Valid Sudoku

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

250px-sudoku-by-l2g-20050714-svg

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

A partially filled sudoku which is valid.

思路:
数独规则,9行9列的棋盘,每行,每列和每个33的小方格都不能有重复的数字,并且数字只能是0-9
分别判断行,列跟3
3小方格中是否满足了解。 可以用Hashset 或者数组来解决

public class Solution {
    public boolean isValidSudoku(char[][] board) {
        if (board.length != 9 || board[0].length != 9 ) return false;
        HashSet<Integer> set;
        // validate col

        for (int i = 0; i < 9; i++) {
            set = new HashSet<Integer>();
            for (int j = 0; j < 9; j++) {
                char cell = board[i][j];
                if (cell == '.') continue;
                if (cell < '0' || cell > '9') return false;
                int val = cell - '0';
                if (set.contains(val)) {
                    return false;
                }
                set.add(val);
            }
        }
        // validate col

        for(int j = 0; j < 9; j++) {
            set = new HashSet<Integer>();
            for (int i = 0; i < 9; i++) {
                char cell = board[i][j];
                if (cell == '.') continue;
                if (cell < '0' || cell > '9') return false;
                int val = cell - '0';
                if (set.contains(val)) {
                    return false;
                }
                set.add(val);
            }
        }

        // validate subsquare

        for (int i = 0; i < 9; i+=3) {
            for (int j = 0; j < 9; j+=3) {
                set = new HashSet<Integer>();
                for (int k = i; k < i + 3; k++) {
                    for (int l = j; l < j + 3; l++) {
                        char cell = board[k][l];
                        if (cell == '.') continue;
                        if (cell < '0' || cell > '9') return false;
                        int val = cell - '0';
                        if (set.contains(val)) {
                            return false;
                        }
                        set.add(val);
                    }
                }
            }
        }
        return true;
    }
}

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s