Проучете внимателно този код и открийте умен начин да използвате рекурсия за решаване на тези трудни судоку пъзели.
Судоку е популярен пъзел с числа, който се състои от решетка 9x9 с цифри от 1 до 9. Пъзелът включва комбинация от числа и няколко празни места, които трябва да попълните.
Когато попълвате празните полета, всеки ред, колона и подрешетка 3x3 трябва да съдържат всички цифри от 1 до 9.
Един прост скрипт на Python може да ви помогне да решите судоку пъзел. Може да анализира всички празни места на дъската за судоку и да намери възможен номер за запълване на всяко празно място.
Как да създадете и покажете дъската за судоку
В рамките на скрипт на Python ще трябва да използвате списък от масиви, за да съхранявате стойностите на нерешения пъзел Sudoku.
Кодът, използван в този проект, е достъпен в това 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 цикъл за обработка на всеки ред в мрежата:
дефprint_board(дъска):
за ред в диапазон (9): - За да разделите всеки ред на трети, проверете дали редът се дели на три и добавете ред:
ако ред % 3 == 0и ред != 0:
печат ("- - - - - - - - - - - - - - ") - Във всеки ред превъртете всяка колона. Можете също така да разделите колони на трети, като проверите дали колоната се дели на три:
за полк в диапазон (9):
ако кол % 3 == 0и col != 0:
печат (" | ", край="") - Отпечатайте числовата стойност, съхранена в мрежата. Ако колоната е последната колона за този конкретен ред, добавете разделителна линия, така че следният ред да се появи на нов ред:
ако col == 8:
печат (дъска [ред][кола])
друго:
print (str (board[row][col]) + " ", край="") - Извикайте функцията за отпечатване на дъската:
print_board (дъска) - В командния ред отидете до папката, в която сте съхранили своя скрипт на Python, например:
cd работен плот - Използвайте командата python, за да стартирате вашия скрипт Sudoku. Вижте пъзела, отпечатан на екрана:
python sudoku.py
Как да идентифицирате празните пространства за решаване
Можете да преминете през списъците, за да намерите интервалите, които се състоят от 0. Те определят кои пространства трябва да бъдат решени.
- В нова функция, наречена find_empty(), преминете през всеки ред и колона на дъската:
дефfind_empty(дъска):
за ред в диапазон (9):
за полк в диапазон (9): - Ако стойността на текущата клетка е 0, върнете текущата позиция на празната клетка:
ако дъска [ред][кола] == 0:
връщане (ред, колона) - Ако скриптът достигне края на функцията, това означава, че скриптът не може да намери клетки със стойност 0. В този случай не връщайте нищо:
връщанеНито един - В нова функция, наречена solve(), използвайте функцията find, за да намерите първото празно място на дъската:
дефрешавам(дъска):
find = find_empty (дъска) - Функцията find_empty() връща позицията на клетката във формат на кортеж, например (0, 2). Запазете тези стойности отделно в ред и полк променливи. В противен случай върнете true, за да укажете, че няма останали празни места за решаване:
аконе намирам:
връщанеВярно
друго:
ред, колона = намиране
Как да решите пъзела за всеки ред, колона и мрежа 3x3
Сега, когато можете да идентифицирате първото празно място за решаване, ще трябва да опитате да намерите подходящо число, за да запълните това място и да решите пъзела.
Използване на рекурсия, извикайте функцията solve() в себе си, за да опитате всяка възможна комбинация от стойности и за всички останали пространства.
- Във функцията solve(), след намиране на първото празно място, преминете през всяко число от 1 до 9. Тези числа представляват възможните числа, които могат да запълнят нерешеното пространство:
за бр в диапазон (1, 10): - Въведете дъската, възможния номер и позицията на празната клетка в нова функция. Новата функция ще върне true, ако това число е валидно число, което може да реши това празно място. Ако е валиден, задайте този номер на клетката на дъската:
ако is_valid (дъска, брой, (ред, колона)):
дъска [ред][колона] = бр - Създайте функцията is_valid() със съответстващи параметри:
дефе валиден(табла, номер, позиция): - Използвайте функцията, за да проверите дали поставянето на числото в тази позиция нарушава правилата на играта Судоку. Първо проверете дали това число вече съществува в реда или колоната на клетката:
за полк в диапазон (9):
ако дъска[поз[0]][колона] == бр и поз[1] != col:
връщанеНевярноза ред в диапазон (9):
ако дъска[ред][поз[1]] == бр и поз[0] != ред:
връщанеНевярно - Вземете мрежата 3x3, към която принадлежи клетката. Можете да направите това, като разделите позицията на клетката на три:
box_row = pos[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 sudoku.py
Създаване на игри с помощта на Python
Судоку е само една от многото игри, които можете да създавате и решавате с Python. Можете да използвате Python за създаване на различни други игри, като бъркотия с думи, текстово базирана приключенска игра или цветна игра, за да назовем само няколко.
