Лабораторная работа №2. Судоку
В этой лабораторной работе требуется написать решатель Судоку. Правила игры в Судоку достаточно простые, вот пояснения с Википедии:
Игровое поле представляет собой квадрат размером 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 read_sudoku(filename):
""" Прочитать Судоку из указанного файла """
digits = [c for c in open(filename).read() if c in '123456789.']
grid = group(digits, 9)
return grid
Задание №1: На текущий момент вашей задачей является написать функцию group()
, которая принимает пазл и размер доски n
, а в качестве результата работы возвращает матрицу размера n*n
:
def group(values, n):
"""
Сгруппировать значения 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
Чтобы убедиться в том, что вы верно написали функцию group()
воспользуйтесь доктестом:
python -m doctest sudoku.py
Результат выполнения этой команды может быть следующим:
File "/Users/dementiy/Downloads/sudoku.py", line 13, in sudoku.group
Failed example:
group([1,2,3,4], 2)
Expected:
[[1, 2], [3, 4]]
Got nothing
**********************************************************************
File "/Users/dementiy/Downloads/sudoku.py", line 15, in sudoku.group
Failed example:
group([1,2,3,4,5,6,7,8,9], 3)
Expected:
[[1, 2, 3], [4, 5, 6], [7, 8, 9]]
Got nothing
**********************************************************************
4 items had failures:
3 of 3 in sudoku.find_empty_positions
3 of 3 in sudoku.get_col
3 of 3 in sudoku.get_row
2 of 2 in sudoku.group
***Test Failed*** 11 failures
На текущий момент нас интересует только функция group()
и из двух тестов она не прошла ни один. В начале вывода показано, какой результат ожидался (Expected
), а какой получили (Got
). Если вы написали функцию верно, то эти сообщения исчезнут, но останутся сообщения для пока еще не написанных функций.
Если вы перестали видеть сообщения с ошибками для функции group()
, то давайте посмотрим как работает функция read_sudoku()
. Запустите программу следующим образом (все пазлы также в репозитории):
$ 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
Задание №2: Так как при решении Судоку ставятся условия, что значения не могут повторяться ни в строке, ни в столбце, ни в квадрате, то следовательно нам эти значения нужно получить. Для этого от вас требуется написать три функции get_row()
, get_col()
и get_block()
, каждая из которых принимает два аргумента: пазл (values
) и позицию (pos
), для которой мы пытаемся найти верное число.
def get_row(values, pos):
""" Возвращает все значения для номера строки, указанной в 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(values, pos):
""" Возвращает все значения для номера столбца, указанного в 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(values, pos):
""" Возвращает все значения из квадрата, в который попадает позиция 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
. Вы можете написать эти функции так, чтобы их можно было использовать для доски любого размера, а можете написать только для доски размером 9*9
, но тогда вы всегда будете получать ошибку в доктестах. Функция get_block()
возвращает все значения из квадрата, в который попадает позиция pos
(всего 9
квадратов размером 3*3
).
Задание №3.1: Давайте наконец перейдем к решению самого Судоку. В шаблоне вы найдете функцию solve()
, которая принимает один аргумент - пазл, а возвращает заполненную значениями доску:
def solve(grid):
""" Решение пазла, заданного в grid
Как решать Судоку?
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
В комментарии приведен алгоритм решения Судоку. Обратите внимание, что он рекурсивный. Решение Судоку очень похоже на задачу о возможных комбинациях:
Каждый раз мы удерживаем один элемент и перебираем все остальные. В Судоку все происходит точно также, сначала мы подставляем одно из возможных значений (пункт 2) для свободной позиции (пункт 1) и перебираем все остальные (пункт 3.2), то есть решаем более простую задачу. Например, вот простейшее "Судоку" (это не совсем Судоку конечно), которое мы можем заполнять значениями 1 или 2:
1.
.1
Находим первую свободную позицию (это окажется (0, 1)
), затем значения которые можем на нее поставить (в данном случае только 2), вставляем это значение на указанную позицию и продолжаем решать уже более простое Судоку:
12
.1
И так продолжаем, пока не заполним все пустые клетки. В конце мы должны получить решение Судоку.
Не забудьте про базовые случаи для выхода из рекурсии, подумайте над вопросами:
- Всегда ли есть свободная позиция?
- Всегда ли есть возможные значения?
Задание №3.2: Нам нужно находить свободные позиции (то есть те, на которых стоит .
- точка). Для этого требуется написать функцию find_empty_positons()
, которая принимает один аргумент - пазл и возвращает первую попавшуюся свободную позицию:
def find_empty_positions(grid):
""" Найти первую свободную позицию в пазле
>>> 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
Задание №3.3: Кроме поиска свободных позиций, также необходимо искать значения, которые на эту позицию можно поставить:
def find_possible_values(grid, pos):
""" Вернуть множество всех возможных значения для указанной позиции
>>> 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
Помните, что всего значений, которые мы можем поставить на указанную позицию, ровно 9
, это числа 1,2,3,4,5,6,7,8,9
. Но не каждое из этих чисел мы можем использовать (см. правила Судоку). В этой функции вы можете пользоваться написанными ранее функциями get_row()
, get_col()
, get_block()
.
Когда вы закончите работать над функциями, то выполните следующие команды:
$ 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
Задание №4: Мы получили решение, но является ли оно верным? Давайте напишем функцию check_solution()
, которая проверяет наше решение:
def check_solution(solution):
""" Если решение solution верно, то вернуть True, в противном случае False """
# PUT YOUR CODE HERE
pass
Решение оказывается верным, если ни в одной строке, ни в одном столбце, ни в квадрате не повторяются значения:
>>> check_solution(solution)
True
Когда вы закончите работать над этой функцией, то запустите программу следующим образом:
$ python sudoku.py
...
Solution is correct
...
Solution is correct
...
Solution is correct
Примечание: Вывод пазлов и их решений опущен.
Если вы встретили сообщение Ooops
, то значит, что одно или все ваши решения оказались не верны. Если же вы уверены в своем решении, то проверьте корректность функции check_solution()
.
Задание 4: Напишите функцию generate_sudoku(N)
, которая создает новый судоку, заполненный на N
элементов:
def generate_sudoku(N):
""" Генерация судоку заполненного на 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 fname in ('puzzle1.txt', 'puzzle2.txt', 'puzzle3.txt'):
grid = read_sudoku(fname)
start = time.time()
solve(grid)
end = time.time()
print(f'{fname}: {end-start}')
На моей машине результат получился таким (от запуска к запуску вы будете получать разные результаты):
puzzle1.txt: 0.05907106399536133
puzzle2.txt: 7.427937984466553
puzzle3.txt: 0.43831491470336914
Очевидно, что пазлы решаются в линейной манере, т.е. пока не будет полностью решен первый пазл мы не сможем приступить к решению второго и т.д.
Давайте попробуем воспользоватся модулем threading, чтобы каждый пазл решался в отдельном потоке:
import threading
def run_solve(fname):
grid = read_sudoku(fname)
start = time.time()
solve(grid)
end = time.time()
print(f'{fname}: {end-start}')
if __name__ == "__main__":
for fname in ('puzzle1.txt', 'puzzle2.txt', 'puzzle3.txt'):
t = threading.Thread(target=run_solve, args=(fname,))
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 fname in ('puzzle1.txt', 'puzzle2.txt', 'puzzle3.txt'):
p = multiprocessing.Process(target=run_solve, args=(fname,))
p.start()
puzzle1.txt: 0.043260812759399414
puzzle3.txt: 0.10617399215698242
puzzle2.txt: 6.155700922012329
Мы получили примерно тот же результат. В чем тогда преимущество multiprocessing
перед threading
? Чтобы лучше ощутить разницу в работе этих двух модулей попробуйте поэкспериментировать с числом решаемых пазлов и их сложностью, например:
if __name__ == "__main__":
N = 5
for _ in range(N):
t = threading.Thread(target=run_solve, args=('puzzle2.txt',))
t.start()
for _ in range(N):
p = multiprocessing.Process(target=run_solve, args=('puzzle2.txt',))
p.start()
Еще один пример сравнения модулей можно найти по этой ссылке.
Для полноты картины приведу пример решения с использованием модуля asyncio:
import asyncio
async def solve(grid):
...
result = await asyncio.ensure_future(solve(grid))
...
async def run_solve(fname):
grid = read_sudoku(fname)
start = time.time()
await solve(grid)
end = time.time()
print(f'{fname}: {end-start}')
if __name__ == '__main__':
loop = asyncio.get_event_loop()
loop.run_until_complete(asyncio.gather(
*[run_solve(f'{fname}') for fname in ('puzzle1.txt', 'puzzle2.txt', 'puzzle3.txt')]
))
loop.close()
puzzle1.txt: 0.08073115348815918
puzzle3.txt: 0.3908212184906006
puzzle2.txt: 5.103452205657959