Solution for "Valid Sudoku"


  • 0
    C

    There are two parts to a solution in Sudoku:

    • Test whether a group might be acceptable, where a group is a row, column, or sub-box
    • Split the board into groups, and test each group.
    class Solution {
    

    The following code assumes that the characters have been put together into a group. It ensures that there is only one character from '1' to '9', and any number of '.' characters.

        public boolean isValidSet(List<Character> listChars) {
            Set<Character> setCharsSeen = new HashSet<Character>();
            
            for (char ch : listChars) {
                if (ch == '.') {
                    // Do nothing. Any combination of '.' is fine.
                } else if (ch >= '1' && ch <= '9') {
                    if (setCharsSeen.contains(ch)) {
                        return false; // We've seen this number before.
                    }
                    setCharsSeen.add(ch);
                } else {
                    return false; // It's not a . or 1-9.
                }
            }
            
            return true;
        }
    

    The following code (mostly) splits the Sudoku board into rows, columns, and sub-boxes, then passes those characters to isValidSet.

        public boolean isValidSudoku(char[][] board) {
            int column;
            int columngroup;
            List<Character> listChars;
            int row;
            int rowgroup;
            
            // Ensure that the sizes are correct.  
            if (board.length != 9) {
                return false;
            }
            for (row = 0; row < 9; row++) {
                if (board[row].length != 9) {
                    return false;
                }
            }
            
            // Check the rows.
            for (row = 0; row < 9; row++) {
                listChars = new LinkedList<Character>();
                for (column = 0; column < 9; column++) {
                    listChars.add(board[row][column]);
                }
                if (! isValidSet(listChars)) {
                    return false;
                }
            }
            
            // Check the columns.
            for (column = 0; column < 9; column++) {
                listChars = new LinkedList<Character>();
                for (row = 0; row < 9; row++) {
                    listChars.add(board[row][column]);
                }
                if (! isValidSet(listChars)) {
                    return false;
                }
            }
            
             // Check the sub-boxes.
            for (rowgroup = 0; rowgroup < 3; rowgroup++) {
                for (columngroup = 0; columngroup < 3; columngroup++) {
                    listChars = new LinkedList<Character>();
                    for (row = 0; row < 3; row++) {
                        for (column = 0; column < 3; column++) {
                            listChars.add(board[rowgroup * 3 + row][columngroup * 3 + column]);
                        }
                    }
                    if (!isValidSet(listChars)) {
                        return false;
                    }
                }
            }
            
            return true;
        }
    }
    

    Have fun!


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.