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.

分析

对于小方块，大坐标（i,j）-> 小坐标（( i / 3, j / 3) 是块的坐标，定位到块）->大坐标（(row / 3) * 3在真正位置travel）

三个数组row[i][val] ，col[j][val] ，block[index][val] 。此处block的index = i / 3 * 3 + j / 3.

( i / 3, j / 3) 是块的坐标，i / 3 * 3 + j / 3直接定位到第几块，相当是 i*row+j(island里定位常用）

2种块坐标表达法

int row = i - i%3, column = j - j%3;
 if(board[row+x][column+y] == val) return false;
 
 int blkrow = (row / 3) * 3, blkcol = (col / 3) * 3; 
 board[blkrow + i / 3][blkcol + i % 3] == num

val就是数字1-9，类似dp里背包用val做Index

class Solution {
    public boolean isValidSudoku(char[][] board) {
        if(board == null || board.length == 0 || board[0] == null || board[0].length == 0)
            return false;
        int n = board.length;
        int m = board[0].length;

        int[][] row = new int[n][m];
        int[][]col = new int[n][m];
        int[][] block= new int[n][m];
        for(int i = 0; i < n; i ++){
            for(int j = 0; j < m; j ++){
                if(board[i][j] != '.'){
                    int val = board[i][j] - '0' - 1;
                    int index = i / 3 * 3 + j / 3;
                    if(row[i][val] > 0 || col[j][val] > 0 || block[index][val] > 0){
                        return false;
                    }else{
                        row[i][val] = col[j][val] = block[index][val] = 1;
                    }
                }
            }
        }
        return true;
    }
}

用bit做,因为每次loop，row的值都知道了，所以每次loop，row都重设为0，但是col和block的值需要完全loop完整个board才知道，所以用数组存下了col和block所有的值，这里总共81个值。所以数组9

    public boolean isValidSudoku(char[][] board) {
        if(board == null || board.length == 0 || board[0] == null || board[0].length == 0)
            return false;
        int n = board.length;
        int m = board[0].length;
        int row = 0;
        int[] cols = new int[n];
        int[] blocks = new int[n];
        for(int i = 0; i < n; i ++){
            row = 0;//每次loop都能得到row所需所有值，所以每次row都不断更新为0，然后col和block不行，所以需要用数组记录所有值、总共81个值。
            for(int j = 0; j < m; j ++){
                if(board[i][j] != '.'){
                    int cur = board[i][j] - '0';
                int bit = 1 << cur;
                if((row & bit) != 0 || (cols[j] & bit) != 0 || (blocks[(i / 3) * 3 + j / 3] & bit) != 0){
                    return false;
                }
                row |= bit;
                cols[j] |= bit;
                blocks[(i / 3) * 3 + j / 3] |= bit;
                }

            }
        }
        return true;
    }

python, 注意是cols[j] 不是cols[i]

class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        N=9
        cols = [0]*9
        blocks = [0]*9
        for i in range(N):
            row = 0
            for j in range(N):
                col = cols[j]
                block = blocks[i//3 * 3 + j//3]
                if board[i][j] != '.':
                    bit = 1 << int(board[i][j])
                    if row&bit or col&bit or block&bit:
                        return False
                    row|=bit
                    cols[j]|=bit
                    blocks[i//3 * 3 + j//3]|=bit
        return True