Valid Sudoku

LeetCode Q 36 - Valid Sudoku

Determine if a 9x9 Sudoku board is valid. Only the filled cells need to be validated according to the following rules:

• Each of the digits 1-9 must occur exactly once in each row.
• Each of the digits 1-9 must occur exactly once in each column.
• Each of the the digits 1-9 must occur exactly once in each of the 9 3x3 sub-boxes of the grid.
  Empty cells are indicated by the character ‘.’.

Solution

Method 1: HashTable

Use a HashSet to check if we have seen the char before.

Code:

public boolean isValidSudoku(char[][] board) {
	Set<Integer>[] rows = new HashSet[9];
	Set<Integer>[] cols = new HashSet[9];
	Set<Integer>[] boxes = new HashSet[9];

	for (int i = 0; i < 9; i++) {
		for (int j = 0; j < 9; j++) {
			if (board[i][j] != '.') {
				int num = board[i][j] - '0';
				if (rows[i] == null) rows[i] = new HashSet<>();
				if (!rows[i].add(num)) return false; 
				if (cols[i] == null) cols[i] = new HashSet<>();
				if (!cols[i].add(num)) return false;
				int index = (i / 3) * 3 + j / 3;
				if (boxes[i] == null) boxes[i] = new HashSet<>();
				if (!boxes[i].add(num)) return false;  
			}
		}
	}

	return true;
}

Method 2: HashTable + String

Collect the set of things we see, encoded as strings. For example:

• ‘4’ in row 7 is encoded as “(4)7”.
• ‘4’ in column 7 is encoded as “7(4)”.
• ‘4’ in the top-right block is encoded as “0(4)2”.
  Scream false if we ever fail to add something because it was already added (i.e., seen before).

Code:

public boolean isValidSudoku(char[][] board) {
	Set<String> seen = new HashSet<>();
	for (int i = 0; i < 9; i++) {
		for (int j = 0; j < 9; j++) {
			if (board[i][j] != '.') {
				String b = "(" + board[i][j] + ")";
				if (!seen.add(b + i) || !seen.add(j + b) || !seen.add(i/3 + b + j/3))
					return false;
			}
		}
	}
    return true;
}