Согласно Википедии, судоку — это логическая комбинаторная головоломка с размещением чисел. В классическом судоку цель состоит в том, чтобы заполнить сетку 9 × 9 цифрами так, чтобы каждый столбец, каждая строка и каждая из девяти подсеток 3 × 3, составляющих сетку (также называемые ящиками, блоками или регионы) содержат все цифры от 1 до 9.
Это правила обычного судоку:
- Каждая строка должна содержать каждое число от 1 до 9 ровно один раз.
- Точно так же в каждом столбце требуется по одному каждому числу от 1 до 9.
- Каждая «область» 3x3 должна следовать одному и тому же шаблону 1–9.
Зная, что такое судоку и правила игры, мы можем написать программу на Python, которая берет список, содержащий числа сетки, и проверяет, составляют ли такие числа допустимое решение судоку.
ШАГ 1. Определите, как хранить судоку
Есть много способов сохранить доску судоку в Python. Вы можете использовать кортежи, наборы или даже словари для хранения чисел для каждой ячейки сетки.
В этом руководстве мы создадим список, содержащий 9 строк, который содержит 9 чисел для каждой строки на доске судоку.
Например:
Также наша программа может получить список, содержащий 9 списков, где каждый список содержит каждое число в строке в виде строки.
Ниже представлена предыдущая доска судоку, устроенная иначе:
Необязательно, но в качестве лучшей практики вы можете использовать эту функцию, чтобы проверить, является ли полученный вами список действительным отправкой:
ШАГ 2. Напишите повторно используемую функцию для проверки повторяющихся значений в строке.
На данный момент наша программа может получать судоку и проверять, является ли она действительной доской судоку. Однако он по-прежнему не может определить, есть ли повторяющиеся числа в строке, столбце или области.
Мы можем написать функцию, которая принимает список (доска судоку), перебирает его элементы (строки), проверяет, есть ли повторяющиеся значения, и возвращает True, если есть повторяющиеся значения, или False, если нет.
Чтобы использовать эту функцию, мы определим две функции для извлечения значений судоку в разном порядке.
ШАГ 3: Напишите функцию, которая получает доску и возвращает список со столбцами
В зависимости от того, как хранится судоку, первая цифра каждого элемента в списке представляет первый столбец, вторая цифра представляет второй столбец и так далее.
Эта функция будет получать доску судоку, перебирать каждую строку на доске и сохранять n-ю цифру каждой строки в списке. После сохранения столбца мы добавим список к родительскому списку и продолжим со следующими цифрами.
Вот как выглядит функция:
Если мы вызовем эту функцию с нашим образцом судоку в качестве аргумента, мы получим следующий список:
print(to_column_list(sample1))
>> [['2', '4', '8', '3', '6', '5', '7', '9', '1'],
['9', '3', '7', '8', '1', '4', '6', '2', '5'],
['5', '1', '6', '7', '2', '9', '3', '8', '4'],
['7', '8', '1', '4', '3', '2', '5', '6', '9'],
['4', '6', '9', '5', '8', '1', '2', '7', '3'],
['3', '5', '2', '9', '7', '6', '4', '1', '8'],
['8', '9', '5', '2', '4', '7', '1', '3', '6'],
['6', '2', '4', '1', '9', '3', '8', '5', '7'],
['1', '7', '3', '6', '5', '8', '9', '4', '2']]
Если вы хотите вернуть список строк вместо списков, вы можете заменить код в строке 11 следующим:
return [''.join(row) for row in nth_digit]
Новый вывод:
print(to_column_list(sample1))
>> ['248365791',
'937814625',
'516729384',
'781432569',
'469581273',
'352976418',
'895247136',
'624193857',
'173658942']
Независимо от того, какой оператор возврата вы используете, программа может использовать оба результирующих списка.
Забавный факт: вложение одной и той же функции четное количество раз вернет исходный список.
Посмотри:
print(to_column_list(to_column_list(sample1)))
>> ['295743861',
'431865927',
'876192543',
'387459216',
'612387495',
'549216738',
'763524189',
'928671354',
'154938672']
ШАГ 4: Напишите функцию, которая получает доску и возвращает список с регионами
Эта функция немного сложнее, чем предыдущая. Вместо того, чтобы перебирать всю строку или столбец, нам просто нужны 9 цифр каждого региона на доске. Для простоты функция будет повторяться слева направо и сверху вниз.
Во-первых, давайте сохраним верхние регионы вручную и проверим, есть ли шаблон, который мы могли бы использовать.
Если присмотреться, функция диапазона получает два параметра: начальное и конечное числа. Вложенные циклы for увеличивают эти числа на 3, чтобы перейти к следующему региону.
Зная это, мы можем поместить эти циклы for в другой цикл for, возвращающий 0–3–6, и добавить эти значения к параметрам диапазона.
Именно так:
Точно так же давайте сохраним другие строки регионов вручную и проверим наличие шаблонов.
Опять же, функции диапазона в строках 10, 22 и 34 каждый раз увеличивают свои параметры на 3. Наконец, мы можем создать цикл for для возврата 0–3–6, чтобы мы могли перейти к следующему ряду регионов.
Взгляните на окончательный код для этого шага:
ШАГ 5: Соберите все вместе
На данный момент у нас есть:
- Функция, проверяющая наличие повторяющихся значений в строке матрицы.
- Функция, которая проверяет, действительна ли доска судоку. (НЕОБЯЗАТЕЛЬНО)
- Функция, которая возвращает n-е значение строк в матрице.
- Функция, которая возвращает список с каждой областью судоку в виде списка.
Давайте определим функцию, которая принимает судоку, проверяет, является ли она допустимой доской, и решает, является ли это допустимым решением судоку или нет.
Поздравляем! У вас есть программа Python, которая проверяет решения судоку.
