leetcode: Valid Sudoku

问题描述：

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.

原问题链接：https://leetcode.com/problems/valid-sudoku/

 

问题分析

　　对于数独问题来说，我们首先要熟悉它本身的规则。它是一个9 x 9的矩阵。作为一个合法的数独表示，它要求里面每一行，每一列都取值自1到９，但是这些数字只能出现１次，而且不能有重复。同时，如果将这个矩阵９等分的话，则有９个3 x 3的小矩阵。对于这些小的矩阵来说，它们里面的每个数字也只能出现一次不能重复。

　　所以要解决这个问题一个最直观的办法就是判断它的每一行，每一列以及每个小矩阵是否都符合要求。按照这个思路，我们每次判断每一行是否合法的时候，只需要用一个set，将碰到的元素和set进行对比。如果该元素非法，则返回false。如果该元素是'.'，不用继续比较，继续下一步，如果集合里有这个元素，那么说明该矩阵非法，返回false。

　　这里稍微困难一点的地方就是怎么来判断里面的９个小矩阵呢？假设从最左上角的那个矩阵开始，也就是这个时候最起始点的索引位置是i = 0, j = 0。按照我们每一行一行从上到下遍历的顺序，它的访问方式如下图：

 　　这里每一条横线可以表示i的值。按照这个顺序，它们的索引位置变化按照如下的顺序(0, 0) -> (0, 1) -> (0, 2) -> (1, 0) -> (1, 1) -> (1, 2)。对于这个矩阵来说，它总共有９个元素。如果我们换一种方式来考虑。假设给定了初始的点i, j，不用i, j构成的双重循环，有没有别的办法来遍历整个矩阵呢？针对这种情况，我们可以用一个变量k来循环。从０到9。对于里面对应的每个位置的关系可以定义如下: i = i + k / 3; j = j + k % 3;

　　所以在给定初始i, j的情况下会有这么一个表达方式：

for(int k = 0; k < 9; k++) 
    board[i + k / 3][j + k % 3] = xxx;

 　它和我们使用如下的方式来遍历是等价的：　　

for(int l = i; l < i + 3; l++) {
    for(int r = j; r < j + 3; r++)
        board[l][r] = xxx;
}

    上述的表达式能够简化部分代码。剩下的部分就是该怎么把这个部分和所有i, j的位置给串起来。对于里面的９个小矩阵，我们现在只需要找到它们每个矩阵最开始的位置。很直观，它们的位置如下：(0, 0)  (0, 3), (0, 6)  (3, 0), (3, 3) (3, 6) (6, 0), (6, 3) (6, 6)。我们可以很直接的用两个循环就解决了：

for(int i = 0; i < 9; i += 3) {
    for(int j = 0; j < 9; j += 3) {
        // xxxx
    }
}

 　　最终可以得到如下的代码：

 

public class Solution {
    public boolean isValidSudoku(char[][] board) {
        if(board == null || board.length != 9 || board[0].length != 9) return false;
        int n = board.length;
        for(int i = 0; i < n; i++) {
            Set<Character> set = new HashSet<>();
            for(int j = 0; j < n; j++) {
                if(!isValid(set, board, i, j)) return false;
            }
        }
        for(int j = 0; j < n; j++) {
            Set<Character> set = new HashSet<>();
            for(int i = 0; i < n; i++) {
                if(!isValid(set, board, i, j)) return false;
            }
        }
        for(int i = 0; i < n; i += 3) {
            for(int j = 0; j < n; j += 3) {
                Set<Character> set = new HashSet<>();
                for(int k = 0; k < n; k++) if(!isValid(set, board, i + k / 3, j + k % 3)) return false;
            }
        }
        return true;
    }
    
    private boolean isValid(Set<Character> set, char[][] board, int i, int j) {
        if(board[i][j] == '.') return true;
        if(board[i][j] < '1' || board[i][j] > '9') return false;
        if(set.contains(board[i][j])) return false;
        set.add(board[i][j]);
        return true;
    }
}

 　　上述代码的时间复杂度为O(N ^ 2)。

 

总结

 　这个问题的思路并不复杂，重要的是要能找到一个对问题解决方法的一个简洁的表达方式。