389. 判断数独是否合法

题目

请判定一个数独是否有效。

该数独可能只填充了部分数字,其中缺少的数字用 . 表示。

http://www.lintcode.com/zh-cn/problem/valid-sudoku/

分析

判断数独填充是否有效,主要看3方面:

  1. 每一行内,填充的数字不重复
  2. 每一列中,填充的数字不重复
  3. 每一个小的九宫格中,填充的数字不重复

暴力枚举即可,逐个考察九宫格中的每一个元素,如果该元素为'.',则合法,继续下一个。
如果格子里是数字,就要进行三方面的判断,分别用三个独立的函数判断即可。

代码


public class Solution {
    
    boolean isValidRow(char[][] board, int row, int col) {
        for(int i=0; i < board[row].length; i++) {
            if (i == col || board[row][i] == '.') {
                continue;
            }
            if ( board[row][i] == board[row][col] )
                return false;
        }
        return true;
    }
    
    boolean isValidCol(char[][] board, int row, int col) {
        for(int i=0; i < board.length; i++) {
            if (i == row || board[i][col] == '.') {
                continue;
            }
            if ( board[i][col] == board[row][col] )
                return false;
        }
        return true;
    }
    
    boolean isValidSquare(char[][] board, int row, int col) {
        int srow = row / 3;
        int scol = col / 3;
        
        for(int i = 0; i < 3; i++) {
            for(int j = 0; j < 3; j++) {
                int r = srow * 3 + i;
                int c = scol * 3 + j;
                if( board[r][c] == '.' || (row == r && col == c) ) {
                    continue;
                }
                if (board[r][c] == board[row][col]) return false;
            }
        }
        return true;
    }
    
    boolean isValidCharacter(char[][] board, int row, int col) {
        if (board[row][col] == '.') return true;
        return isValidRow(board, row, col) 
                && isValidCol(board, row, col)
                && isValidSquare(board, row, col);
    }
    /**
     * @param board: the board
     * @return: whether the Sudoku is valid
     */
    public boolean isValidSudoku(char[][] board) {
        // write your code here
        for(int row=0; row < board.length; row++){
            for(int col=0; col < board[row].length; col++) {
                if(isValidCharacter(board, row, col)) {
                    continue;
                }else{
                    return false;
                }
            }
        }
        return true;
    }
}
Show Comments

Get the latest posts delivered right to your inbox.