Start learning free

LESSON 318 OF 569 · HASH TABLE

Valid Sudoku in Java: One Pass with HashSets per Row, Column, Box

Practice O(81) Read the full explanation

A Sudoku board is a 9 x 9 grid of cells. Each cell holds a digit from '1' to '9', or '.' while it is empty. Rows 0-2, 3-5 and 6-8 and columns 0-2, 3-5 and 6-8 split the board into nine 3 x 3 boxes.

Given a partly filled board, return true if it is valid so far, and false otherwise. The board is valid when no digit appears twice:

  1. in the same row,
  2. in the same column,
  3. in the same 3 x 3 box.

Only the filled cells are checked; empty cells don't count. A valid board doesn't have to be solvable: you check the digits already on it, you don't solve the puzzle.

Rows are numbered from 0 at the top and columns from 0 at the left. In the examples, each line is one row of the board.

 

Example 1:



Input: board =
53..7....
6..195...
.98....6.
8...6...3
4..8.3..1
7...2...6
.6....28.
...419..5
....8..79
Output: true
Explanation: No row, column or box holds the same digit twice.

Example 2:

Input: board =
83..7....
6..195...
.98....6.
8...6...3
4..8.3..1
7...2...6
.6....28.
...419..5
....8..79
Output: false
Explanation: The board of Example 1 with an 8 instead of the 5 in the top left corner.
Column 0 now holds two 8s, in rows 0 and 3, and so does the top left box, in rows 0 and 2.

Example 3:

Input: board =
12345678.
.........
.........
.........
........9
.........
.........
.........
.........
Output: true
Explanation: No digit repeats, so the board is valid, although it has no solution:
the last cell of row 0 can only be a 9, and column 8 already has a 9 in row 4.

 

Constraints:

  • The board has 9 rows, and each row has 9 cells.
  • Each cell holds a digit from '1' to '9' or '.'.

Note:

Your algorithm should look at each cell once and check it in constant time: O(81) time and O(81) extra space for the 81 cells. Scanning the row, the column and the box of every cell again would also work on a board this small, but it looks at each cell many times.

STEP 1 OF 14
    Ctrl + Enter to check

    JAVA · HASH TABLE

    Valid Sudoku in Java, explained

    Problem overview

    The method isValidSudoku receives a 9 x 9 char[][] board. Each cell holds a digit from '1' to '9', or '.' when it is empty. The method returns true when no digit appears twice in the same row, the same column or the same 3 x 3 box, and false otherwise. Only filled cells count, and the board does not have to be solvable: you check the digits already on it, you don't solve the puzzle.

    The statement's first board is valid, and the method returns true. Replace its top-left 5 with an 8 and column 0 holds two 8s (rows 0 and 3), as does the top-left box (rows 0 and 2), so the method returns false. A third board has the digits 1 to 8 in row 0 and a 9 at row 4, column 8. It has no solution, because the last cell of row 0 could only be a 9 and column 8 already has one, but no digit repeats, so the method returns true.

    Approach: remember what each row, column and box has seen

    You could scan the row, the column and the box of every cell again and again. On a 9 x 9 board that is fast enough, but it looks at each cell many times. A better idea is to visit each cell once and keep a set of the digits seen so far in every row, every column and every box. A cell is a problem when its digit is already in one of its three sets.

    That is 27 sets: 9 for rows, 9 for columns, 9 for boxes. Every cell belongs to exactly one row, one column and one box. Since the board has a fixed size of 81 cells, the work is constant, and the lesson's notes call it O(81) time and space.

    Numbering the boxes

    Rows and columns number themselves: use r and c. For boxes you need a formula. The box's row is r / 3 and its column is c / 3. Number the boxes left to right, then top to bottom, and the number is (r / 3) * 3 + c / 3. Integer division drops the remainder: 7 / 3 is 2 in Java, while 7 / 3.0 is 2.3333333333333335. These cells show the formula:

    cell (0, 0) -> box 0
cell (0, 8) -> box 2
cell (4, 7) -> box 5
cell (4, 4) -> box 4
cell (8, 8) -> box 8
cell (2, 3) -> box 1

    Step by step

    1. Create the row sets. rows is a List<Set<Character>> built as a new ArrayList. rows.get(r) will hold the digits seen so far in row r. A set of char values needs the wrapper type Character, because generics can't take primitives.
    2. Create cols and boxes the same way.
    3. Fill the three lists with a loop of nine turns. They start empty, and get(r) on an empty list would throw.
    4. Add a new HashSet to rows inside that loop. The diamond new HashSet<>() takes its element type from the list it goes into.
    5. Add one to cols and one to boxes too. Each row, column and box needs a set of its own.
    6. Loop over the rows with r from 0 to 8.
    7. Loop over the columns of row r with c from 0 to 8.
    8. Store the cell board[r][c] in a char named digit.
    9. Skip empty cells. If digit is '.', continue to the next column. Empty cells never break the rules.
    10. Compute the box number into an int box with the formula above.
    11. Check for a repeat. If any of the three sets already contains digit, return false. Each set holds the digits of the cells visited before this one in that row, column or box, so finding the digit there means it appears twice.
    12. Record the digit in the row's set.
    13. Record it in the column's and the box's sets too.
    14. Return true after both loops. Every filled cell was checked against the ones before it, and nothing repeated.

    The solution in Java

    class Solution {
    public boolean isValidSudoku(char[][] board) {
        List<Set<Character>> rows = new ArrayList<>();
        List<Set<Character>> cols = new ArrayList<>();
        List<Set<Character>> boxes = new ArrayList<>();
        for (int i = 0; i < 9; i++) {
            rows.add(new HashSet<>());
            cols.add(new HashSet<>());
            boxes.add(new HashSet<>());
        }
        for (int r = 0; r < 9; r++) {
            for (int c = 0; c < 9; c++) {
                char digit = board[r][c];
                if (digit == '.') continue;
                int box = (r / 3) * 3 + c / 3;
                if (rows.get(r).contains(digit) || cols.get(c).contains(digit) || boxes.get(box).contains(digit)) {
                    return false;
                }
                rows.get(r).add(digit);
                cols.get(c).add(digit);
                boxes.get(box).add(digit);
            }
        }
        return true;
    }
}

    Java details worth knowing:

    • Boxing of char. Calling contains(digit) on a Set<Character> boxes the char into a Character. The type matters: after set.add('5'), set.contains('5') is true, but set.contains((int) '5') and set.contains(5) are both false, because an Integer is never equal to a Character.
    • Digits are characters, not numbers. '5' is the character with code 53. The solution never does arithmetic on digits, only compares them, so it doesn't need to convert them.
    • Short-circuit ||. The three contains checks stop at the first true.
    • Single-statement continue. if (digit == '.') continue; skips the rest of that column's turn, and the loop moves on to the next c.

    Complexity

    Time: O(81), that is, constant. The board always has 81 cells, each visited once, and each visit does a few set lookups and insertions, which take constant time on average. For a board of n x n cells it would be O(n²).

    Space: O(81). The 27 sets together hold at most one entry per filled cell in each of its three sets, so at most 243 entries.

    Edge cases and common mistakes

    • Checking only rows and columns. The box rule is easy to forget. A 5 at row 0, column 0 and another at row 1, column 1 share no row and no column, yet the board is invalid: the method returns false for it.
    • The same digit in unrelated cells. A 5 at (0, 0) and a 5 at (4, 4) share no row, column or box, so the method returns true.
    • A wrong box formula. r / 3 + c / 3 gives the same number, 1, to cell (0, 3) and cell (3, 0), which lie in different boxes. Multiplying the box row by 3 gives them 1 and 3.
    • An empty board. It is valid. Treating '.' as a digit would make the second dot of every row look like a repeat.
    • Unsolvable but valid. Looking for a contradiction beyond repeats, such as a cell with no possible digit, is not what is asked.
    • Sets that are shared. Adding the same HashSet object to the list nine times would make all rows share one set. Create a new set for each row, column and box.

    Testing

    • The statement's first board gives true.
    • The same board with an 8 in the top-left corner gives false.
    • Row 0 equal to 12345678. and a single 9 at row 4, column 8, with every other cell empty, gives true.
    • A board with only a 5 at (0, 0) and a 5 at (0, 8) gives false: same row.
    • A board with only a 5 at (0, 0) and a 5 at (8, 0) gives false: same column.
    • A board with only a 5 at (0, 0) and a 5 at (1, 1) gives false: same box.
    • An entirely empty board gives true.
    Keep going with Java500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free