Valid Sudoku

Published at24 Jul 2026

Like0

Determine if a 9x9 Sudoku board is valid. A valid board has digits 1-9 appearing at most once per row, per column, and per 3x3 sub-box. Empty cells are marked with '.'. The board may be partially filled — only filled cells must follow the rules.

A brute force approach would scan each row, column, and box separately, requiring three passes over the board. A hash map approach solves it in one pass: as we iterate each cell, we track its digit in three concurrent hash maps — one for the cell's row, one for its column, and one for its 3x3 box. If any digit already exists in the corresponding map, the board is invalid.

The 3x3 box index can be computed from the cell coordinates: boxIndex = floor(row / 3) * 3 + floor(col / 3). This formula maps each cell to one of nine boxes numbered 0 through 8. The algorithm runs in O(81) = O(1) time since the board is always 9x9, and O(1) space (nine hash maps each with at most 9 entries).

Edge cases include an empty board (all '.' — valid), a board with only one row/column conflict, and a board with a box conflict that is not visible in any row or column scan. The one-pass approach catches all three simultaneously.

Example Input & Output

Example 1

Input

[["5", "3", ".", ".", "7", ".", ".", ".", "."], ["6", ".", ".", "1", "9", "5", ".", ".", "."], [".", "9", "8", ".", ".", ".", ".", "6", "."], ["8", ".", ".", ".", "6", ".", ".", ".", "3"], ["4", ".", ".", "8", ".", "3", ".", ".", "1"], ["7", ".", ".", ".", "2", ".", ".", ".", "6"], [".", "6", ".", "5", ".", ".", "2", "8", "."], ["6", ".", ".", "4", "1", "9", ".", ".", "5"], [".", ".", ".", ".", "8", ".", ".", "7", "9"]]

Output

false

Explanation

Bottom-left box has two 6s: row 6 col 1 and row 7 col 0.

Example 2

Input

[["5","5",".",".","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

Duplicate 5 in first row.

Example 3

Input

[[".",".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".",".","."]]

Output

true

Explanation

Empty board is valid.

Example 4

Input

[["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

Valid board with no conflicts.

Example 5

Input

[["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

Duplicate 8 in first column.

Algorithm Flow

Recommendation Algorithm Flow for Valid Sudoku

Solution Approach

Create three arrays of 9 hash maps for rows, columns, and boxes. Iterate each cell, compute box index, check for duplicates across all three maps.

function solution(board) {
  var rows = [{},{},{},{},{},{},{},{},{}];
  var cols = [{},{},{},{},{},{},{},{},{}];
  var boxes = [{},{},{},{},{},{},{},{},{}];
  for (var i = 0; i < 9; i++) {
    for (var j = 0; j < 9; j++) {
      var ch = board[i][j];
      if (ch === '.') continue;
      var b = Math.floor(i / 3) * 3 + Math.floor(j / 3);
      if (rows[i][ch] || cols[j][ch] || boxes[b][ch]) return false;
      rows[i][ch] = 1; cols[j][ch] = 1; boxes[b][ch] = 1;
    }
  }
  return true;
}

Time O(1), Space O(1) — fixed 9x9 board.

Best Answers
These are the verified best solutions for this Challenge. You can use them as a reference to improve your solution.

java

import java.util.*;
class Solution {
    public boolean solution(char[][] board) {
        Map<Integer,Set<Character>> rows = new HashMap<>();
        Map<Integer,Set<Character>> cols = new HashMap<>();
        Map<Integer,Set<Character>> boxes = new HashMap<>();
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                char ch = board[i][j];
                if (ch == '.') continue;
                int b = (i / 3) * 3 + j / 3;
                if (rows.computeIfAbsent(i, k -> new HashSet<>()).contains(ch) ||
                    cols.computeIfAbsent(j, k -> new HashSet<>()).contains(ch) ||
                    boxes.computeIfAbsent(b, k -> new HashSet<>()).contains(ch)) return false;
                rows.get(i).add(ch);
                cols.get(j).add(ch);
                boxes.get(b).add(ch);
            }
        }
        return true;
    }
}

javascript

function solution(board) {
  var rows = [{},{},{},{},{},{},{},{},{}];
  var cols = [{},{},{},{},{},{},{},{},{}];
  var boxes = [{},{},{},{},{},{},{},{},{}];
  for (var i = 0; i < 9; i++) {
    for (var j = 0; j < 9; j++) {
      var ch = board[i][j];
      if (ch === '.') continue;
      var b = Math.floor(i / 3) * 3 + Math.floor(j / 3);
      if (rows[i][ch] || cols[j][ch] || boxes[b][ch]) return false;
      rows[i][ch] = 1; cols[j][ch] = 1; boxes[b][ch] = 1;
    }
  }
  return true;
}

php

<?php
function solution($board) {
    $rows = array_fill(0, 9, []);
    $cols = array_fill(0, 9, []);
    $boxes = array_fill(0, 9, []);
    for ($i = 0; $i < 9; $i++) {
        for ($j = 0; $j < 9; $j++) {
            $ch = $board[$i][$j];
            if ($ch === '.') continue;
            $b = intdiv($i, 3) * 3 + intdiv($j, 3);
            if (isset($rows[$i][$ch]) || isset($cols[$j][$ch]) || isset($boxes[$b][$ch])) return false;
            $rows[$i][$ch] = 1;
            $cols[$j][$ch] = 1;
            $boxes[$b][$ch] = 1;
        }
    }
    return true;
}

python

def solution(board):
    rows = [{} for _ in range(9)]
    cols = [{} for _ in range(9)]
    boxes = [{} for _ in range(9)]
    for i in range(9):
        for j in range(9):
            ch = board[i][j]
            if ch == '.':
                continue
            b = (i // 3) * 3 + j // 3
            if ch in rows[i] or ch in cols[j] or ch in boxes[b]:
                return False
            rows[i][ch] = 1
            cols[j][ch] = 1
            boxes[b][ch] = 1
    return True

rust

use std::collections::HashSet;
fn solution(board: Vec<Vec<char>>) -> bool {
    let mut rows: [HashSet<char>; 9] = Default::default();
    let mut cols: [HashSet<char>; 9] = Default::default();
    let mut boxes: [HashSet<char>; 9] = Default::default();
    for i in 0..9 {
        for j in 0..9 {
            let ch = board[i][j];
            if ch == '.' { continue; }
            let b = (i / 3) * 3 + j / 3;
            if rows[i].contains(&ch) || cols[j].contains(&ch) || boxes[b].contains(&ch) { return false; }
            rows[i].insert(ch);
            cols[j].insert(ch);
            boxes[b].insert(ch);
        }
    }
    true
}

typescript

function solution(board: string[][]): boolean {
    var rows: any = [{},{},{},{},{},{},{},{},{}];
    var cols: any = [{},{},{},{},{},{},{},{},{}];
    var boxes: any = [{},{},{},{},{},{},{},{},{}];
    for (var i = 0; i < 9; i++) {
        for (var j = 0; j < 9; j++) {
            var ch = board[i][j];
            if (ch === '.') continue;
            var b = ~~(i / 3) * 3 + ~~(j / 3);
            if (rows[i][ch] || cols[j][ch] || boxes[b][ch]) return false;
            rows[i][ch] = 1; cols[j][ch] = 1; boxes[b][ch] = 1;
        }
    }
    return true;
}

Related Hash Table Challenges

Comments (0)

Join the Discussion

Share your thoughts, ask questions, or help others with this Challenge.

Valid Sudoku

Example Input & Output

Algorithm Flow

Solution Approach

Best AnswersThese are the verified best solutions for this Challenge. You can use them as a reference to improve your solution.

Solutions Coming Soon

Related Hash Table Challenges

Duplicate Indices Map

Contains Duplicate

Valid Anagram

Ransom Note

Two Sum Indices

Majority Element

Comments (0)

Join the Discussion

Best Answers
These are the verified best solutions for this Challenge. You can use them as a reference to improve your solution.