Valid Sudoku

Question

Determine if a Sudoku is valid. The Sudoku board could be partially filled, where empty cells are filled with the character '.'

Solution

自己的思路跟參考解答是差不多的，就是用三個 HashSet 分別去紀錄 row, column, cube 的數字有沒有 valid。我想了一下子，但實做起來就很癟手癟腳，下面是我第一次寫的 code，真的是太蠢了一定要記錄一下：

public boolean isValidSudoku(char[][] board) {
        if (board.length < 3 || board[0].length < 3) {
            return false;
        }

        ArrayList<Set<Character>> rowList = new ArrayList<Set<Character>>();
        ArrayList<Set<Character>> colList = new ArrayList<Set<Character>>();
        ArrayList<Set<Character>> nineList = new ArrayList<Set<Character>>();

        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if (rowList.size() <= i) {
                    rowList.add(new HashSet<Character>());
                    rowList.get(i).add(board[i][j]);
                } else {
                    if (board[i][j] != '.' && rowList.get(i).contains(board[i][j]) || isNotValid(board[i][j])) {
                        return false;
                    } else {
                        rowList.get(i).add(board[i][j]);
                    }
                }

                if (colList.size() <= j) {
                    colList.add(new HashSet<Character>());
                    colList.get(j).add(board[i][j]);
                } else {
                    if (board[i][j] != '.' && colList.get(j).contains(board[i][j]) || isNotValid(board[i][j])) {
                        System.out.println("col");
                        return false;
                    } else {
                        colList.get(j).add(board[i][j]);
                    }
                }

                if (nineList.size() <= (board[0].length / 3 * (i / 3) + (j / 3))) {
                    nineList.add(new HashSet<Character>());
                    nineList.get(board[0].length / 3 * (i / 3) + (j / 3)).add(board[i][j]);
                } else {
                    if (board[i][j] != '.' && nineList.get(board[0].length / 3 * (i / 3) + (j / 3)).contains(board[i][j]) || isNotValid(board[i][j])) {

                        return false;
                    } else {
                        nineList.get(board[0].length / 3 * (i / 3) + (j / 3)).add(board[i][j]);
                    }
                }
            }
        }

        return true;
    }

    public boolean isNotValid(char c) {
        if (c == '.') {
            return false;
        }
        if (Character.getNumericValue(c) > 9 || Character.getNumericValue(c) < 1) {
            return true;
        } else if (Character.getNumericValue(c) != (int)Character.getNumericValue(c)) {
            return true;
        }

        return false;
    }

參考解答的重點在兩個地方：

1. 寫到 column 的時候，改用 board[j][i]，如此可以在 row 的遍歷裡，走完 column 的遍歷
2. 矩陣型的 linear transform：rowIndex = 3 (i/3), columnIndex = 3 (i / 3)。最後求值的時候為 board[rowIndex + j / 3][colIndex + j % 3]

因此可以歸納出，在 2d 矩陣裡面， i 是掌管第幾 row 第幾個 column： row = i / 3; col = i % 3;

而實際位置在哪裡，這個 offset 就由 j 來掌管。對照一下參考解答：

public boolean isValidSudoku(char[][] board) {
    for(int i = 0; i<9; i++){
        HashSet<Character> rows = new HashSet<Character>();
        HashSet<Character> columns = new HashSet<Character>();
        HashSet<Character> cube = new HashSet<Character>();
        for (int j = 0; j < 9;j++){
            if(board[i][j]!='.' && !rows.add(board[i][j]))
                return false;
            if(board[j][i]!='.' && !columns.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;
}