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.