Valid Sudoku Solution In C++/Python/java/JS
Problem Description:
Determine if a 9 x 9 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 3 x 3 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.
Examples:
Input: board =
[["5","3",".",".","7",".",".",".","."]
,["6",".",".","1","9","5",".",".","."]
,[".","9","8",".",".",".",".","6","."]
,["8",".",".",".","6",".",".",".","3"]
,["4",".",".","8",".","3",".",".","1"]
,["7",".",".",".","2",".",".",".","6"]
,[".","6",".",".",".",".","2","8","."]
,[".",".",".","4","1","9",".",".","5"]
,[".",".",".",".","8",".",".","7","9"]]
Output: true
Explanation: This matrix doesn't happen to break any of the 3 rules mentioned hence it's a valid sudoku.
Input: board =
[["8","3",".",".","7",".",".",".","."]
,["6",".",".","1","9","5",".",".","."]
,[".","9","8",".",".",".",".","6","."]
,["8",".",".",".","6",".",".",".","3"]
,["4",".",".","8",".","3",".",".","1"]
,["7",".",".",".","2",".",".",".","6"]
,[".","6",".",".",".",".","2","8","."]
,[".",".",".","4","1","9",".",".","5"]
,[".",".",".",".","8",".",".","7","9"]]
Output: false
Explanation: Same as Example 1, except with the 5 in the top left corner being modified to 8. Since there are two 8's in the top left 3x3 sub-box, it is invalid.
Constraints:
- board.length == 9
- board[i].length == 9
- board[i][j] is a digit 1-9 or '.'.
Valid Sudoku Problem
In this problem, we are given a 9x9 Sudoku board and need to determine whether it is valid based on Sudoku rules. The board is considered valid if the following conditions are met:
- Each row must contain the digits 1-9 without any duplicates.
- Each column must contain the digits 1-9 without repetition.
- Each of the nine 3x3 sub-grids must also contain the digits 1-9 without any duplicates.
The function should return True if the board is valid and False otherwise.
Brute Force Approach
Intuition:
Imagine you're solving a Sudoku puzzle and you want to check if you're doing it right.
What are the rules again?
The rules must be super clear, because our code will be built around them. Let's quickly revise the three key 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 must also follow the same rule: no repeated digits.
Valid Sudoku Algorithm
We’ll go cell by cell, and for each filled cell, we’ll check:
- Is the same number repeated in its row?
- Is it repeated in its column?
- Is it repeated in its 3x3 box?
If yes, we return false immediately.
We return true if we scan the entire board and find no problems.
Simple and clean.
But wait – How Do We Check for Rows, Columns and boxes?
Let’s say we’re looking at cell (i, j), which is in the ith row and jth column.
We’ll do this:
Check the Row:
- Go through all cells in row i.
- Count how many times the same number appears.
- If it appears more than once invalid.
Check the Column:
- Go through all cells in column j.
- Same idea: count the number of times the number appears.
- More than once? → invalid.
Check the 3x3 Box:
- Think of the 9x9 Sudoku grid as being divided into 9 smaller 3x3 boxes like this:
Each box is 3 rows tall and 3 columns wide.
So for example:
- Box 0 covers rows 0–2 and columns 0–2
- Box 1 covers rows 0–2 and columns 3–5
- Box 4 covers rows 3–5 and columns 3–5
- And so on...
Let’s Take an Example:
Let’s say we’re at cell (4, 7) — that’s row 4, column 7.
Our question: Which 3x3 box does this belong to?
We want to find the starting cell of that 3x3 box — the top-left corner.
That’s where the formula comes in:
- x = (i / 3) * 3
- y = (j / 3) * 3
Now plug in i = 4 and j = 7:
- x = (4 / 3) * 3 = 1 * 3 = 3
- y = (7 / 3) * 3 = 2 * 3 = 6
So, the 3x3 box starts at cell (3, 6) and goes until (5, 8).
Now we know:
- Row range: 3 to 5
- Column range: 6 to 8
And that’s exactly the 3x3 box where cell (4, 7) lives!
Why Does This Work?
Let’s understand the logic behind the formula:
- i / 3 gives us which group of 3 rows the cell is in.
- 0 to 2 → group 0
- 3 to 5 → group 1
- 6 to 8 → group 2
- Multiply it by 3, and you will get the starting row of that group.
- The same logic applies to the columns.
So:
- (i / 3) * 3 gives the starting row of the box.
- (j / 3) * 3 gives the starting column of the box.
Now that we have the top-left corner, we can:
- loop from x to x+2 and y to y+2 — this gives us the full 3x3 box.
- Count how many times the number appears in this box.
Here’s an observation we use:
The current cell will be counted in all three checks. So the number will appear at least 3 times if it's not duplicated.
If the count is more than 3, it means there’s repetition in either row, column, or box.
To summarize the logic. We will loop through all 9 rows. Inside that, loop through all 9 columns so we’re visiting each cell (i, j). If the current cell is empty (.), skip it. Otherwise, check the row for duplicates. Check the column for duplicates. Check the 3x3 box for duplicates. Count how many times this number appears. If it appears more than 3 times, it's invalid. If the whole board passes all checks, it’s valid.
Illustration of Valid Sudoku Solution Explanation
Valid Sudoku Example
Input: board =
[["5", "3", ".", ".", "7", ".", ".", ".", "."],
["6", ".", ".", "1", "9", "5", ".", ".", "."],
[".", "9", "8", ".", ".", ".", ".", "6", "."],
["8", ".", ".", ".", "6", ".", ".", ".", "3"],
["4", ".", ".", "8", ".", "3", ".", ".", "1"],
["7", ".", ".", ".", "2", "6", ".", ".", "6"],
[".", "6", ".", ".", ".", ".", "2", "8", "."],
[".", ".", ".", "4", "1", "9", ".", ".", "5"],
[".", ".", ".", ".", "8", ".", ".", "7", "9"]]
Output: False
Explanation: The middle box contains two occurrences of ,6 which is not valid, hence false.
Outer loop:
(i = 0)
(0,0) → '5'
Row check: '5' found at (0,0)
Column check: '5' found at (0,0)
Sub-box check: '5' found at (0,0)
cnt = 3 → Valid
(0,1) → '3'
Row check: '3' found at (0,1)
Column check: '3' found at (0,1)
Sub-box check: '3' found at (0,1)
cnt = 3 → Valid
(0,4) → '7'
Row check: '7' found at (0,4)
Column check: '7' found at (0,4)
Sub-box check: '7' found at (0,4)
cnt = 3 → Valid
(i = 1)
(1,0) → '6'
Row check: '6' found at (1,0)
Column check: '6' found at (1,0)
Sub-box check: '6' found at (1,0)
cnt = 3 → Valid
(1,3) → '1'
Row check: '1' found at (1,3)
Column check: '1' found at (1,3)
Sub-box check: '1' found at (1,3)
cnt = 3 → Valid
(1,4) → '9'
Row check: '9' found at (1,4)
Column check: '9' found at (1,4)
Sub-box check: '9' found at (1,4)
cnt = 3 → Valid
(1,5) → '5'
Row check: '5' found at (1,5)
Column check: '5' found at (1,5)
Sub-box check: '5' found at (1,5)
cnt = 3 → Valid
(i = 2)
(2,1) → '9'
Row check: '9' found at (2,1)
Column check: '9' found at (2,1)
Sub-box check: '9' found at (2,1)
cnt = 3 → Valid
(2,2) → '8'
Row check: '8' found at (2,2)
Column check: '8' found at (2,2)
Sub-box check: '8' found at (2,2)
cnt = 3 → Valid
(2,7) → '6'
Row check: '6' found at (2,7)
Column check: '6' found at (2,7)
Sub-box check: '6' found at (2,7)
cnt = 3 → Valid
(i = 3)
(3,0) → '8'
Row check: '8' found at (3,0)
Column check: '8' found at (3,0)
Sub-box check: '8' found at (3,0)
cnt = 3 → Valid
(3,4) → '6'
Row check: '6' found at (3,4)
Column check: '6' found at (3,4)
Sub-box check: '6' found at (3,4) and (5, 5)
cnt = 4 → InValid → return false.
When checking for index (3,4), the box contains two occurrences of 6. Hence, we return false. 3, every number is valid.
Final Output: false (Not a Valid Sudoku)
Valid Sudoku Algorithm
Step 1: Loop Through the Entire Board
- Use two nested loops to go through every cell (i, j):
- Outer loop for each row i from 0 to 8.
- Inner loop for each column j from 0 to 8.
Step 2: Skip Empty Cells
- If the current cell contains '.' (i.e., it's empty), skip checking this cell.
Step 3: Set Up a Counter
- For every filled cell, initialize a counter to 0.
- This counter will track how many times the current number appears in:
- Its row
- Its column
- Its 3x3 sub-grid
Step 4: Count in the Row and Column
- Loop through all 9 positions in:
- The current row to count how many times the number appears.
- The current column for the same reason.
- Increment the counter for each match.
Step 5: Determine the Top-Left Index of the 3x3 Sub-grid
- For any cell (i, j), calculate the starting row and column of the 3x3 box it belongs to:
- Start row: (i / 3) * 3
- Start column: (j / 3) * 3
Step 6: Count in the 3x3 Sub-grid
- From the top-left index, loop through the 3x3 sub-grid.
- For every matching cell (same number as current), increment the counter.
Step 7: Check for Validity
- At this point, the counter should be exactly 3 (i.e., one in row, one in column, one in box — all counting the same current cell).
- If the counter is more than 3, that means the number is duplicated in one of those areas.
- In that case, immediately return false.
Step 8: Final Return
- If all cells are checked without finding any invalid condition, return true to indicate that the board is valid.
Valid Sudoku solution in all languages
Valid Sudoku solution in C++
class Solution {
public:
bool isValidSudoku(vector<vector<char>>& board) {
// Iterate through each cell in the 9x9 Sudoku board
for (int i = 0; i < 9; ++i) {
for (int j = 0; j < 9; ++j) {
// If the cell is empty ('.'), skip the iteration
if (board[i][j] == '.') continue;
int cnt = 0; // Counter to track occurrences of the current number
// Check the row and column for duplicate numbers
for (int k = 0; k < 9; ++k) {
if (board[i][k] == board[i][j]) cnt++; // Check the same row
if (board[k][j] == board[i][j]) cnt++; // Check the same column
}
// Calculate the top-left index of the 3x3 sub-box the current cell belongs to
int x = (i / 3) * 3;
int y = (j / 3) * 3;
// Iterate over the 3x3 sub-box to check for duplicate numbers
for (int k = x; k < x + 3; ++k) {
for (int l = y; l < y + 3; ++l) {
if (board[k][l] == board[i][j]) cnt++;
}
}
// Each valid number should appear **exactly 3 times**:
// - Once in its row
// - Once in its column
// - Once in its 3x3 sub-box
// If cnt exceeds 3, it means there's a duplicate → Sudoku is invalid
if (cnt > 3) return false;
}
}
// If no conflicts are found, return true (valid Sudoku)
return true;
}
};
Valid Sudoku solution in Java
class Solution {
public boolean isValidSudoku(char[][] board) {
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
// Skip empty cells
if (board[i][j] == '.') continue;
// Initialize repetition count
int cnt = 0;
// Check row and column
for (int k = 0; k < 9; k++) {
if (board[i][k] == board[i][j]) cnt++;
if (board[k][j] == board[i][j]) cnt++;
}
// Find top-left of 3x3 box
int x = (i / 3) * 3;
int y = (j / 3) * 3;
// Check 3x3 box
for (int k = x; k < x + 3; k++) {
for (int l = y; l < y + 3; l++) {
if (board[k][l] == board[i][j]) cnt++;
}
}
// If count exceeds 3, repetition exists
if (cnt > 3) return false;
}
}
return true;
}
}Valid Sudoku solution in Python
class Solution:
def isValidSudoku(self, board: List[List[str]]) -> bool:
for i in range(9):
for j in range(9):
# Skip empty cells
if board[i][j] == '.':
continue
# Initialize count
cnt = 0
# Check row and column
for k in range(9):
if board[i][k] == board[i][j]:
cnt += 1
if board[k][j] == board[i][j]:
cnt += 1
# Top-left corner of 3x3 sub-grid
x = (i // 3) * 3
y = (j // 3) * 3
# Check 3x3 sub-box
for k in range(x, x + 3):
for l in range(y, y + 3):
if board[k][l] == board[i][j]:
cnt += 1
# If more than 3 occurrences, return false
if cnt > 3:
return False
return TrueValid Sudoku solution in Javascript
/**
* @param {character[][]} board
* @return {boolean}
*/
var isValidSudoku = function(board) {
for (let i = 0; i < 9; i++) {
for (let j = 0; j < 9; j++) {
// Skip empty cells
if (board[i][j] === '.') continue;
// Initialize count
let cnt = 0;
// Check row and column
for (let k = 0; k < 9; k++) {
if (board[i][k] === board[i][j]) cnt++;
if (board[k][j] === board[i][j]) cnt++;
}
// Get top-left of 3x3 box
let x = Math.floor(i / 3) * 3;
let y = Math.floor(j / 3) * 3;
// Check 3x3 sub-box
for (let k = x; k < x + 3; k++) {
for (let l = y; l < y + 3; l++) {
if (board[k][l] === board[i][j]) cnt++;
}
}
// If count exceeds 3, duplicate exists
if (cnt > 3) return false;
}
}
return true;
}
Valid Sudoku Complexity Analysis
Time Complexity: O(1)
Outer Loop (i, j):
- There are 9 rows × 9 columns = 81 cells
- For each cell, you do work only if the cell is non-empty.
- In the worst case (all cells filled), you'll check all 81 cells.
Inner Work Per Cell:
- For each cell, you're checking:
- 9 positions in the row
- 9 positions in the column
- 9 positions in the 3×3 box
- So, O(27) operations per filled cell.
Final Time Complexity: O(81×27) = O(2187) = O(1)
Why O(1)?
Because the board size is fixed at 9×9, all operations are bounded and constant. So even though we write O(81 × 27), it's still considered constant time in Big-O notation.
Space Complexity: O(1)
Let's break down the space complexity.
- Auxiliary Space (extra memory used during computation)
- Total Space (input + auxiliary)
Auxiliary Space Complexity
- You are not using any extra arrays, sets, or maps
- Only primitive variables are used:
- int cnt
- int i, j, k, l, x, y
- All are constant-sized (fixed number of integers)
So, Auxiliary Space=O(1)
Total Space Complexity
Input Space (Part of Total Space)
- The input is a 9 × 9 grid: board
- Each character represents a digit '1' to '9' or '.'
- This board takes: 9×9=81 characters
- Since it's passed by reference, you're not duplicating it, so it does not count toward auxiliary space, but it is part of total space.
Total Space = Input space + Auxiliary space = O(81)+O(1)=O(1)
In Big-O terms, since 81 is constant, the total space complexity is still O(1).
Hence, overall space complexity is O(1)
Similar Problems
Now we have successfully tackled this problem, let's try these similar problems:-
Write a program to solve a Sudoku puzzle by filling the empty cells.
A sudoku solution must satisfy all of the following rules:
- Each of the digits 1-9 must occur exactly once in each row.
- Each of the digits 1-9 must occur exactly once in each column.
- Each of the digits 1-9 must occur exactly once in each of the 9 3x3 sub-boxes of the grid.
The '.' character indicates empty cells.
An n x n matrix is valid if every row and every column contains all the integers from 1 to n (inclusive).
Given an n x n integer matrix matrix, return true if the matrix is valid. Otherwise, return false.