卖萌的弱渣

I am stupid, I am hungry.

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.

Solution

对于9*9矩阵中的每个元素 1. 检查他所在行是否和他重复 2. 检查他所在列是否和他重复 3. 检查他所在3*3 小矩阵是否和他重复

  • Python
(Valid-Sudoku.py) download
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

class Solution(object):
    def isValidSudoku(self, board):
        """
        :type board: List[List[str]]
        :rtype: bool
        """

        def check(x,y,board):
            # 检查横行是否和board[x][y]重复
            for i in range(9):
                if y != i and board[x][i] == board[x][y]:
                    return False

            # 检查纵行是否和board[x][y]重复
            for i in range(9):
                if x != i and board[i][y] == board[x][y]:
                    return False

            # 检查3*3的小矩阵是否和board[x][y]重复
            for i in range(3):
                for j in range(3):
                    # x/3 找到是第几个3*3的矩阵
                    if x/3*3+i!=x and y/3*3+j!=y and board[x/3*3+i][y/3*3+j] == board[x][y]:
                        return False
            return True


        for i in range(9):
            for j in range(9):
                if board[i][j] == ".":
                    continue
                if check(i,j,board) == False:
                    return False
        return True
  • Java
(Valid-Sudoku.java) download
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

public class Solution {
    public boolean isValidSudoku(char[][] board) {
        int row = board.length;
        int col = board[0].length;

        for(int i=0;i<row;i++){
            for (int j=0;j<col;j++){
                if (board[i][j]=='.') continue;

                // 行
                int k=0;
                while (k<9){
                    if(j!=k && board[i][k] == board[i][j])
                        return false;
                    k+=1;
                }

                // 列
                k = 0;
                while(k<9){
                    if (i!=k && board[k][j] == board[i][j])
                        return false;
                    k+=1;
                }

                // ３×３
                for (int m=0;m<3;m++){
                    for (int n=0;n<3;n++){
                        if (i/3*3+m !=i && j/3*3+n != j && board[i][j] == board[i/3*3+m][j/3*3+n])
                            return false;
                    }
                }
            }
        }
        return true;
    }
}