# python – Leetcode valid sudoku

Link here

I’ll include a solution in Python and C++ and you can review one. I’m mostly interested in reviewing the C++ code which is a thing I recently started learning; those who don’t know C++ can review the Python code. Both solutions share similar logic, so the review will apply to any.

## Problem statement

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.

Example 1:

``````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
``````

Example 2:

``````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.
``````

`valid_sudoku.py`

``````def is_valid(board, empty_value='.', b_size=3):
seen = set()
size = b_size * b_size
for row in range(size):
for col in range(size):
if (value := board(row)(col)) == empty_value:
continue
r = f'0{row}{value}'
c = f'1{col}{value}'
b = f'2{row // b_size}{col // b_size}{value}'
if r in seen or c in seen or b in seen:
return False
seen.update({r, c, b})
return True

if __name__ == '__main__':
g = (
("5", "3", ".", ".", "7", "5", ".", ".", "."),
("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"),
)
print(is_valid(g))
``````

Stats:

``````Runtime: 92 ms, faster than 81.70% of Python3 online submissions for Valid Sudoku.
Memory Usage: 14.1 MB, less than 73.95% of Python3 online submissions for Valid Sudoku.
``````

Here’s an alternative solution using numpy, it’s shorter and more readable but slower:

``````import numpy as np

def is_valid(board, size=3, empty_value='.'):
board = np.array(board)
blocks = board.reshape(4 * (size)).transpose(0, 2, 1, 3).reshape(2 * (size * size))
for grid in (board, board.T, blocks):
for line in grid:
non_empty = line(line != empty_value)
if not len(non_empty) == len(set(non_empty)):
return False
return True
``````

Stats:

``````Runtime: 172 ms, faster than 5.19% of Python3 online submissions for Valid Sudoku.
Memory Usage: 30.2 MB, less than 11.10% of Python3 online submissions for Valid Sudoku.
``````

`valid_sudoku.h`

``````#ifndef LEETCODE_VALID_SUDOKU_H
#define LEETCODE_VALID_SUDOKU_H

#include <string_view>
#include <unordered_set>

bool sudoku_check_update(const size_t &row, const size_t &col, const char &value,
const int &block_size,
std::unordered_set<std::string_view> &seen);

bool sudoku_check(const std::vector<std::vector<char>> &board,
const char &empty_value = '.');

void test1();

#endif //LEETCODE_VALID_SUDOKU_H
``````

`valid_sudoku.cpp`

``````#include <iostream>
#include <vector>
#include <string_view>
#include <cmath>
#include <unordered_set>

bool sudoku_check_update(const size_t &row, const size_t &col, const char &value,
const int &block_size,
std::unordered_set<std::string_view> &seen) {
std::string_view r, c, b;
r = "0-" + std::to_string(row) + value;
c = "1-" + std::to_string(col) + value;
b = "2-" + std::to_string(row / block_size) + std::to_string(col / block_size) +
value;
for (const auto &seen_id: {r, c, b}) {
if (seen.find(seen_id) != seen.end())
return false;
seen.insert(seen_id);
}
return true;
}

bool sudoku_check(const std::vector<std::vector<char>> &board,
const char &empty_value = '.') {
std::unordered_set<std::string_view> seen;
const auto row_size = board.size();
const int block_size = std::sqrt(row_size);
for (size_t row = 0; row < row_size; ++row) {
for (size_t col = 0; col < row_size; ++col) {
auto value = board(row)(col);
if (value == empty_value)
continue;
if (!sudoku_check_update(row, col, value, block_size, seen))
return false;
}
}
return true;
}

void test1() {
std::vector<std::vector<char>> v = {
{'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'}
};
std::cout << sudoku_check(v);
}
``````

Stats:

``````Runtime: 48 ms, faster than 17.98% of C++ online submissions for Valid Sudoku.
Memory Usage: 20.4 MB, less than 22.55% of C++ online submissions for Valid Sudoku.
``````