Leetcode and Lintcode

Valid Sudoku

Problem:

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.

Leetcode link
Lintcode link

My Solution:

This question is straight, no tricky ideas needed.
But it reviews the capacity of detailed implementation.

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
/*************************************************************************
	> File Name: ValidateSudoku.java
	> Author: Yao Zhang 
	> Mail: psyyz10@163.com 
	> Created Time: Thu 12 Nov 22:54:54 2015
 ************************************************************************/

public class ValidateSudoku{
    public boolean isValidSudoku(char[][] board){
        boolean[] visited = new boolean[9];

        for (int col = 0; col < 9; col++){
            Arrays.fill(visited,false);

            for (int row = 0; row < 9; row++){
                char current = board[col][row];
                if (!process(visited,current)){
                    return false;
                }
            }
        }


        for (int row = 0; row < 9; row++){
            Arrays.fill(visited,false);

            for (int col = 0; col < 9; col++){
                char current = board[col][row];
                if (!process(visited,current)){
                    return false;
                }
            }
        }

        for (int i = 0; i < 9; i += 3){
            for (int j = 0; j < 9; j += 3){
                Arrays.fill(visited, false);

                for (int k = 0; k < 9; k++){
                	// note use mod and division to track a small matrix
                    char current = board[i + k % 3][j + k / 3]; 
                    if (!process(visited, current)){
                        return false;
                    }
                }
            }
        }

        return true;
       
    }

    public boolean process(boolean[] visited, char current){
        if (current == '.')
            return true;
        
        int index = current - '1';
        if (visited[index])
            return false;
            
         visited[index] = true;
         return true;
    }
}

Related Problems: