Leetcode-4/src/main/java/com/fishercoder/solutions/_36.java at master · codingwhite/Leetcode-4 · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
package com.fishercoder.solutions;

/**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 '.'.


 A partially filled sudoku which is valid.

 Note:
 A valid Sudoku board (partially filled) is not necessarily solvable. Only the filled cells need to be validated.*/
public class _36 {

    // this is my original solution, pretty straightforward, but lengthy, there's a very concise
    // version: https://discuss.leetcode.com/topic/9748/shared-my-concise-java-code, it uses
    //three HashSets in each loop, pretty cool!
    public boolean isValidSudoku(char[][] board) {
        for (int i = 0; i < 9; i++) {
            if (!isValidRow(board, i)) {
                return false;
            }
        }

        for (int j = 0; j < 9; j++) {
            if (!isValidCol(board, j)) {
                return false;
            }
        }

        for (int i = 0; i < 7; i = i + 3) {
            for (int j = 0; j < 7; j = j + 3) {
                if (!isValidSquare(board, i, j)) {
                    return false;
                }
            }
        }
        return true;
    }

    boolean isValidRow(char[][] board, int row) {
        int[] nums = new int[9];
        for (int i = 0; i < 9; i++) {
            nums[i] = 1;
        }
        for (int j = 0; j < 9; j++) {
            if (board[row][j] != '.') {
                nums[Character.getNumericValue(board[row][j]) - 1]--;
            }
        }
        for (int i : nums) {
            if (i < 0) {
                return false;
            }
        }
        return true;
    }

    boolean isValidCol(char[][] board, int col) {
        int[] nums = new int[9];
        for (int i = 0; i < 9; i++) {
            nums[i] = 1;
        }
        for (int i = 0; i < 9; i++) {
            if (board[i][col] != '.') {
                nums[Character.getNumericValue(board[i][col]) - 1]--;
            }
        }
        for (int i : nums) {
            if (i < 0) {
                return false;
            }
        }
        return true;
    }

    boolean isValidSquare(char[][] board, int row, int col) {
        int[] nums = new int[9];
        for (int i = 0; i < 9; i++) {
            nums[i] = 1;
        }
        for (int i = row; i < row + 3; i++) {
            for (int j = col; j < col + 3; j++) {
                if (board[i][j] != '.') {
                    nums[Character.getNumericValue(board[i][j]) - 1]--;
                }
            }
        }
        for (int i : nums) {
            if (i < 0) {
                return false;
            }
        }
        return true;
    }

    public static void main(String... strings) {
        _36 test = new _36();
        // char[][] board = new char[][]{
        // {'4', '3', '5', '2', '6', '9', '7', '8', '1'},
        // {'6', '8', '2', '5', '7', '1', '4', '9', '3'},
        // {'1', '9', '7', '8', '3', '4', '5', '6', '2'},
        // {'8', '2', '6', '1', '9', '5', '3', '4', '7'},
        // {'3', '7', '4', '6', '8', '2', '9', '1', '5'},
        // {'9', '5', '1', '7', '4', '3', '6', '2', '8'},
        // {'5', '1', '9', '3', '2', '6', '8', '7', '4'},
        // {'2', '4', '8', '9', '5', '7', '1', '3', '6'},
        // {'7', '6', '3', '4', '1', '8', '2', '5', '9'},
        // };

        // char[][] board = new char[][]{
        // {'.', '8', '7', '6', '5', '4', '3', '2', '1'},
        // {'2', '.', '.', '.', '.', '.', '.', '.', '.'},
        // {'3', '.', '.', '.', '.', '.', '.', '.', '.'},
        // {'4', '.', '.', '.', '.', '.', '.', '.', '.'},
        // {'5', '.', '.', '.', '.', '.', '.', '.', '.'},
        // {'6', '.', '.', '.', '.', '.', '.', '.', '.'},
        // {'7', '.', '.', '.', '.', '.', '.', '.', '.'},
        // {'8', '.', '.', '.', '.', '.', '.', '.', '.'},
        // {'9', '.', '.', '.', '.', '.', '.', '.', '.'},
        // };

        char[][] board = new char[][] {
                { '.', '.', '.', '.', '5', '.', '.', '1', '.' },// this upper right corner 3*3
                                                                // square is invalid, '1' appears
                                                                // twice
                { '.', '4', '.', '3', '.', '.', '.', '.', '.' },
                { '.', '.', '.', '.', '.', '3', '.', '.', '1' },
                { '8', '.', '.', '.', '.', '.', '.', '2', '.' },
                { '.', '.', '2', '.', '7', '.', '.', '.', '.' },
                { '.', '1', '5', '.', '.', '.', '.', '.', '.' },
                { '.', '.', '.', '.', '.', '2', '.', '.', '.' },
                { '.', '2', '.', '9', '.', '.', '.', '.', '.' },
                { '.', '.', '4', '.', '.', '.', '.', '.', '.' }, };

        // ["....5..1.",".4.3.....",".....3..1","8......2.","..2.7....",".15......",".....2...",".2.9.....","..4......"]

        System.out.println(test.isValidSudoku(board));
    }
}