Практическая задача Python 5: Решение головоломки судоку
Ваша последняя практическая задача на Python – решить головоломку судоку !
Найти быстрое и эффективное с точки зрения памяти решение этой проблемы может оказаться непростой задачей. Решение, которое вы исследуете, было выбрано из соображений удобочитаемости, а не скорости, но вы можете оптимизировать свое решение по своему усмотрению.
Описание проблемы
Описание решателя судоку немного сложнее, чем предыдущие задачи:
# sudokusolve.py
""" Sudoku Solver
Примечание: описание головоломки судоку можно найти по адресу:
https://ru.wikipedia.org/wiki/Судоку
Учитывая строку в формате SDM, описанную ниже, напишите программу для поиска и
возврата решения головоломки судоку в строке. Решение должно быть возвращено в
том же формате SDM, что и входные данные.
Некоторые головоломки не будут разрешимы. В этом случае верните строку "неразрешимо".
Общий формат SDM описан здесь:
http://www.sudocue.net/fileformats.php
Для наших целей каждая строка SDM будет представлять собой последовательность из 81 цифры,
по одной для каждой позиции в головоломке судоку. Известные числа будут даны,
а неизвестные позиции будут иметь нулевое значение.
Например, предположим, что вам дана эта строка цифр (разделенная на две строки для удобства чтения):
0040060790000006020560923000780610305090004
06020540890007410920105000000840600100
Строка представляет собой эту стартовую головоломку судоку:
0 0 4 0 0 6 0 7 9
0 0 0 0 0 0 6 0 2
0 5 6 0 9 2 3 0 0
0 7 8 0 6 1 0 3 0
5 0 9 0 0 0 4 0 6
0 2 0 5 4 0 8 9 0
0 0 7 4 1 0 9 2 0
1 0 5 0 0 0 0 0 0
8 4 0 6 0 0 1 0 0
Выполнение предоставленных модульных тестов может занять некоторое время, так что будьте терпеливы.
"""
Вы можете видеть, что вам нужно иметь дело с чтением и записью в конкретный формат, а также с созданием решения.
Решение проблемы
Это более крупная и сложная проблема, чем вы рассматривали до сих пор в этой серии статей. Вы пройдете через эту проблему шаг за шагом, заканчивая рекурсивная функция это решает загадку. Вот примерный план шагов, которые вы предпримете:
- Читать головоломка в виде сетки.
- Для каждой ячейки:
- Для каждого возможного числа в этой ячейке:
- Место номер в камере.
- Удалять это число из строки, столбца и маленького квадрата.
- Подвиньте на следующую позицию.
- Если никаких возможных чисел не осталось, то объявите головоломку неразрешимый.
- Если все ячейки заполнены, то верните решение.
- Для каждого возможного числа в этой ячейке:
Хитрая часть этого алгоритма заключается в отслеживании сетки на каждом этапе процесса. Вы будете использовать рекурсию, создавая новую копию сетки на каждом уровне рекурсии, чтобы сохранить эту информацию.
Имея в виду этот план, Давайте начнем с первого шага – создания сетки.
Создание сетки из линии
Для начала полезно преобразовать данные головоломки в более удобный формат. Даже если вы в конечном итоге хотите решить головоломку в данной Формат SDM скорее всего, вы добьетесь более быстрого прогресса в проработке деталей вашего алгоритма с данными в виде сетки. Как только у вас есть решение, которое работает, вы можете преобразовать его для работы с другой структурой данных.
Для этого давайте начнем с пары функций преобразования:
1 # sudokusolve.py 2 def line_to_grid(values): 3 grid = [] 4 line = [] 5 for index, char in enumerate(values): 6 if index and index % 9 == 0: 7 grid.append(line) 8 line = [] 9 line.append(int(char)) 10 # Добавьте последнюю строку 11 grid.append(line) 12 return grid 13 14 def grid_to_line(grid): 15 line = "" 16 for row in grid: 17 r = "".join(str(x) for x in row) 18 line += r 19 return line
Ваша первая функция, line_to_grid(), преобразует данные из одной строки из восьмидесяти одной цифры в список списков. Например, он преобразует строку line к сетке, как start:
line = "0040060790000006020560923000780...90007410920105000000840600100"
start = [
[ 0, 0, 4, 0, 0, 6, 0, 7, 9],
[ 0, 0, 0, 0, 0, 0, 6, 0, 2],
[ 0, 5, 6, 0, 9, 2, 3, 0, 0],
[ 0, 7, 8, 0, 6, 1, 0, 3, 0],
[ 5, 0, 9, 0, 0, 0, 4, 0, 6],
[ 0, 2, 0, 5, 4, 0, 8, 9, 0],
[ 0, 0, 7, 4, 1, 0, 9, 2, 0],
[ 1, 0, 5, 0, 0, 0, 0, 0, 0],
[ 8, 4, 0, 6, 0, 0, 1, 0, 0],
]
Каждый внутренний список здесь представляет собой горизонтальную строку в вашей головоломке судоку.
Вы начинаете с пустого места grid и пустой line. Затем вы строите каждый из них line путем преобразования девяти символов из строки values для однозначных целых чисел, а затем добавление их к текущему line. Как только у вас есть девять значений в line, как указано в index % 9 == 0 в строке 7 вы вставляете это line в grid и начинаете новую жизнь.
Функция завершается добавлением финала line к grid. Вам это нужно, потому что цикл for закончится с последним line все еще хранится в локальной переменной и еще не добавлено к ней grid.
Обратная функция, grid_to_line(), немного короче. Она использует a выражение генератора с join() чтобы создать девятизначную строку для каждой строки. Затем он добавляет эту строку к общему списку line и возвращает его. Обратите внимание, что можно использовать вложенные генераторы для создания этого результата в меньшем количестве строк кода, но читабельность решения начинает резко падать.
Теперь, когда у вас есть данные в нужной структуре данных, давайте начнем работать с ними.
Генерация небольшого цикла квадратов
Ваша следующая функция-генератор, который поможет вам найти меньший квадрат размером три на три, в котором находится данная позиция. Учитывая координаты x и y рассматриваемой ячейки, этот генератор выдаст список координат, соответствующих содержащему ее квадрату:
На изображении выше вы рассматриваете ячейку (3, 1), таким образом, ваш генератор будет производить пары координат, соответствующие всем слегка заштрихованным ячейкам, пропуская координаты, которые были переданы в:
(3, 0), (4, 0), (5, 0), (4, 1), (5, 1), (3, 2), (4, 2), (5, 2)
Если поместить логику определения этого небольшого квадрата в отдельную служебную функцию, то поток других ваших функций будет более читабельным. Создание этого генератора позволяет использовать его в for цикл для итерации по каждому из значений.
Функция для этого включает в себя использование ограничений целочисленной математики:
# sudokusolve.py
def small_square(x, y):
upperX = ((x + 3) // 3) * 3
upperY = ((y + 3) // 3) * 3
lowerX = upperX - 3
lowerY = upperY - 3
for subX in range(lowerX, upperX):
for subY in range(lowerY, upperY):
# If subX != x or subY != y:
if not (subX == x and subY == y):
yield subX, subY
В паре таких строк есть много троек, что делает строки похожими на ((x + 3) // 3) * 3 выглядит запутанно. Вот что происходит, когда x является 1.
>>>
>>> x = 1 >>> x + 3 4 >>> (x + 3) // 3 1 >>> ((x + 3) // 3) * 3 3
Использование округления целочисленной математики позволяет получить следующее по величине кратное трем выше заданного значения. Как только вы это сделаете, вычитание трех даст вам кратное трем ниже заданного числа.
Есть еще несколько низкоуровневых утилит, которые нужно изучить, прежде чем вы начнете строить поверх них.
Переходим к следующему месту
Ваше решение должно будет проходить через сеточную структуру по одной ячейке за раз. Это означает, что в какой-то момент вам нужно будет выяснить, какой должна быть следующая позиция. compute_next_position() на помощь!
compute_next_position() принимает текущие координаты x и y в качестве входных данных и возвращает кортеж, содержащий флаг finished вместе с координатами x и y следующей позиции:
# sudokusolve.py
def compute_next_position(x, y):
nextY = y
nextX = (x + 1) % 9
if nextX < x:
nextY = (y + 1) % 9
if nextY < y:
return (True, 0, 0)
return (False, nextX, nextY)
Флаг finished сообщает вызывающему, что алгоритм вышел из конца головоломки и завершил все квадраты. Вы увидите, как это используется в следующем разделе.
Удаление невозможных чисел
Ваша конечная низкоуровневая утилита довольно мала. Он принимает целочисленное значение и итерацию. Если значение ненулевое и появляется в iterable, то функция удаляет его из iterable:
# sudokusolve.py
def test_and_remove(value, possible):
if value != 0 and value in possible:
possible.remove(value)
Как правило, вы не превратили бы этот маленький кусочек функциональности в функцию. Однако вы будете использовать эту функцию несколько раз, поэтому лучше всего следовать Сухой принцип и подтяните его к функции.
Теперь вы увидели нижний уровень пирамиды функциональности. Пришло время сделать шаг вперед и использовать эти инструменты для построения более сложной функции. Вы почти готовы решить головоломку!
Найти то, что возможно
Ваша следующая функция использует некоторые из низкоуровневых функций, которые вы только что прошли. Учитывая сетку и позицию на этой сетке, он определяет, какие значения эта позиция все еще может иметь:
Для сетки выше, на позиции (3, 1), возможные значения таковы: [1, 5, 8] потому что все остальные значения присутствуют либо в этой строке или столбце, либо в маленьком квадрате, который вы рассматривали ранее.
Это входит в обязанности detect_possible():
# sudokusolve.py
def detect_possible(grid, x, y):
if grid[x][y]:
return [grid[x][y]]
possible = set(range(1, 10))
# Test horizontal and vertical
for index in range(9):
if index != y:
test_and_remove(grid[x][index], possible)
if index != x:
test_and_remove(grid[index][y], possible)
# Test in small square
for subX, subY in small_square(x, y):
test_and_remove(grid[subX][subY], possible)
return list(possible)
Функция начинается с проверки того, находится ли данная позиция на x и y уже имеет ненулевое значение. Если это так, то это единственное возможное значение, и оно возвращается.
Если нет, то функция создает набор чисел от одного до девяти. Функция продолжает проверять различные номера блокировки и удаляет их из этого набора.
Он начинается с проверки столбца и строки данной позиции. Это можно сделать с помощью одного цикла, просто чередуя изменения индекса. grid[x][index] проверяет значения в том же столбце, В то время как grid[index][y] проверяет эти значения в одной строке. Вы можете видеть, что вы используете test_and_remove() здесь, чтобы упростить код.
Как только эти ценности будут удалены из вашего possible после установки функция переходит к небольшому квадрату. Вот где находится генератор small_square(), который вы создали раньше, пригодится. Вы можете использовать его для перебора каждой позиции в маленьком квадрате, снова используя test_and_remove() чтобы исключить любые известные значения из вашего списка possible.
Как только все известные значения блокировки будут удалены из вашего набора, у вас будет список всех значений possible для этой позиции в этой сетке.
Вы можете задаться вопросом, почему код и его описание указывают на то, что позиция находится “на этой сетке”. В следующей функции вы увидите, что программа создает множество копий сетки, пытаясь решить ее.
Решение этой проблемы
Вы достигли сути этого решения: solve()! Эта функция рекурсивна, поэтому небольшое предварительное объяснение может помочь.
Общая конструкция solve() основан на тестировании одной позиции за один раз. Для интересующей позиции алгоритм получает список возможных значений и затем выбирает эти значения, по одному за раз, чтобы быть в этой позиции.
Для каждого из этих значений он создает сетку с угаданным значением в этой позиции. Затем он вызывает функцию для проверки решения, передавая новую сетку и следующую позицию.
Так уж получилось, что функция, которую он вызывает, – это он сам.
Для любой рекурсии необходимо условие завершения. Этот алгоритм имеет четыре из них:
- Для этой позиции нет никаких возможных значений. Это указывает на то, что решение, которое он тестирует, не может работать.
- Он прошел до конца сетки и нашел возможное значение для каждой позиции. Загадка решена!
- Одна из догадок в этой позиции, возвращенная решателю, возвращает решение.
- Он перепробовал все возможные значения на этой позиции, и ни одно из них не сработает.
Давайте посмотрим на код для этого и посмотрим, как все это происходит:
# sudokusolve.py
import copy
def solve(start, x, y):
temp = copy.deepcopy(start)
while True:
possible = detect_possible(temp, x, y)
if not possible:
return False
finished, nextX, nextY = compute_next_position(x, y)
if finished:
temp[x][y] = possible[0]
return temp
if len(possible) > 1:
break
temp[x][y] = possible[0]
x = nextX
y = nextY
for guess in possible:
temp[x][y] = guess
result = solve(temp, nextX, nextY)
if result:
return result
return False
Первое, что следует отметить в этой функции, – это то, что она делает deepcopy() из сетки. Это делает глубокое копирование потому что алгоритм должен точно отслеживать, где он был в любой момент рекурсии. Если бы функция создавала только поверхностную копию, то каждая рекурсивная версия этой функции использовала бы одну и ту же сетку.
Как только сетка будет скопирована, solve() может работать с новой копией temp. Была передана позиция на сетке, так что это число, которое будет решать эта версия функции. Первый шаг-посмотреть, какие значения возможны в этой позиции. Как вы видели ранее, detect_possible() возвращает список возможных значений, которые могут быть пустыми.
Если нет никаких возможных значений, то вы попали в первое условие завершения рекурсии. Функция возвращает False и вызов return переводит на продолжение цикла.
Если есть если это возможные значения, то вам нужно двигаться дальше и посмотреть, является ли какое-либо из них решением. Перед этим вы можете добавить в код небольшую оптимизацию. Если есть только одно возможное значение, то вы можете вставить это значение и перейти к следующей позиции. Показанное решение делает это в цикле, так что вы можете поместить несколько чисел в сетку без необходимости повторяться.
Это может показаться небольшим улучшением, и мы признаем, что наша первая реализация не включала этого. Но некоторые тесты показали, что это решение было значительно быстрее, чем просто повторение здесь по цене более сложного кода.
Примечание: Это отличный момент, чтобы поднять во время интервью, даже если вы не добавляете код для этого. Показать им, что вы думаете о том, чтобы обменять скорость на сложность, – это сильный позитивный сигнал для интервьюеров.
Иногда, конечно, существует несколько возможных значений для текущей позиции, и вам нужно решить, приведет ли какое-либо из них к решению. К счастью, вы уже определили следующую позицию в сетке, поэтому можете отказаться от размещения возможных значений.
Если следующая позиция находится вне конца сетки, то текущая позиция является последней для заполнения. Если вы знаете, что существует хотя бы одно возможное значение для этой позиции, то вы нашли решение! Текущая позиция заполняется, и заполненная сетка возвращается вызывающей функции.
Если следующая позиция все еще находится в сетке, то вы перебираете каждое возможное значение для текущего пятна, заполняя предположение о текущей позиции, а затем вызываете solve(temp) с сеткой и новой позицией для тестирования.
solve() может возвращать только заполненную сетку или False, так что если какая-либо из возможных догадок возвращает результат, который не является False, то результат был найден, и эта сетка может быть возвращена вверх по стеку.
Если все возможные догадки были сделаны, и ни одна из них не является решением, то сетка, которая была передана, неразрешима. Если это вызов верхнего уровня, то это означает, что загадка неразрешима. Если вызов находится ниже в дереве рекурсии, то это просто означает, что эта ветвь дерева рекурсии не жизнеспособна.
Продолжение следует…
Начало:
- Проблемы с практикой Python. Приготовьтесь к следующему собеседованию. Часть 1
- Проблемы с практикой Python. Приготовьтесь к следующему собеседованию. Шифр Цезаря Часть 2
- Проблемы с практикой Python. Приготовьтесь к следующему собеседованию. Анализатор журнала. Часть 3
Продолжение: