Problem

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

  1. Each row must contain the digits 1-9 without repetition.
  2. Each column must contain the digits 1-9 without repetition.
  3. Each of the nine 3 x 3 sub-boxes of the grid must contain the digits 1-9 without repetition.

Note:

  • A Sudoku board (partially filled) could be valid but is not necessarily solvable.
  • Only the filled cells need to be validated according to the mentioned rules.

The Sudoku board could be partially filled, where empty cells are filled with the character ‘.’.

Examples

Example 1:

Input: board = 
[ ["5","3",".",".","7",".",".",".","."]
,["6",".",".","1","9","5",".",".","."]
,[".","9","8",".",".",".",".","6","."]
,["8",".",".",".","6",".",".",".","3"]
,["4",".",".","8",".","3",".",".","1"]
,["7",".",".",".","2",".",".",".","6"]
,[".","6",".",".",".",".","2","8","."]
,[".",".",".","4","1","9",".",".","5"]
,[".",".",".",".","8",".",".","7","9"]]
Output: true

Method 1 - Using Boolean Array as Hashmap with 3 pass

This is a 3 pass solution, where we will first go through all columns are valid, then all rows and cubes or grids or blocks.

We will use boolean array to store the 9 values, as we can have 9 columns, rows or values in block. When we see value at specific column, we will set index in boolean array as true. If we see it again, we will return false.

Code

Java
public boolean isValidSudoku(char[][] board) {
	if (board == null || board.length != 9 || board[0].length != 9)
		return false;
	// check each column
	for (int i = 0; i<9; i++) {
		boolean[] m = new boolean[9];
		for (int j = 0; j<9; j++) {
			if (board[i][j] != '.') {
				if (m[(int)(board[i][j] - '1')]) {
					return false;
				}
				m[(int)(board[i][j] - '1')] = true;
			}
		}
	}

	//check each row
	for (int j = 0; j<9; j++) {
		boolean[] m = new boolean[9];
		for (int i = 0; i<9; i++) {
			if (board[i][j] != '.') {
				if (m[(int)(board[i][j] - '1')]) {
					return false;
				}
				m[(int)(board[i][j] - '1')] = true;
			}
		}
	}

	//check each 3*3 matrix
	for (int block = 0; block<9; block++) {
		boolean[] m = new boolean[9];
		for (int i = block / 3 * 3; i<block / 3 * 3 + 3; i++) {
			for (int j = block % 3 * 3; j<block % 3 * 3 + 3; j++) {
				if (board[i][j] != '.') {
					if (m[(int)(board[i][j] - '1')]) {
						return false;
					}
					m[(int)(board[i][j] - '1')] = true;
				}
			}
		}
	}

	return true;
}

Method 2 - Using the Hashset and String Instead

We can use string concatenation to create string like: 1 in row 0. Now, if we find again 1 in row 0, hashset add will return false, hence we find out if sudoku is valid or not.

We can create a key in Hashset based on the check we are performing. For eg.

  • Check number in row - '4' in row 7 
  • Check number in column - '4' in column 7
  • Check number in grid 9 (for row 7, column 7), can be '4' in grid 7/3-7/3

The add method of Set returns true if this set did not already contain the specified element (i.e., the current number in that row, column, or subgrid); if it’s false, this means we’ve encountered a duplicate number in the same row, column, or subgrid, and thus the Sudoku board is not valid. Therefore, the method will return false.

Code

Java
class Solution {

	public boolean isValidSudoku(char[][] board) {
		Set<String> seen = new HashSet<>();

		for (int i = 0; i < 9; ++i) {
			for (int j = 0; j < 9; ++j) {
				char number = board[i][j];

				if (number == '.') {
					continue;
				}

				if (!seen.add(number + " in row " + i) ||
					!seen.add(number + " in column " + j) ||
					!seen.add(number + " in block " + i / 3 + "-" + j / 3)) {
					return false;
				}
			}
		}

		return true;
	}
}

Method 3 - Using char set

This approach is similar to previous method.

For a block traversal, it goes the following way using / & %

  • 0,0, 0,1, 0,2; < — 3 Horizontal Steps followed by 1 Vertical step to next level.
  • 1,0, 1,1, 1,2; < — 3 Horizontal Steps followed by 1 Vertical step to next level.
  • 2,0, 2,1, 2,2; < — 3 Horizontal Steps.

And so on… But, the j iterates from 0 to 9.

But we need to stop after 3 horizontal steps, and go down 1 step vertical.

Use % for horizontal or column based traversal. Because % increments by 1 for each j : 0%3 = 0 , 1%3 = 1, 2%3 = 2, and resets back. So this covers horizontal traversal for each block by 3 steps.

Use / for vertical traversal. Because / increments by 1 after every 3 j: 0/3 = 0; 1/3 = 0; 2/3 =0; 3/3 = 1.

So far, for a given block, you can traverse the whole block using just j.

But because j is just 0 to 9, it will stay only first block. But to increment block, use i. To move horizontally to next block, use % again : colIndex = 3 * i%3 (Multiply by 3 so that the next block is after 3 columns. Ie 0,0 is start of first block, second block is 0,3 (not 0,1);

Similarly, to move to next block vertically, use / and multiply by 3 as explained above. Hope this helps.

Code

Java
class Solution {

	public boolean isValidSudoku(char[][] board) {
		for (int i = 0; i < 9; i++) {
			HashSet<Character> rows = new HashSet<Character>();
			HashSet<Character> columns = new HashSet<Character>();
			HashSet<Character> cube = new HashSet<Character>();

			for (int j = 0; j < 9; j++) {
				if (board[i][j] != '.' && !rows.add(board[i][j])) {
					return false;
				}

				if (board[j][i] != '.' && !columns.add(board[j][i])) {
					return false;
				}

				int rowIdx = 3 * (i / 3);
				int colIdx = 3 * (i % 3);

				if (board[rowIdx + j / 3][colIdx + j % 3] != '.' && !cube.add(board[rowIdx + j / 3][colIdx + j % 3])) {
					return false;
				}
			}
		}

		return true;
	}
}