6. diel - Backtracking - Lúštič Sudoku – Úvod

V predchádzajúcom článku, Backtracking - Prerezávanie , sme sa zoznámili s technikou prerezávania.

V dnešnom tutoriále o rekurzívnych algoritmoch začneme programovať lúštič Sudoku. Po niekoľkých teoretických lekciách si konečne zakódujeme a postupne vytvoríme program, v ktorom využijeme silu backtrackingu spojeného s prerezávaním.

Poznamenajme vopred, že výsledný program nebude (okrem prerezávania) nijako optimalizovaný na výkon. Jeho účelom bude predovšetkým demonštrácia algoritmu. Bude nám stačiť, keď vyriešené Sudoku obdržíme do jednej sekundy. O prípadných vylepšeniach budeme diskutovať, až celé Sudoku naprogramujeme.

Trieda Sudoku

Celé Sudoku budeme implementovať ako triedu Sudoku. Pozrime sa najskôr stručne na to, čo bude trieda obsahovať.

Trieda bude mať dvoch dátových členov:

• hraciPole – dvojrozmerné pole znakov o veľkosti 9 x 9, reprezentujúce hracie pole,
• vyreseno – premenná typu bool, indikujúca, či je Sudoku vyriešené.

Premenná hraciPole bude súkromná, lebo nie je dôvod vystavovať ju navonok. Premenná vyreseno bude naopak verejná – podľa jej hodnoty sa užívateľ dozvie, či bolo Sudoku vyriešené, resp. či má vôbec riešenie.

Naša trieda bude mať tieto verejné metódy:

 

...koniec náhľadu článku...
Pokračuj ďalej