Tuesday, September 9, 2014

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.
Understand the problem:
The problem asks for determining if a Sudoku is valid. Note that only the filled cells need to be validated. The rule of Sudoku is each row should only contains 1 - 9 of each number occurring only once, each column contains 1-9, and each 3 by 3 sub-matrix should contain 1 - 9.

Solution:
A straight-forward solution will be check each row, and then each column, and each block, respectively. Use hash set to store the visited numbers. In this method, we need to scan the matrix three times. Here we show a neat program which requires scanning the matrix only once. 

Code (Java):
public class Solution {
    public boolean isValidSudoku(char[][] board) {
        if (board == null || board.length != 9 || board[0].length != 9) {
            return false;
        }
        
        boolean[][] rows = new boolean[9][9];
        boolean[][] cols = new boolean[9][9];
        boolean[][] blocks = new boolean[9][9];
        
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (board[i][j] == '.') {
                    continue;
                }
                
                int c = board[i][j] - '1';
                
                if (rows[i][c] == true || cols[j][c] == true || blocks[(i / 3) * 3 + j / 3][c] == true) {
                    return false;
                }
                
                rows[i][c] = true;
                cols[j][c] = true;
                blocks[(i / 3) * 3 + j / 3][c] = true;
            }
        }
        return true;
    }
}


Summary:
It is a relatively easy question, the solution above is very tricky. Try to fully understand what does the rows, cols, and blocks mean. 


Update on 9/29/15:
public class Solution {
    public boolean isValidSudoku(char[][] board) {
        boolean[][] rows = new boolean[9][9];
        boolean[][] cols = new boolean[9][9];
        boolean[][] grid = new boolean[9][9];
        
        
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (board[i][j] == '.') {
                    continue;
                }
                
                int num = board[i][j] - '1';
                int x = 3 * (i / 3) + num / 3;
                int y = 3 * (j / 3) + num % 3;
                if (rows[i][num] || cols[num][j] || grid[x][y]) {
                    return false;
                }
                
                rows[i][num] = true;
                cols[num][j] = true;
                grid[x][y] = true;
            }
        }
        
        return true;
    }
}

No comments:

Post a Comment