Valid Sudoku

Java solution using HashMap

Photo by Richard Bell on Unsplash

The problem is taken from the leetcode Hash Table chapter. Here is the link to the problem.

A complete solution is presented at the end.

Problem statement

Check if a 9 x 9 partially filled Sudoku board is valid (not necessarily solvable).

1. The numbers 1 through 9 must appear once in each row.
2. The numbers 1 through 9 must appear once in each column.
3. The numbers 1 through 9 must appear once in a 3 x 3 sub-grid.

Figure 1 can be solved since it satisfies all three constraints, while figure 2 does not meet the third constraint.

Solution

This problem could be solved in many different ways, here we will try to solve it using Hashmap.

First, we will see what input looks like. “.” represents the empty cell.

char[][] board ={{'8','6','.','.','.','4','.','.','9'}
,{'.','9','.','6','.','7','5','.','.'}
,{'.','.','3','.','.','.','.','.','.'}
,{'.','2','8','.','7','.','.','5','.'}
,{'.','.','.','.','5','.','.','.','.'}
,{'.','5','.','.','2','.','6','4','.'}
,{'.','.','.','.','.','.','3','.','.'}
,{'.','.','6','8','.','9','.','2','.'}
,{'4','.','.','7','.','.','.','9','6'}};

1. Our KEY in the HashMap is the String that tells a Row or Column or 3 X 3 Grid and VALUE is the list of Numbers in a Row or Column or 3 X 3 Grid.

Map<String, List<Character>> map = new HashMap<>();

To illustrate, our HashMap for the above input looks like below. Total 27 keys( 9 Rows+9 Columns+9 sub-grids), each Row contains a List of maximum length 9.

HashMap <Key,Value>

The list of Numbers in each value must be unique to say the given Sudoku is valid.

2. Now, let's read the input.

Loop through the input. we need two FOR loops since the input is a Matrix.

// Return True if Valid, else, False
public boolean isValidSudoku(char[][] board) {
    char val;
    for (int row = 0; row < board.length; row++) {
        for (int col = 0; col < board.length; col++) {
            val = board[row][col];
        }
    }
    return true;
}

3. Create Row and Column key

Creating Rows and columns Keys is straightforward. We just need to append the row number to “R” and the column number to “C”

public boolean isValidSudoku(char[][] board) {
    String key_R, key_C;
    char val;
    for (int row = 0; row < board.length; row++) {
        for (int col = 0; col < board.length; col++) {
            val = board[row][col];
            key_R = "R" + row; //Row Key
            key_C = "C" + col; //Column Key
        }
    }
    return true;
}

4. Create a 3 X 3 grid Key

Sub-Grid Keys are represented by B1..B9

//Input position of the Sudoku we are scanning i.e(row,col)
private String getSubGridKey(int row, int col) {
    int key = (col / 3);
    if (row / 3 >= 2) {
        key = key + 6;
    } else if (row / 3 >= 1) {
        key = key + 3;
    }
    return "B" + key;
}
public boolean isValidSudoku(char[][] board) {
    String key_R, key_C, key_B;
    char val;
    for (int row = 0; row < board.length; row++) {
        for (int col = 0; col < board.length; col++) {
            val = board[row][col];
            key_R = "R" + row; //Row Key
            key_C = "C" + col; //Column Key
            key_B = getSubGridKey(row, col); //3X3 subGrid Key
        }
    }
    return true;
}

5. Insert the Key Value Pair to HashMap

Another important method is to insert the above-generated Keys and respective Values into the HashMap.

List<Character> list = new ArrayList<>();
Map<String, List<Character>> map = new HashMap<>();
// Insert Key Value to Map.
// Return False if list contains duplicate values.
private boolean insertToMap(String key, char val) {
    list = new ArrayList<>();
    if (map.containsKey(key)) {
        list = map.get(key);
        if (list.contains(val)) {
            return false;
        }
    }
    list.add(val);
    map.put(key, list);
    return true;
}

Call the insertToMap from the code isValidSudoku.

public boolean isValidSudoku(char[][] board) {
    String key;
    char val;
    for (int row = 0; row < board.length; row++) {
        for (int col = 0; col < board.length; col++) {
            val = board[row][col];
            if (val != '.') {
                key = "r" + row;
                if (!insertToMap(key, val)) {
                    return false;
                }
                key = "c" + col;
                if (!insertToMap(key, val)) {
                    return false;
                }
                key = getSubGridKey(row, col);
                if (!insertToMap(key, val)) {
                    return false;
                }
            }
        }
    }
    return true;
}

Final Code