LeetCode - Valid Sudoku | Darren's Blog

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 '.'. Below is a partially filled sudoku which is valid.

Each row must have the numbers 1-9 occuring just once.

Each column must have the numbers 1-9 occuring just once.

And the numbers 1-9 must occur just once in each of the 9 sub-boxes of the grid.

• With three passes

public boolean isValidSudoku(char[][] board) {

    HashSet<Character> set = new HashSet<Character>();

    // Check for each row

    for (int i = 0; i < 9; i++) {

        for (int j = 0; j < 9; j++) {

            if (board[i][j] == '.')

                continue;

            if (set.contains(board[i][j]))

                return false;

            set.add(board[i][j]);

        }

        set.clear();

    }

 

    // Check for each column

    for (int j = 0; j < 9; j++) {

        for (int i = 0; i < 9; i++) {

            if (board[i][j] == '.')

                continue;

            if (set.contains(board[i][j]))

                return false;

            set.add(board[i][j]);

        }

        set.clear();

    }

 

    // Check for each sub-grid

    for (int k = 0; k < 9; k++) {

        for (int i = k/3*3; i < k/3*3+3; i++) {

            for (int j = (k%3)*3; j < (k%3)*3+3; j++) {

                if (board[i][j] == '.')

                    continue;

                if (set.contains(board[i][j]))

                    return false;

                set.add(board[i][j]);

            }

        }

        set.clear();

    }

 

    return true;

}

Code from http://xixiaogualu.blogspot.com/2013/09/leetcode-valid-sudoku.html

public boolean isValidSudoku(char[][] board) {

        for(int i=0;i<9;i++){   //check rows

            boolean[] checker=new boolean[10];

            for(int k=1;k<10;k++)

                checker[k]=false;

            for(int j=0;j<9;j++){

                char c=board[i][j];

                //System.out.println(c-'0');

                if(c=='.')

                    continue;

                else if(checker[c-'0'])

                    return false;

                else

                    checker[c-'0']=true;

            }

        }

        for(int i=0;i<9;i++){   //check rows

            boolean[] checker=new boolean[10];

            for(int k=1;k<10;k++)

                checker[k]=false;

            for(int j=0;j<9;j++){

                char c=board[j][i];

                if(c=='.')

                    continue;

                else if(checker[c-'0'])

                    return false;

                else

                    checker[c-'0']=true;

            }

        }

        for(int i=0;i<9;i+=3)   //check 9-sub

            for(int j=0;j<9;j+=3){

                boolean[] checker=new boolean[10];

                for(int k=1;k<10;k++)

                    checker[k]=false;

                for(int m=0;m<3;m++)

                    for(int n=0;n<3;n++){

                        char c=board[i+m][j+n];

                        if(c=='.')

                            continue;

                        else if(checker[c-'0'])

                            return false;

                        else

                            checker[c-'0']=true;

                    }

            }

        return true;

    }

• With one pass

public boolean isValidSudoku(char[][] board) {

    // rowChecker[i][j]=true: j appears in row i

    boolean[][] rowChecker = new boolean[9][9];

    // columnChecker[i][j]=true: j appears in column i

    boolean[][] columnChecker = new boolean[9][9];

    // gridChecker[i][j]=true: j appears in grid i

    // numberring from left to right, then top to bottom

    boolean[][] gridChecker = new boolean[9][9];

 

    // One-pass scan in row-major manner

    for (int i = 0; i < 9; i++) {

        for (int j = 0; j < 9; j++) {

            if (board[i][j] == '.')

                continue;

            int val = board[i][j] - '1';

            // Check for the corresponding row, column, and grid at the same time

            if (rowChecker[i][val] || columnChecker[j][val] || gridChecker[i/3*3+j/3][val])

                return false;

            rowChecker[i][val] = columnChecker[j][val] = gridChecker[i/3*3+j/3][val] = true;

        }

    }

    return true;

}

Read full article from LeetCode - Valid Sudoku | Darren's Blog