Valid Sudoku problem in Java
The Valid Sudoku problem is a classic programming challenge that involves determining whether a given 9x9 Sudoku board is valid according to the rules of the game. A Sudoku puzzle is a number-placement puzzle where the objective is to fill a 9x9 grid with digits from 1 to 9, ensuring that each column, each row, and each of the nine 3x3 sub-grids (also known as blocks) contain all of the digits from 1 to 9 without repetition.
The rules of a valid Sudoku solution are as follows
- Each row must contain all the digits from 1 to 9 without repetition.
- Each column must contain all the digits from 1 to 9 without repetition.
- Each of the nine 3x3 sub-grids must contain all the digits from 1 to 9 without repetition.
Example 1:
Input
Output
Valid Sudoku
Explanation
Since there are no repeated elements in same row or column it is a valid sudoku
Example 2:
Input
Output
Invalid Sudoku
Explanation
The sudoku is not valid because of the repeated elements in same row and column
Approach 1: Brute Force
The Brute Force approach to solving the Valid Sudoku problem involves exhaustively checking each row, each column, and each 3x3 sub-grid to ensure that there are no repeated digits and that all digits from 1 to 9 are present. It's a straightforward method that directly follows the rules of Sudoku and iterates through the entire board to verify its validity.
Algorithm
Step 1: Iterate through each row of the Sudoku board. Use a helper function (isValid) to check if the row is valid (no repeated digits and all digits from 1 to 9 are present).
Step 2: Iterate through each column of the Sudoku board. Create temporary arrays for each column and use the same helper function (isValid) to check if the column is valid.
Step 3: Check Sub-Grids: Iterate through each 3x3 sub-grid of the Sudoku board. Create temporary arrays for each sub-grid and use the helper function (isValid) to check if the sub-grid is valid.
Step 4: The isValid function takes an array of characters representing a row, column, or sub-grid. Uses a boolean array (used) of size 9 to track the presence of digits.
Step 5: Iterates through the array, checking for repeated digits and ensuring that all digits from 1 to 9 are present.
Step 6: If the character is '0' return false. If all rows, columns, and sub-grids pass the validity checks, return true (indicating a valid Sudoku board); otherwise, return false.
Filename: ValidSudoku.java
public class ValidSudoku {
public static boolean isValidSudoku(char[][] board) {
// Check rows
for (int i = 0; i < 9; i++) {
if (!isValid(board[i])) {
return false;
}
}
// Check columns
for (int j = 0; j < 9; j++) {
char[] column = new char[9];
for (int i = 0; i < 9; i++) {
column[i] = board[i][j];
}
if (!isValid(column)) {
return false;
}
}
// Check sub-grids
for (int blockRow = 0; blockRow < 3; blockRow++) {
for (int blockCol = 0; blockCol < 3; blockCol++) {
char[] block = new char[9];
int index = 0;
for (int i = blockRow * 3; i < blockRow * 3 + 3; i++) {
for (int j = blockCol * 3; j < blockCol * 3 + 3; j++) {
block[index++] = board[i][j];
}
}
if (!isValid(block)) {
return false;
}
}
}
return true;
}
private static boolean isValid(char[] chars) {
boolean[] used = new boolean[9];
for (char c : chars) {
if (c == '0' || c == '.') { // Modified condition
return false;
}
int digit = c - '1';
if (used[digit]) {
return false;
}
used[digit] = true;
}
return true;
}
public static void main(String[] args) {
char[][] sudokuBoard = {
{'5', '3', '4', '6', '7', '8', '9', '1', '2'},
{'6', '7', '2', '1', '9', '5', '3', '4', '8'},
{'1', '9', '8', '3', '4', '2', '5', '6', '7'},
{'8', '5', '9', '7', '6', '1', '4', '2', '3'},
{'4', '2', '6', '8', '5', '3', '7', '9', '1'},
{'7', '1', '3', '9', '2', '4', '8', '5', '6'},
{'9', '6', '1', '5', '3', '7', '2', '8', '4'},
{'2', '8', '7', '4', '1', '9', '6', '3', '5'},
{'3', '4', '5', '2', '8', '6', '1', '7', '9'}
};
System.out.println("Is valid Sudoku? " + isValidSudoku(sudokuBoard));
}
}
Output:
Is valid Sudoku? true
Time Complexity
The time complexity of the Brute Force approach for checking the validity of a Sudoku board is O(1), or constant time. This is because the size of a standard Sudoku board is fixed at 9x9, and the nested loops iterate over a constant number of cells and sub-grids (81 cells in total). Regardless of the size of the input, the number of iterations remains constant.
Space Complexity
The space complexity of the Brute Force approach is also O(1), or constant space. The additional space used is minimal and independent of the input size. The boolean array used in the isValid helper function has a constant size of 9, representing the digits from 1 to 9. The other variables and arrays used in the algorithm also have constant size.
Approach 2: Using HashSet
The HashSet approach to solving the Valid Sudoku problem involves using sets to efficiently check for the presence of digits in each row, column, and 3x3 sub-grid of the Sudoku board. In this approach we leverage the HashSet data structure to store unique digits, ensuring that there are no repeated digits in each row, column, and sub-grid.
Algorithm
Step 1: Iterate through each row of the Sudoku board. Call the isValid function to check the validity of each row. If any row is not valid, return false.
Step 2: Iterate through each column of the Sudoku board. Call the isValid function to check the validity of each column. If any column is not valid, return false.
Step 3: Iterate through each 3x3 sub-grid of the Sudoku board. Call the isValid function to check the validity of each sub-grid. If any sub-grid is not valid, return false. If all rows, columns, and sub-grids pass the validity checks, return true (indicating a valid Sudoku board).
Step 4: isValid Function: Takes a character array (chars) representing a row, column, or sub-grid. Uses a HashSet (set) to keep track of unique digits.
Step 5: Iterates through each character in the array: If the character is '0' or if the character is not '.', and adding it to the HashSet fails (it's already present), return false (indicating a duplicate digit). If the iteration completes without finding any duplicates, return true.
Step 6: getColumn Function: Takes the Sudoku board and a column index. Creates a character array (column) representing the specified column and return the column array.
Step 7: getSubgrid Function: Takes the Sudoku board and 3x3 sub-grid indices (blockRow and blockCol). Creates a character array (subgrid) representing the specified sub-grid and return the sub-grid array.
Step 8: In the main function, the example creates a sample Sudoku board. Calls isValidSudoku with the board and prints whether it's a valid Sudoku.
Filename: ValidSudokuHashSet.java
import java.util.HashSet;
import java.util.Set;
public class ValidSudokuHashSet {
public static boolean isValidSudoku(char[][] board) {
// Check rows
for (int i = 0; i < 9; i++) {
if (!isValid(board[i])) {
return false;
}
}
// Check columns
for (int j = 0; j < 9; j++) {
if (!isValid(getColumn(board, j))) {
return false;
}
}
// Check sub-grids
for (int blockRow = 0; blockRow < 3; blockRow++) {
for (int blockCol = 0; blockCol < 3; blockCol++) {
if (!isValid(getSubgrid(board, blockRow, blockCol))) {
return false;
}
}
}
return true;
}
private static boolean isValid(char[] chars) {
Set<Character> set = new HashSet<>();
for (char c : chars) {
if (c == '0' || c == '.') { // Modified condition
return false;
}
if (!set.add(c)) {
return false; // Duplicate digit found
}
}
return true;
}
private static char[] getColumn(char[][] board, int col) {
char[] column = new char[9];
for (int i = 0; i < 9; i++) {
column[i] = board[i][col];
}
return column;
}
private static char[] getSubgrid(char[][] board, int blockRow, int blockCol) {
char[] subgrid = new char[9];
int index = 0;
for (int i = blockRow * 3; i < blockRow * 3 + 3; i++) {
for (int j = blockCol * 3; j < blockCol * 3 + 3; j++) {
subgrid[index++] = board[i][j];
}
}
return subgrid;
}
public static void main(String[] args) {
char[][] sudokuBoard = {
{'5', '3', '4', '6', '7', '8', '9', '1', '2'},
{'6', '7', '2', '1', '9', '5', '3', '4', '8'},
{'1', '9', '8', '3', '4', '2', '5', '6', '7'},
{'8', '5', '9', '7', '6', '1', '4', '2', '3'},
{'4', '2', '6', '8', '5', '3', '7', '9', '1'},
{'7', '1', '3', '9', '2', '4', '8', '5', '6'},
{'9', '6', '1', '5', '3', '7', '2', '8', '4'},
{'2', '8', '7', '4', '1', '9', '6', '3', '5'},
{'3', '4', '5', '2', '8', '6', '1', '7', '9'}
};
System.out.println("Is valid Sudoku? " + isValidSudoku(sudokuBoard));
}
}
Output:
Is valid Sudoku? true
Time Complexity
The time complexity of the algorithm is constant which is O(1). Regardless of the size of the input Sudoku board, the number of operations is fixed and does not depend on the input size. The nested loops and HashSet operations are proportional to the constant size of a standard 9x9 Sudoku board.
Space Complexity
The space complexity is constant as well which is O(1). The additional space used by the algorithm is independent of the input size. HashSet instances are created for each row, column, and sub-grid, but the maximum number of elements in these sets is constant (9). The size of the Sudoku board does not affect the space complexity.
Approach 3: Using a HashMap
The approach using a HashMap involves iterating over each row, column, and sub-grid of the Sudoku board and using a HashMap to keep track of the occurrences of digits. By efficiently storing and updating the count of digits encountered, we can quickly determine if the board violates any Sudoku rules.
Algorithm
Step 1: isValidSudoku method takes a 9x9 Sudoku board represented as a 2D array of characters as input and returns true if the board is valid and false otherwise.
Step 2: It iterates over each row, column, and sub-grid of the Sudoku board and checks their validity using the isValid method.
Step 3: isValid method takes an array of characters representing a row, column, or sub-grid as input and checks its validity. It uses a HashMap to keep track of the occurrences of digits encountered.
Step 4: For each character in the array: If the character is '0' or if it is not a '.', and it already exists in the HashMap, it returns false, indicating an invalid board. Otherwise, it updates the count of the character in the HashMap. If no violations are found, it returns true, indicating a valid row, column, or sub-grid.
Step 5: getColumn method takes the Sudoku board and a column index as input and returns the characters of that column in an array.
Step 6: getSubgrid method takes the Sudoku board and the indices of the block row and block column of the sub-grid as input and returns the characters of that sub-grid in an array.
Step 7: The main method initializes a 9x9 Sudoku board with predefined values. It calls the isValidSudoku method with the Sudoku board as an argument and prints whether the Sudoku board is valid or not.
Filename: ValidSudokuBT.java
import java.util.HashMap;
public class ValidSudoku {
public static boolean isValidSudoku(char[][] board) {
for (int i = 0; i < 9; i++) {
if (!isValid(board[i])) {
return false;
}
}
for (int j = 0; j < 9; j++) {
if (!isValid(getColumn(board, j))) {
return false;
}
}
for (int blockRow = 0; blockRow < 3; blockRow++) {
for (int blockCol = 0; blockCol < 3; blockCol++) {
if (!isValid(getSubgrid(board, blockRow, blockCol))) {
return false;
}
}
}
return true;
}
private static boolean isValid(char[] chars) {
HashMap<Character, Integer> map = new HashMap<>();
for (char c : chars) {
if (c == '0' || (c != '.' && map.containsKey(c))) {
return false;
}
map.put(c, 1);
}
return true;
}
private static char[] getColumn(char[][] board, int col) {
char[] column = new char[9];
for (int i = 0; i < 9; i++) {
column[i] = board[i][col];
}
return column;
}
private static char[] getSubgrid(char[][] board, int blockRow, int blockCol) {
char[] subgrid = new char[9];
int index = 0;
for (int i = blockRow * 3; i < blockRow * 3 + 3; i++) {
for (int j = blockCol * 3; j < blockCol * 3 + 3; j++) {
subgrid[index++] = board[i][j];
}
}
return subgrid;
}
public static void main(String[] args) {
char[][] sudokuBoard = {
{'5', '3', '4', '6', '7', '8', '9', '1', '2'},
{'6', '7', '2', '1', '9', '5', '3', '4', '8'},
{'1', '9', '8', '3', '4', '2', '5', '6', '7'},
{'8', '5', '9', '7', '6', '1', '4', '2', '3'},
{'4', '2', '6', '8', '5', '3', '7', '9', '1'},
{'7', '1', '3', '9', '2', '4', '8', '5', '6'},
{'9', '6', '1', '5', '3', '7', '2', '8', '4'},
{'2', '8', '7', '4', '1', '9', '6', '3', '5'},
{'3', '4', '5', '2', '8', '6', '1', '7', '9'}
};
System.out.println("Is valid Sudoku? " + isValidSudoku(sudokuBoard));
}
}
Output:
Is valid Sudoku? true
Time Complexity
The time complexity of the provided algorithm is O(1) because it iterates over a fixed-size Sudoku board of 9x9 cells. In each iteration, it performs constant-time operations to check the validity of rows, columns, and sub-grids.
Space Complexity
The space complexity is also O(1) because the algorithm uses a fixed amount of additional space regardless of the input size. It utilizes a HashMap to store the occurrences of digits, but the size of the HashMap is bounded by the number of unique digits (0 to 9), which is a constant.