36. Valid Sudoku.md

36. 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

tag:

Solution

本题的关键是i,j 到 小棋盘索引的转换

整个棋盘可以分为9个小棋盘，每个为3*3, 左上角索引为
00 03 06
30 33 36
60 63 66
i的变化范围为0-9， 故棋盘左上角可用3*(i/3)， 3*（i%3)表示

对于每个小棋盘内部，如果减去其左上角索引，则
00 01 02
10 11 12
20 21 22
此时，j从0-9， 行和列可用 j/3, j%3


故

boxi = 3*(i/3)+j/3, boxj = 3*(i%3)+(j%3)

java

    public boolean isValidSudoku(char[][] board) {
        Set<Character> row = new HashSet<Character>(), col = new HashSet<Character>(), box = new HashSet<Character>();
        for(int i=0; i<9; i++) {
            row.clear();col.clear();box.clear();
            for(int j=0; j<9; j++) {
                if(board[i][j]!='.' && !row.add(board[i][j])) return false;
                if(board[j][i]!='.' && !col.add(board[j][i])) return false;
                if(board[3*(i/3)+j/3][3*(i%3)+j%3]!='.' && !box.add(board[3*(i/3)+j/3][3*(i%3)+j%3])) return false;
            }
        }
        return true;
    }

go

func isValidSodoku(board [][]byte) bool {
	for i := 0; i < 9; i++ {
		row, col, box := make(map[byte]bool), make(map[byte]bool), make(map[byte]bool)

		for j := 0; j < 9; j++ {
			if board[i][j] != '.' {
				if row[board[i][j]] == true {
					return false
				} else {
					row[board[i][j]] = true
				}
			}

			if board[j][i] != '.' {
				if col[board[i][j]] == true {
					return false
				} else {
					col[board[i][j]] = true
				}
			}

			boxi, boxj := 3*(i/3)+j/3, 3*(i%3)+(j%3)
			if board[boxi][boxj] != '.' {
				if box[board[boxi][boxj]] == true {
					return false
				} else {
					box[board[boxi][boxj]] = true
				}
			}
		}
	}
	return true
}