Внимательно изучите этот код и найдите умный способ использовать рекурсию для решения этих хитрых головоломок судоку.
Судоку — популярная головоломка с числами, состоящая из сетки 9x9 с цифрами от 1 до 9. Головоломка включает в себя комбинацию чисел и несколько пустых мест, которые вам нужно заполнить.
При заполнении пустых мест каждая строка, столбец и подсетка 3x3 должны содержать все цифры от 1 до 9.
Простой скрипт Python может помочь вам решить головоломку судоку. Он может анализировать все пустые места на доске судоку и находить возможное число для заполнения каждого пустого места.
Как создать и отобразить доску судоку
Внутри сценария Python вам нужно будет использовать список массивов для хранения значений нерешенной головоломки судоку.
Код, используемый в этом проекте, доступен в этом репозиторий GitHub по лицензии MIT.
- Внутри нового скрипта Python с именем sudoku.py сохраните все значения для сетки 9x9. Каждая строка и столбец представляют девять чисел в головоломке судоку. Добавьте 0 для представления пробелов, которые необходимо решить:
доска = [
[5, 3, 0, 0, 7, 0, 0, 0, 0],
[6, 0, 0, 1, 9, 5, 0, 0, 0],
[0, 9, 8, 0, 0, 0, 0, 6, 0],
[8, 0, 0, 0, 6, 0, 0, 0, 3],
[4, 0, 0, 8, 0, 3, 0, 0, 1],
[7, 0, 0, 0, 2, 0, 0, 0, 6],
[0, 6, 0, 0, 0, 0, 2, 8, 0],
[0, 0, 0, 4, 1, 9, 0, 0, 5],
[0, 0, 0, 0, 8, 0, 0, 7, 9]
] - Внутри новой функции, называемой print_board, использовать цикл for для обработки каждой строки в сетке:
дефдоска_печати(доска):
для ряд в диапазон(9): - Чтобы разделить каждую строку на трети, проверьте, делится ли строка на три, и добавьте строку:
если ряд % 3 == 0и ряд != 0:
Распечатать("- - - - - - - - - - - - - - ") - В каждой строке прокрутите каждый столбец. Вы также можете разделить столбцы на трети, проверив, делится ли столбец на три:
для колонка в диапазон(9):
если цвет % 3 == 0и столбец != 0:
Распечатать(" | ", конец ="") - Распечатайте числовое значение, хранящееся в сетке. Если столбец является последним столбцом для этой конкретной строки, добавьте строку разрыва, чтобы следующая строка появилась на новой строке:
если столбец == 8:
печать (доска [строка] [столбец])
еще:
print (str (board[row][col]) + " ", конец ="") - Вызовите функцию для печати платы:
print_board (доска) - В командной строке перейдите в папку, в которой вы сохранили свой скрипт Python, например:
компакт-диск Рабочий стол - Используйте команду python для запуска сценария судоку. Просмотрите головоломку, напечатанную на экране:
Python судоку.py
Как определить пустые места для решения
Вы можете просмотреть списки, чтобы найти пробелы, состоящие из 0. Они определяют, какие пространства необходимо решить.
- В новой функции find_empty() прокрутите каждую строку и столбец на доске:
дефнайти_пустой(доска):
для ряд в диапазон(9):
для колонка в диапазон(9): - Если значение текущей ячейки равно 0, вернуть текущую позицию пустой ячейки:
если доска[строка][столбец] == 0:
возвращаться (строка, столбец) - Если скрипт достигает конца функции, это означает, что скрипт не смог найти ни одной ячейки со значением 0. В этом случае ничего не возвращайте:
возвращатьсяНикто - В новой функции с именемsolve() используйте функцию find, чтобы найти первое пустое место на доске:
дефрешать(доска):
найти = найти_пусто (доска) - Функция find_empty() возвращает позицию ячейки в формате кортежа, например, (0, 2). Сохраните эти значения отдельно в ряд и колонка переменные. В противном случае верните true, чтобы показать, что пустых мест для решения не осталось:
еслинет находить:
возвращатьсяИстинный
еще:
строка, столбец = найти
Как решить головоломку для каждой строки, столбца и сетки 3x3
Теперь, когда вы можете определить первое пустое место для решения, вам нужно попытаться найти подходящее число, чтобы заполнить это пространство и решить головоломку.
Использование рекурсии, вызовите функциюsolve() внутри себя, чтобы попробовать все возможные комбинации значений для всех других пробелов.
- Внутри функцииsolve() после нахождения первого пустого места прокручивайте каждое число от 1 до 9. Эти числа представляют собой возможные числа, которые могли бы заполнить нерешенное пространство:
для число в диапазон(1, 10): - Введите доску, возможное число и позицию пустой ячейки в новую функцию. Новая функция вернет true, если это допустимое число, которое может решить это пустое место. Если он действителен, назначьте этот номер ячейке на доске:
если is_valid (доска, число, (строка, столбец)):
доска[строка][столбец] = число - Создайте функцию is_valid() с соответствующими параметрами:
дефдействует(доска, номер, позиция): - Используйте эту функцию, чтобы проверить, не нарушает ли размещение числа в этой позиции какие-либо правила игры в судоку. Сначала проверьте, существует ли этот номер в строке или столбце ячейки:
для колонка в диапазон(9):
если доска[поз[0]][столбец] == число и поз[1] != столбец:
возвращатьсяЛОЖЬдля ряд в диапазон(9):
если доска[строка][позиция[1]] == число и поз[0] != строка:
возвращатьсяЛОЖЬ - Получите сетку 3x3, которой принадлежит ячейка. Вы можете сделать это, разделив позицию ячейки на три:
box_row = позиция [0] // 3
box_col = позиция[1] // 3 - Для каждой строки и столбца в этой сетке 3x3 проверьте, существует ли уже номер. Если это так, верните false:
для ряд в диапазон (box_row*3, box_row*3 + 3):
для колонка в диапазон (box_col*3, box_col*3 + 3):
если доска[строка][столбец] == число и (строка, столбец) != позиция:
возвращатьсяЛОЖЬ - Если сценарий достигает конца функции, это означает, что ни одно из правил судоку не сработало. Вернуть истину:
возвращатьсяИстинный - Функция is_valid() только проверяет правильность размещения числа, но это не означает, что это правильный ответ на общее решение. В функцииsolve() снова вызовите функциюsolve() с обновленной доской. Функцияsolve() может достичь состояния, в котором она больше не может использовать числа для заполнения пробелов. В этом случае вся функция возвращает false, сбрасывает эту конкретную ячейку обратно в 0 и выполняет возврат. Функцияsolve() возвращает true только тогда, когда скрипт может заполнить все пробелы:
для число в диапазон(1, 10):
если is_valid (доска, число, (строка, столбец)):
доска[строка][столбец] = число
если решить (доска):
возвращатьсяИстинный
доска[строка][столбец] = 0возвращатьсяЛОЖЬ - Чтобы начать решать головоломку, вызовите функциюsolve() с исходной доской в нижней части скрипта после объявления функцииsolve():
решить (доска) - Распечатайте окончательный результат:
Распечатать("Решено:")
print_board (доска) - В командной строке используйте команду python для повторного запуска скрипта. Просмотрите решенную головоломку, напечатанную на экране:
Python судоку.py
Создание игр с использованием Python
Судоку — это лишь одна из многих игр, которые вы можете создавать и решать с помощью Python. Вы можете использовать Python для создания различных других игр, таких как мешанина слов, текстовая приключенческая игра или цветная игра, и это лишь некоторые из них.
