Abstract / Summary

Check if a 9x9 grid follows sudoku rules without solving it.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 65% (4+ million submissions).

Typical patterns to solve this problem:

• Array
• Hash Table
• Matrix

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The presented implementation validates a 9 × 9 Sudoku board by ensuring that each filled cell does not duplicate a digit in its row, column, or 3 × 3 sub-grid. The algorithm iterates over every cell, skips empty positions marked with ‘.’, and then performs three distinct checks: a forward scan down the column, a forward scan across the row, and a full scan of the containing sub-grid while excluding the cell itself. If any duplicate is found, the function returns false; otherwise it completes the traversal and returns true.

Core Logic

The entry point is the isValidSudoku method, which receives the board as a reference to a two-dimensional vector of characters. The outer loops iterate with indices x (row) and y (column) ranging from 0 to 8. For each position the current character is stored in a local variable current. An early continue bypasses the validation steps when the cell is empty.

for (int x = 0; x < 9; x++)
    for (int y = 0; y < 9; y++)
    {
        auto current = board[x][y];
        if (current == '.')
            continue;
        // validation steps follow
    }

Row and Column Validation

The column check starts from the row directly below the current cell (xx = x + 1) and proceeds to the bottom of the board. If any cell in the same column contains the same digit, the function aborts with false. The row check mirrors this pattern, scanning columns to the right of the current cell (yy = y + 1). By only scanning forward, the algorithm avoids redundant comparisons that would have been performed when earlier cells were processed.

for (int xx = x + 1; xx < 9; xx++)
    if (current == board[xx][y])
        return false;

for (int yy = y + 1; yy < 9; yy++)
    if (current == board[x][yy])
        return false;

Sub-grid Validation

To examine the 3 × 3 block that contains the current cell, the code first computes the top-left corner of the block. Integer division by 3 isolates the block index, which is then multiplied by 3 to obtain the starting row (xx) and column (yy). A nested double loop iterates over the nine cells of the block. The condition if (xx + i == x && yy + j == y) continue; skips the cell under inspection, preventing a false positive when comparing the cell to itself. Any matching digit within the block triggers an immediate false return.

int xx = (x / 3) * 3;
int yy = (y / 3) * 3;
for (int i = 0; i < 3; i++)
    for (int j = 0; j < 3; j++)
    {
        if (xx + i == x && yy + j == y)
            continue;
        if (current == board[xx + i][yy + j])
            return false;
    }

Edge Cases Handled

The implementation gracefully handles boards that contain empty cells, represented by the period character ‘.’. By checking if (current == '.') continue; the algorithm excludes these placeholders from all duplicate checks, allowing partially filled boards to be validated without false failures.

Another subtle edge case is the avoidance of self-comparison within the sub-grid scan. The explicit skip condition ensures that the current cell does not trigger a duplicate detection against itself, which would otherwise cause every non-empty board to be rejected.

The forward-only scans for rows and columns also implicitly handle the scenario where duplicate digits appear earlier in the traversal order. Since earlier cells have already examined the later positions, a later duplicate will be caught when the earlier cell’s forward scan reaches it. This design eliminates the need for a separate backward scan.

Performance Considerations

The algorithm reduces unnecessary work by limiting column and row scans to the portion of the line that lies after the current cell. This forward-only approach halves the number of comparisons for each line relative to a naïve full-line scan, because each pair of cells is examined exactly once across the entire execution.

Computing the sub-grid origin with integer arithmetic ((x / 3) * 3) is a constant-time operation that avoids more expensive modulo or division sequences. The nested loops over the 3 × 3 block are bounded to nine iterations, guaranteeing a predictable and small overhead per cell.

Early termination is another source of efficiency. As soon as a duplicate is detected, the function returns false without processing the remaining cells. In the worst case of a valid board, the algorithm must examine every cell, but the forward-only scans and limited sub-grid checks keep the total number of comparisons modest.

Overall, the code balances clarity with a modest optimization strategy that leverages the fixed size of the Sudoku grid to keep the runtime practical for typical use cases.

Imagine a big square board made up of eighty-one smaller boxes that need numbers. This code acts like a very careful checker who looks at every single number on the board to make sure there are no mistakes.

The checker starts at the top left corner and moves across every row and down every column. When a number is found, the checker looks at the rest of that row to see if the same number is already hiding there. If a match is found, the checker knows the game is broken. Next, the checker looks down the column for that same number to make sure it is not repeated there.

Then, there is a special check for the smaller three by three squares inside the big board. The checker looks at all the other tiny boxes in that specific square to make sure the number is not appearing twice in that local area. If everything stays unique, the board is perfect.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: constant
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++	Python	Java									TS
	WalkCCC	C++	Python	Java
	leetcode.ca	C++	Python	Java	C#	Rust		JS			Go	PHP	TS
	LeetcodeHelp	C++	Python	Java
	MemoryLimitExceeded	C++	Python
	Progiez	C++	Python	Java
github	aylei					Rust
	begeekmyfriend						C
	BigEggStudy				C#
	black-shadows	C++
	bujosa					Rust
	chandansgowda		Python
	charles-wangkai			Java
	chenyanzhe	C++
	Dijkstra-Edu			Java
	everthis							JS
	fartem								Ruby
	FelixFan1122				C#
	fengvyi	C++
	fpdjsns	C++
	gaosq0604		Python
	Garvit244		Python
	halfrost										Go
	haoel	C++
	JoshCrozier							JS
	lennylxx						C
	linouk23	C++
	lkwq007		Python
	luangong	C++
	MacJim	C++
	qiyuangong		Python
	ruoru					Rust
	shreymehul				C#
	suxrobGM				C#
	varunu28			Java
	vli02						C
	vthwang			Java
	XiaotaoGuo	C++
	yuanliu666									Kotlin
	YuriSpiridonov		Python
	zfang399	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, C#, Go, Java, JavaScript, PHP, Python, Rust, TypeScript
LeetcodeHelp	C++, Java, Python
MemoryLimitExceeded	Python, C++
Progiez	C++, Java, Python
aylei	Rust
begeekmyfriend	C
BigEggStudy	C#
black-shadows	C++, C++
bujosa	Rust
chandansgowda	Python
charles-wangkai	Java
chenyanzhe	C++
Dijkstra-Edu	Java
everthis	JavaScript
fartem	Ruby
FelixFan1122	C#
fengvyi	C++
fpdjsns	C++
gaosq0604	Python
Garvit244	Python
halfrost	Go
haoel	C++
JoshCrozier	JavaScript
lennylxx	C
linouk23	C++
lkwq007	Python
luangong	C++
MacJim	C++
qiyuangong	Python
ruoru	Rust
shreymehul	C#
suxrobGM	C#
varunu28	Java
vli02	C
vthwang	Java
XiaotaoGuo	C++
yuanliu666	Kotlin
YuriSpiridonov	Python
zfang399	C++

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality