UniLecs #Task. Sudoku

Albert Davletov

Published in

UniLecs

2 min readApr 26, 2020

Задача: необходимо проверить правильно ли расставлена начальная позиция в таблице Судоку размера 9x9, а именно:

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

Входные данные: символьная матрица, пустые клетки обозначены символом точки ‘.’.

Вывод: true/false — начальная позиция валидна или нет.

Пример:

Output: True

Разбор

Итак, нам необходимо проверить валидность начальной расстановки таблицы судоку, т.е.

нет дубликатов (цифр) ни в одной строке
нет дубликатов (цифр) ни в одном столбце
нет дубликатов (цифр) ни в одном под-блоке 3х3

Главная сложность: подсчет дубликатов в под-блоках 3х3. Для того, чтобы пройтись по таблице 1 раз и проверить все 3 условия сразу, необходимо вывести формулу для индексирования под-блоков. Для судоку 9х9 с подблоками размера 3х3 она будет следующей:

boxIndex = (row / 3) * 3 + col / 3

Теперь можно вкратце описать алгоритм проверки:

нам понадобится завести хэш-мап для каждой строки, столбца и под-блока, где ключом будет цифра, а значением — кол-во вхождений соот-но в строку/столбец/под-блок. Далее проходим по таблице и проверяем каждый цифровой символ, заносим цифру в соот.хэш-мап и проверяем кол-во вхождений этой цифры. Если мы встретим дубликат, возвращаем false.

Детали реализации смотрите ниже в коде.