Задача: 36. Valid Sudoku
Сложность: medium

Определите, является ли доска Судоку размером 9x9 валидной. Нужно проверить только заполненные ячейки:

- В каждой строке цифры 1-9 должны быть без повторений.
- В каждом столбце цифры 1-9 должны быть без повторений.
- В каждом 3x3 блоке цифры 1-9 должны быть без повторений.

Пример:

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  

👨‍💻 Алгоритм:

1⃣Создайте три массива множеств: для строк, столбцов и блоков 3x3.

2⃣Проходя по каждой ячейке и проверяя, не встречалось ли число в соответствующей строке, столбце или блоке

3⃣Если не встретилось — добавить и продолжить; если встреча состоялась — вернуть false

😎 Решение:

public class Solution {
    public bool IsValidSudoku(char[][] board) {
        int N = 9;
        HashSet<char>[] rows = new HashSet<char>[N];
        HashSet<char>[] cols = new HashSet<char>[N];
        HashSet<char>[] boxes = new HashSet<char>[N];

        for (int i = 0; i < N; i++) {
            rows[i] = new HashSet<char>();
            cols[i] = new HashSet<char>();
            boxes[i] = new HashSet<char>();
        }

        for (int r = 0; r < N; r++) {
            for (int c = 0; c < N; c++) {
                char val = board[r][c];
                if (val == '.') continue;

                if (rows[r].Contains(val) || cols[c].Contains(val) || boxes[(r / 3) * 3 + c / 3].Contains(val)) {
                    return false;
                }

                rows[r].Add(val);
                cols[c].Add(val);
                boxes[(r / 3) * 3 + c / 3].Add(val);
            }
        }

        return true;
    }
}

Ставь 👍 и забирай 📚 Базу знаний