Leetcode: Check whether partially filled sudoku is valid.



https://leetcode.com/problems/valid-sudoku

A sudoku is valid when:

Sudoku

  • Each row must have the numbers 1-9 occuring just once.
  • Each column must have the numbers 1-9 occuring just once.
  • And the numbers 1-9 must occur just once in each of the 9 sub-boxes of the grid.
public class ValidSudoku {

	public static void main(String args[]) {
		
		char b [][] = new char[][]{
			"......5..".toCharArray(),
			 ".........".toCharArray(),
			 ".........".toCharArray(),
			 "93..2.4..".toCharArray(),
			 "..7...3..".toCharArray(),
			 ".........".toCharArray(),
			 "...34....".toCharArray(),
			 ".....3...".toCharArray(),
			 ".....52..".toCharArray()};
			System.out.println(new ValidSudoku().isValidSudoku(b));
	}

	public boolean isValidSudoku(char[][] board) {
		if (board.length == 0 || board[0].length == 0)
			return false;
		// check row
		Set duplicates = new HashSet<>();
		for (int i = 0; i < board.length; i++) {
			duplicates = new HashSet<>();
			for (int j = 0; j < board[0].length; j++) {
				if (board[i][j] == '.')
					continue;
				if (duplicates.contains(board[i][j]))
					return false;
				duplicates.add(board[i][j]);
			}
		}

		// check colm
		for (int i = 0; i < board.length; i++) {
			duplicates = new HashSet<>();
			for (int j = 0; j < board.length; j++) {
				if (board[j][i] == '.')
					continue;
				if (duplicates.contains(board[j][i]))
					return false;
				duplicates.add(board[j][i]);
			}
		}

		for (int i = 0; i <= board.length - 3; i = i + 3) {
			for (int j = 0; j <= board[0].length - 3; j = j + 3) {
				if (!check(i, i + 3, j, j + 3, board)) {
					return false;
				}
			}
		}
		return true;
	}

	private boolean check(int i, int i1, int j, int j1, char[][] board) {
		Set duplicates = new HashSet<>();
		for (int r = i; r < i1; r++) {
			for (int c = j; c < j1; c++) {
				if (board[r][c] == '.')
					continue;
				if(duplicates.contains(board[r][c])) {
					return false;
				}
				duplicates.add(board[r][c]);
			}
		}
		return true;
	}
}

Subscribe to get latest updates.

© 2016 Java Questions | Sitemap