Have you ever tried solving a Sudoku puzzle? It's like putting together a puzzle where every piece has its special place. Imagine you’re playing a game where you need to make sure everything fits perfectly. But what if you need to check if the puzzle is already put together correctly? That’s what we’re going to explore today!

Just like how you might double-check your homework to see if everything is correct, checking if a 9x9 Sudoku board is valid is about making sure that all the numbers are in the right spots. Let’s dive into this interesting challenge together!

Problem statement: valid sudoku

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

• Each row must contain the digits 1-9 without repetition.
• Each column must contain the digits 1-9 without repetition.
• Each of the nine 3x3 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.

Example:

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

Explanation:
In this example, the board is valid because no number repeats in any row, column, or 3x3 sub-box. All the rules of Sudoku are followed, so the output is True.

Understanding the problem

Before we jump into solving the problem, let’s make sure we understand the rules of Sudoku. Imagine you have a grid, and you need to fill it with numbers from 1 to 9. But there’s a catch! Each number can only appear once in each row, once in each column, and once in each 3x3 sub-box. If you break these rules, the board isn’t valid.

Think of it like organizing your school supplies. You can’t put two rulers in the same box, just like you can’t have two of the same number in a row, column, or sub-box. Our goal is to check if everything is where it should be.

Brute force approach

The simplest way to solve this problem is to check each row, column, and 3x3 sub-box one by one. For each of these, you’ll need to make sure that no number appears more than once. If you find a duplicate, the board is not valid.

A smarter approach

A more efficient way is to use sets. A set is like a special box where you can put items, but only if they’re not already in the box. If you try to put the same item in the set again, it won’t go in. This is perfect for our problem because we can use sets to track the numbers we’ve seen in each row, column, and sub-box. If we try to add a number that’s already in the set, we know the board isn’t valid.

Pseudocode

Let’s break down the solution into simple steps:

• Create three sets: one for rows, one for columns, and one for sub-boxes.
• Loop through each cell in the 9x9 grid.
• For each cell that contains a number (not a dot):
  • Check if the number is already in the corresponding row set, column set, or sub-box set.
  • If it is, return False because the board isn’t valid.
  • If it’s not, add the number to the sets.
• If you finish checking all the cells without finding any duplicates, return True.

Python code

Let’s start with the straightforward approach:

1def is_valid_sudoku(board):
2    for i in range(9):
3        row = set()
4        col = set()
5        box = set()
6        for j in range(9):
7            # Check row
8            if board[i][j] != '.' and board[i][j] in row:
9                return False
10            row.add(board[i][j])
11            
12            # Check column
13            if board[j][i] != '.' and board[j][i] in col:
14                return False
15            col.add(board[j][i])
16            
17            # Check 3x3 sub-box
18            box_row = 3 * (i // 3) + j // 3
19            box_col = 3 * (i % 3) + j % 3
20            if board[box_row][box_col] != '.' and board[box_row][box_col] in box:
21                return False
22            box.add(board[box_row][box_col])
23    return True

Explanation

• We use three sets for each row, column, and sub-box to track the numbers we’ve seen.
• As we go through each cell, we check if the number is already in the set. If it is, we return False.
• If all checks pass, we return True at the end.

Java code

1import java.util.HashSet;
2
3public class SudokuValidator {
4    public boolean isValidSudoku(char[][] board) {
5        for (int i = 0; i < 9; i++) {
6            HashSet<Character> row = new HashSet<>();
7            HashSet<Character> col = new HashSet<>();
8            HashSet<Character> box = new HashSet<>();
9            for (int j = 0; j < 9; j++) {
10                // Check row
11                if (board[i][j] != '.' && !row.add(board[i][j])) {
12                    return false;
13                }
14                
15                // Check column
16                if (board[j][i] != '.' && !col.add(board[j][i])) {
17                    return false;
18                }
19                
20                // Check 3x3 sub-box
21                int boxRow = 3 * (i / 3) + j / 3;
22                int boxCol = 3 * (i % 3) + j % 3;
23                if (board[boxRow][boxCol] != '.' && !box.add(board[boxRow][boxCol])) {
24                    return false;
25                }
26            }
27        }
28        return true;
29    }
30}

C++ code

1#include <vector>
2#include <unordered_set>
3
4bool isValidSudoku(const std::vector<std::vector<char>>& board) {
5    for (int i = 0; i < 9; i++) {
6        std::unordered_set<char> row;
7        std::unordered_set<char> col;
8        std::unordered_set<char> box;
9        for (int j = 0; j < 9; j++) {
10            // Check row
11            if (board[i][j] != '.' && row.find(board[i][j]) != row.end()) {
12                return false;
13            }
14            row.insert(board[i][j]);
15            
16            // Check column
17            if (board[j][i] != '.' && col.find(board[j][i]) != col.end()) {
18                return false;
19            }
20            col.insert(board[j][i]);
21            
22            // Check 3x3 sub-box
23            int boxRow = 3 * (i / 3) + j / 3;
24            int boxCol = 3 * (i % 3) + j % 3;
25            if (board[boxRow][boxCol] != '.' && box.find(board[boxRow][boxCol]) != box.end()) {
26                return false;
27            }
28            box.insert(board[boxRow][boxCol]);
29        }
30    }
31    return true;
32}

Explanation

• In all three languages, we follow the same logic.
• We use sets to check for duplicates in rows, columns, and sub-boxes.
• If any duplicate is found, the function returns False; otherwise, it returns True.

Conclusion

Determining if a 9x9 Sudoku board is valid might seem like a complex task, but with the right approach, it becomes manageable. By using sets to track the numbers in each row, column, and sub-box, we can efficiently check if the board follows all the rules of Sudoku.

This problem teaches us the importance of organizing and checking data carefully. Just like making sure all your school supplies are in the right place, validating a Sudoku board requires attention to detail and a methodical approach.