Pozorne si preštudujte tento kód a objavte šikovný spôsob, ako využiť rekurziu na vyriešenie týchto zložitých sudoku.
Sudoku je populárna číselná hádanka, ktorá pozostáva z mriežky 9x9 s číslicami od 1 do 9. Puzzle obsahuje kombináciu čísel a niekoľko prázdnych miest, ktoré musíte vyplniť.
Pri vypĺňaní prázdnych miest by mal každý riadok, stĺpec a podmriežka 3x3 obsahovať všetky číslice od 1 do 9.
Jednoduchý skript Python vám môže pomôcť vyriešiť hádanku sudoku. Dokáže analyzovať všetky prázdne miesta na hracej ploche sudoku a nájsť možné číslo na vyplnenie každého prázdneho miesta.
Ako vytvoriť a zobraziť tabuľu sudoku
V Python skripte budete musieť použiť zoznam polí na uloženie hodnôt nevyriešeného sudoku.
Kód použitý v tomto projekte je dostupný v tomto Úložisko GitHub pod licenciou MIT.
- Vo vnútri nového skriptu Python s názvom sudoku.py uložte všetky hodnoty pre mriežku 9x9. Každý riadok a stĺpec predstavuje deväť čísel naprieč a nadol v hlavolame Sudoku. Pridajte 0, aby ste reprezentovali priestory, ktoré je potrebné vyriešiť:
doska = [
[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]
] - Vo vnútri novej funkcie s názvom print_board, použite cyklus for spracovať každý riadok v mriežke:
defprint_board(doska):
pre riadok v rozsah(9): - Ak chcete rozdeliť každý riadok na tretiny, skontrolujte, či je riadok deliteľný tromi, a pridajte riadok:
ak riadok % 3 == 0a riadok != 0:
vytlačiť ("- - - - - - - - - - - - - - ") - V každom riadku prevlečte každý stĺpec. Stĺpce môžete rozdeliť aj na tretiny tak, že skontrolujete, či je stĺpec deliteľný tromi:
pre kol v rozsah(9):
ak stĺpec % 3 == 0a col != 0:
vytlačiť (" | ", koniec ="") - Vytlačte číselnú hodnotu uloženú v mriežke. Ak je stĺpec posledným stĺpcom pre daný riadok, pridajte prerušovací riadok, aby sa nasledujúci riadok objavil na novom riadku:
ak col == 8:
vytlačiť (tabula[riadok][stĺpec])
inak:
print (str (board[row][col]) + " ", koniec ="") - Ak chcete vytlačiť tabuľu, zavolajte funkciu:
print_board (doska) - V príkazovom riadku prejdite do priečinka, do ktorého ste uložili skript python, napríklad:
cd Desktop - Na spustenie skriptu Sudoku použite príkaz python. Pozrite si puzzle vytlačené na obrazovke:
python sudoku.py
Ako identifikovať prázdne miesta na vyriešenie
Môžete prechádzať cez zoznamy a nájsť medzery, ktoré pozostávajú z nul. Tieto určujú, ktoré priestory je potrebné vyriešiť.
- V novej funkcii s názvom find_empty() prechádzajte každým riadkom a stĺpcom na doske:
defnájsť_prázdne(doska):
pre riadok v rozsah(9):
pre kol v rozsah(9): - Ak je hodnota aktuálnej bunky 0, vráťte aktuálnu pozíciu prázdnej bunky:
ak tabuľka[riadok][stĺpec] == 0:
vrátiť (riadok, stĺpec) - Ak skript dosiahne koniec funkcie, znamená to, že skript nenašiel žiadne bunky s hodnotou 0. V tomto prípade nič nevracajte:
vrátiťžiadne - V novej funkcii s názvom solve() použite funkciu find na nájdenie prvého prázdneho miesta na hracej ploche:
defvyriešiť(doska):
find = find_empty (doska) - Funkcia find_empty() vráti pozíciu bunky vo formáte n-tice, napríklad (0, 2). Uložte tieto hodnoty samostatne do riadok a kol premenných. V opačnom prípade vráťte hodnotu true, čím označíte, že nezostali žiadne prázdne miesta na vyriešenie:
aknie Nájsť:
vrátiťPravda
inak:
rad, col = nájsť
Ako vyriešiť hádanku pre každý riadok, stĺpec a mriežku 3x3
Teraz, keď môžete identifikovať prvé prázdne miesto na vyriešenie, budete sa musieť pokúsiť nájsť vhodné číslo, ktoré zaplní toto miesto a vyrieši hádanku.
Pomocou rekurzie, zavolajte v sebe funkciu solve(), aby ste vyskúšali všetky možné kombinácie hodnôt aj pre všetky ostatné priestory.
- Vo funkcii solve() po nájdení prvého prázdneho miesta precyklujte každé číslo od 1 do 9. Tieto čísla predstavujú možné čísla, ktoré by mohli vyplniť nevyriešený priestor:
pre č v rozsah(1, 10): - Zadajte tabuľu, možné číslo a pozíciu prázdnej bunky do novej funkcie. Nová funkcia vráti hodnotu true, ak je toto číslo platné číslo, ktoré dokáže vyriešiť toto prázdne miesto. Ak je platné, priraďte toto číslo bunke na tabuli:
ak is_valid (board, num, (riadok, stĺpec)):
tabuľka[riadok][stĺpec] = num - Vytvorte funkciu is_valid() so zodpovedajúcimi parametrami:
defje platné(doska, číslo, poz.): - Pomocou funkcie skontrolujte, či umiestnenie čísla na túto pozíciu neporušuje pravidlá hry Sudoku. Najprv skontrolujte, či toto číslo už existuje v riadku alebo stĺpci bunky:
pre kol v rozsah(9):
ak board[pos[0]][col] == num a poz [1] != col:
vrátiťNepravdivépre riadok v rozsah(9):
ak tabuľka[riadok][pos[1]] == num a poz [0] != riadok:
vrátiťNepravdivé - Získajte mriežku 3x3, do ktorej bunka patrí. Môžete to urobiť vydelením pozície bunky tromi:
box_row = poz [0] // 3
box_col = poz [1] // 3 - Pre každý riadok a stĺpec v tejto mriežke 3x3 skontrolujte, či už číslo existuje. Ak áno, vráťte false:
pre riadok v rozsah (box_row*3, box_row*3 + 3):
pre kol v rozsah (box_col*3, box_col*3 + 3):
ak tabuľka[riadok][kol] == num a (riadok, stĺpec) != poz:
vrátiťNepravdivé - Ak skript dosiahne koniec funkcie, znamená to, že žiadne z pravidiel sudoku zlyhalo. Vráti pravdu:
vrátiťPravda - Funkcia is_valid() iba kontroluje, či je umiestnenie čísla platné, ale to neznamená, že je to správna odpoveď na celkové riešenie. V rámci funkcie solve() znova zavolajte funkciu solve() s aktualizovanou doskou. Funkcia solve() môže dosiahnuť stav, kedy už nemôže použiť žiadne čísla na vyplnenie medzier. V tomto prípade celá funkcia vráti hodnotu false, obnoví konkrétnu bunku späť na 0 a vráti sa späť. Funkcia solve() vráti hodnotu true iba vtedy, keď skript dokáže vyplniť všetky medzery:
pre č v rozsah(1, 10):
ak is_valid (board, num, (riadok, stĺpec)):
tabuľka[riadok][stĺpec] = num
ak vyriešiť (doska):
vrátiťPravda
board[row][col] = 0vrátiťNepravdivé - Ak chcete začať riešiť hádanku, zavolajte funkciu solve() s pôvodnou tabuľou v spodnej časti skriptu po vyhlásení funkcie solve():
vyriešiť (doska) - Vytlačte konečný výsledok:
vytlačiť ("Vyriešené:")
print_board (doska) - Na príkazovom riadku použite príkaz python na opätovné spustenie skriptu. Pozrite si vyriešenú hádanku vytlačenú na obrazovke:
python sudoku.py
Vytváranie hier pomocou Pythonu
Sudoku je len jednou z mnohých hier, ktoré môžete vytvoriť a vyriešiť pomocou Pythonu. Python môžete použiť na vytváranie rôznych iných hier, ako je napríklad slovná zmes, textová adventúra alebo farebná hra, aby sme vymenovali len niektoré.
