Решатель Судоку
В этой работе требуется написать решатель Судоку. Правила игры в Судоку достаточно простые, вот пояснения с Википедии:
Quote
Игровое поле представляет собой квадрат размером 9×9, разделённый на меньшие квадраты со стороной в 3 клетки. Таким образом, всё игровое поле состоит из 81 клетки. В них уже в начале игры стоят некоторые числа от 1 до 9, называемые подсказками. От игрока требуется заполнить свободные клетки цифрами от 1 до 9 так, чтобы в каждой строке, в каждом столбце и в каждом малом квадрате 3×3 каждая цифра встречалась бы только один раз.
Далее приведен пример Судоку и его решения:
Чтение пазлов
Нам нужно каким-то образом хранить сам пазл. Для этого можно использовать обычные текстовые файлы, например, представленный выше пазл может выглядеть следующим образом:
53..7....
6..195...
.98....6.
8...6...3
4..8.3..1
7...2...6
.6....28.
...419..5
....8..79
где каждая точка соответствует пустой клетке, которую требуется заполнить числом.
Теперь нужно написать функцию для чтения пазла из файла (шаблон работы можно найти в репозитория курса). Назовем ее read_sudoku() и в качестве аргумента будем передавать путь к файлу, в котором хранится пазл:
def create_grid(puzzle: str) -> tp.List[tp.List[str]]:
digits = [c for c in puzzle if c in "123456789."]
grid = group(digits, 9)
return grid
def read_sudoku(path: tp.Union[str, pathlib.Path]) -> tp.List[tp.List[str]]:
""" Прочитать Судоку из указанного файла """
path = pathlib.Path(path)
with path.open() as f:
puzzle = f.read()
return create_grid(puzzle)
На текущий момент вашей задачей является написать функцию group(), которая принимает список значений произвольного типа T и размер группы n, а в качестве результата работы возвращает матрицу размера n*n:
T = tp.TypeVar("T")
def group(values: tp.List[T], n: int) -> tp.List[tp.List[T]]:
"""
Сгруппировать значения values в список, состоящий из списков по n элементов
>>> group([1,2,3,4], 2)
[[1, 2], [3, 4]]
>>> group([1,2,3,4,5,6,7,8,9], 3)
[[1, 2, 3], [4, 5, 6], [7, 8, 9]]
"""
# PUT YOUR CODE HERE
pass
Note
Процесс выполнения работы такой же как и предыдущей, поэтому не забудьте активировать виртуальное окружение, создавать новую ветку homework02, запускать тесты и делать коммиты.
Hint
Для решения ряда задач используйте списковые включения. Например, чтобы создать список из четных элементов в диапазоне от 0 до 10 можно использовать такую конструкцию:
>>> ll = [i for i in range(10) if i % 2 == 0]
>>> ll
[0, 2, 4, 6, 8]
Чтобы убедиться в том, что вы верно написали функцию group() воспользуйтесь юнит-тестами:
(cs102) $ python -m unittest test_sudoku.SudokuTestCase.test_group
.
----------------------------------------------------------------------
Ran 1 test in 0.000s
OK
Обратите внимание как мы указали путь к конкретному тесту файл.ТестКейс.метод. Аналогично мы можем протестировать весь тест-кейс, указав файл.ТестКейс. Если ТестКейс является единственным в файле, то достаточно указать только имя файла.
Если вы корректно реализовали функцию group(), то давайте посмотрим как работает функция read_sudoku(). Запустите скрипт с заходом в интерактивный режим (все пазлы также в репозитории):
(cs102) $ python -i sudoku.py
>>> grid = read_sudoku('puzzle1.txt')
>>> from pprint import pprint as pp
>>> pp(grid)
[['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']]
Вывод содержимого пазла grid не очень нагляден, поэтому для вас написана функция display(), которая выводит пазл в более человеко-наглядной форме:
>>> display(grid)
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
Разбивка на строки, колонки и блоки
Так как при решении Судоку ставятся условия, что значения не могут повторяться ни в строке, ни в столбце, ни в квадрате, то следовательно нам эти значения нужно получить. Для этого от вас требуется написать три функции get_row(), get_col() и get_block(), каждая из которых принимает два аргумента: пазл (grid) и позицию (pos), для которой мы пытаемся найти верное число:
def get_row(grid: tp.List[tp.List[str]], pos: tp.Tuple[int, int]) -> tp.List[str]:
""" Возвращает все значения для номера строки, указанной в pos
>>> get_row([['1', '2', '.'], ['4', '5', '6'], ['7', '8', '9']], (0, 0))
['1', '2', '.']
>>> get_row([['1', '2', '3'], ['4', '.', '6'], ['7', '8', '9']], (1, 0))
['4', '.', '6']
>>> get_row([['1', '2', '3'], ['4', '5', '6'], ['.', '8', '9']], (2, 0))
['.', '8', '9']
"""
# PUT YOUR CODE HERE
pass
def get_col(grid: tp.List[tp.List[str]], pos: tp.Tuple[int, int]) -> tp.List[str]:
""" Возвращает все значения для номера столбца, указанного в pos
>>> get_col([['1', '2', '.'], ['4', '5', '6'], ['7', '8', '9']], (0, 0))
['1', '4', '7']
>>> get_col([['1', '2', '3'], ['4', '.', '6'], ['7', '8', '9']], (0, 1))
['2', '.', '8']
>>> get_col([['1', '2', '3'], ['4', '5', '6'], ['.', '8', '9']], (0, 2))
['3', '6', '9']
"""
# PUT YOUR CODE HERE
pass
def get_block(grid: tp.List[tp.List[str]], pos: tp.Tuple[int, int]) -> tp.List[str]:
""" Возвращает все значения из квадрата, в который попадает позиция pos
>>> grid = read_sudoku('puzzle1.txt')
>>> get_block(grid, (0, 1))
['5', '3', '.', '6', '.', '.', '.', '9', '8']
>>> get_block(grid, (4, 7))
['.', '.', '3', '.', '.', '1', '.', '.', '6']
>>> get_block(grid, (8, 8))
['2', '8', '.', '.', '.', '5', '.', '7', '9']
"""
# PUT YOUR CODE HERE
pass
Разберемся с тем, как представлена позиция в программе. Каждая позиция однозначно определяется номером строки и номером столбца, поэтому для ее представления удобно использовать кортеж. Вспомним, что кортеж это неизменяемый список. Позиция создается следующим образом:
>>> pos = (0, 0)
>>> row, col = pos
>>> row
0
>>> col
0
Обратите внимание, что для функций get_row() и get_col() приведены примеры в доктестах для доски размером 3*3. У нас же доска 9*9, но функции должны работать для доски любого размера. Функция get_block() возвращает все значения из квадрата, в который попадает позиция pos (всего 9 квадратов размером 3*3).
Не забудьте запустить тесты и сделать соответствующие коммиты:
(cs102) $ python -m unittest \
test_sudoku.SudokuTestCase.test_get_col \
test_sudoku.SudokuTestCase.test_get_row \
test_sudoku.SudokuTestCase.test_get_block
...
----------------------------------------------------------------------
Ran 3 tests in 0.001s
OK
Алгоритм решения Судоку
Давайте наконец перейдем к решению самого Судоку. В шаблоне вы найдете функцию solve(), которая принимает один аргумент - пазл, а возвращает заполненную значениями доску:
def solve(grid: tp.List[tp.List[str]]) -> tp.Optional[tp.List[tp.List[str]]]:
""" Поиск решения для указанного пазла.
Как решать Судоку?
1. Найти свободную позицию
2. Найти все возможные значения, которые могут находиться на этой позиции
3. Для каждого возможного значения:
3.1. Поместить это значение на эту позицию
3.2. Продолжить решать оставшуюся часть пазла
>>> grid = read_sudoku('puzzle1.txt')
>>> solve(grid)
[['5', '3', '4', '6', '7', '8', '9', '1', '2'], ['6', '7', '2', '1', '9', '5', '3', '4', '8'], ['1', '9', '8', '3', '4', '2', '5', '6', '7'], ['8', '5', '9', '7', '6', '1', '4', '2', '3'], ['4', '2', '6', '8', '5', '3', '7', '9', '1'], ['7', '1', '3', '9', '2', '4', '8', '5', '6'], ['9', '6', '1', '5', '3', '7', '2', '8', '4'], ['2', '8', '7', '4', '1', '9', '6', '3', '5'], ['3', '4', '5', '2', '8', '6', '1', '7', '9']]
"""
# PUT YOUR CODE HERE
pass
Мы будем решать Судоку методом перебора (поиска) с возвратом. Общая схема этого метода заключается в следующем:
def Перебор(Ситуация):
if Ситуация конечная:
Завершающая обработка
else:
for Действие in Множество всех возможных действий:
Применить Действие к Ситуация
Перебор(Ситуация)
откатить Действие назад
Решение Судоку чем-то похоже на задачу о возможных комбинациях:
def permutations(L: tp.List[tp.Any], result: tp.List[tp.Any]) -> None:
if len(L) == 0:
print(result)
else:
for i in range(len(L)):
permutations(L[0:i] + L[i+1:], result + [L[i]])
>>> permutations([1,2,3], [])
Каждый раз мы удерживаем один элемент и перебираем все остальные. В Судоку все происходит точно также, сначала мы подставляем одно из возможных значений (пункт 2) для свободной позиции (пункт 1) и перебираем все остальные (пункт 3.2), то есть решаем более простую задачу. Например, вот простейшее «Судоку» (это не совсем Судоку конечно), которое мы можем заполнять значениями 1 или 2:
1.
.1
Находим первую свободную позицию (это окажется (0, 1)), затем значения которые можем на нее поставить (в данном случае только 2), вставляем это значение на указанную позицию и продолжаем решать уже более простое Судоку:
12
.1
И так продолжаем, пока не заполним все пустые клетки. В конце мы должны получить решение Судоку.
Не забудьте про базовые случаи для выхода из рекурсии, подумайте над вопросами:
- Всегда ли есть свободная позиция?
- Всегда ли есть возможные значения?
Поиск возможных решений
Нам нужно находить свободные позиции (то есть те, на которых стоит . - точка). Для этого требуется написать функцию find_empty_positons(), которая принимает один аргумент - пазл и возвращает первую попавшуюся свободную позицию:
def find_empty_positions(grid: tp.List[tp.List[str]]) -> tp.Optional[tp.Tuple[int, int]]:
""" Найти первую свободную позицию в пазле
>>> find_empty_positions([['1', '2', '.'], ['4', '5', '6'], ['7', '8', '9']])
(0, 2)
>>> find_empty_positions([['1', '2', '3'], ['4', '.', '6'], ['7', '8', '9']])
(1, 1)
>>> find_empty_positions([['1', '2', '3'], ['4', '5', '6'], ['.', '8', '9']])
(2, 0)
"""
# PUT YOUR CODE HERE
pass
Кроме поиска свободных позиций, также необходимо искать значения, которые на эту позицию можно поставить:
def find_possible_values(grid: tp.List[tp.List[str]], pos: tp.Tuple[int, int]) -> tp.Set[str]:
""" Вернуть множество всех возможных значения для указанной позиции
>>> grid = read_sudoku('puzzles/puzzle1.txt')
>>> values = find_possible_values(grid, (0,2))
>>> set(values) == {'1', '2', '4'}
True
>>> values = find_possible_values(grid, (4,7))
>>> set(values) == {'2', '5', '9'}
True
"""
# PUT YOUR CODE HERE
pass
Hint
Для решения этого задания используйте множества set.
Помните, что всего значений, которые мы можем поставить на указанную позицию, ровно 9, это числа 1,2,3,4,5,6,7,8,9. Но не каждое из этих чисел мы можем использовать (см. правила Судоку). В этой функции вы можете пользоваться написанными ранее функциями get_row(), get_col(), get_block().
К этому моменту функция solve() уже должна быть полностью рабочей:
(cs102) $ python -i sudoku.py
>>> grid = read_sudoku('puzzle1.txt')
>>> display(grid)
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
>>> solution = solve(grid)
>>> display(solution)
5 3 4 |6 7 8 |9 1 2
6 7 2 |1 9 5 |3 4 8
1 9 8 |3 4 2 |5 6 7
------+------+------
8 5 9 |7 6 1 |4 2 3
4 2 6 |8 5 3 |7 9 1
7 1 3 |9 2 4 |8 5 6
------+------+------
9 6 1 |5 3 7 |2 8 4
2 8 7 |4 1 9 |6 3 5
3 4 5 |2 8 6 |1 7 9
Проверка решения
Мы получили решение, но является ли оно верным? Давайте напишем функцию check_solution(), которая проверяет наше решение:
def check_solution(solution: tp.List[tp.List[str]]) -> bool:
""" Если решение solution верно, то вернуть True, в противном случае False """
# PUT YOUR CODE HERE
pass
Решение оказывается верным, если ни в одной строке, ни в одном столбце, ни в квадрате не повторяются значения:
>>> check_solution(solution)
True
Когда вы закончите работать над этой функцией, то запустите программу следующим образом:
(cs102) $ python sudoku.py
...
Solution is correct
...
Solution is correct
...
Solution is correct
Если вы встретили сообщение Ooops, то значит, что одно или все ваши решения оказались не верны. Если же вы уверены в своем решении, то проверьте корректность функции check_solution().
Генерация новых пазлов
Напишите функцию generate_sudoku(N), которая создает новый судоку, заполненный на N элементов:
def generate_sudoku(N: int) -> tp.List[tp.List[str]]:
""" Генерация судоку заполненного на N элементов
>>> grid = generate_sudoku(40)
>>> sum(1 for row in grid for e in row if e == '.')
41
>>> solution = solve(grid)
>>> check_solution(solution)
True
>>> grid = generate_sudoku(1000)
>>> sum(1 for row in grid for e in row if e == '.')
0
>>> solution = solve(grid)
>>> check_solution(solution)
True
>>> grid = generate_sudoku(0)
>>> sum(1 for row in grid for e in row if e == '.')
81
>>> solution = solve(grid)
>>> check_solution(solution)
True
"""
# PUT YOUR CODE HERE
pass
Пример использования функции:
>>> sudoku = generate_sudoku(40)
>>> display(sudoku)
. 3 . |6 . 8 |. . .
6 . 2 |. 9 . |3 4 .
. . . |3 4 . |. 6 7
------+------+------
. 5 . |7 . 1 |. 2 .
. . 6 |8 . 3 |. 9 1
7 . 3 |. 2 . |8 . 6
------+------+------
9 . . |5 . 7 |2 . 4
. . 7 |4 . . |. . .
3 4 5 |. 8 6 |1 7 .
Приложение
Вы заметили, что второй пазл решается дольше остальных?
import time
if __name__ == "__main__":
for filename in ("puzzle1.txt", "puzzle2.txt", "puzzle3.txt"):
grid = read_sudoku(filename)
start = time.time()
solve(grid)
end = time.time()
print(f"{filename}: {end-start}")
На моей машине результат получился таким (от запуска к запуску вы будете получать разные результаты):
puzzle1.txt: 0.05907106399536133
puzzle2.txt: 7.427937984466553
puzzle3.txt: 0.43831491470336914
Очевидно, что пазлы решаются в линейной манере, т.е. пока не будет полностью решен первый пазл мы не сможем приступить к решению второго и т.д.
Давайте попробуем воспользоватся модулем threading, чтобы каждый пазл решался в отдельном потоке:
import threading
def run_solve(filename: str) -> None:
grid = read_sudoku(filename)
start = time.time()
solve(grid)
end = time.time()
print(f"{filename}: {end-start}")
if __name__ == "__main__":
for filename in ("puzzle1.txt", "puzzle2.txt", "puzzle3.txt"):
t = threading.Thread(target=run_solve, args=(filename,))
t.start()
puzzle1.txt required 0.013156652450561523
puzzle3.txt required 0.7069487571716309
puzzle2.txt required 7.912024021148682
Из результатов видно, что решение для puzzle3 мы получили раньше чем для puzzle2, но тем не менее они не были решены параллельно, как можно было бы подумать, и связано это с таким понятием как GIL.
Чтобы решать пазлы параллельно (за исключением разных если) мы можем воспользоваться модулем multiprocessing:
import multiprocessing
if __name__ == "__main__":
for filename in ("puzzle1.txt", "puzzle2.txt", "puzzle3.txt"):
p = multiprocessing.Process(target=run_solve, args=(filename,))
p.start()
puzzle1.txt: 0.043260812759399414
puzzle3.txt: 0.10617399215698242
puzzle2.txt: 6.155700922012329
Мы получили примерно тот же результат. В чем тогда преимущество multiprocessing перед threading? Чтобы лучше ощутить разницу в работе этих двух модулей попробуйте поэкспериментировать с числом решаемых пазлов и их сложностью. Список сложных пазлов можно найти в репозитории в файле hard_puzzles.txt.