Problém rozloženia 8 dám na šachovnici

Zhrnutie prednášky

Prednáška pokračuje témou backtrackingu a predstavuje riešenie problému ôsmich dám, ktoré sa majú rozmiestniť na šachovnici tak, aby sa navzájom neohrozovali. Kľúčovou myšlienkou je, že šachovnica nie je potrebná: každá dáma sa umiestňuje do vlastného riadka rekurzívnym volaním funkcie Hľadaj s cyklom for cez stĺpce. Obsadenosť stĺpcov sa eviduje v jednorozmernom poli a diagonály v dvoch poliach, kde sa využíva súčet a rozdiel súradníc (pri rozdiele s posunom o 7 kvôli indexovaniu od nuly v jazyku C). Ak sa dáma nedá položiť, algoritmus vráti značky späť a vráti sa o riadok vyššie. Program nájde dokopy 92 riešení, ktoré zapíše do súboru.

• - Úloha: rozložiť 8 dám na šachovnici 8×8 tak, aby sa navzájom neohrozovali.
• - Použitie backtrackingu: každá dáma rieši jeden riadok a pri neúspechu sa algoritmus vráti o riadok vyššie.
• - Šachovnica nie je na výpočet potrebná, slúži iba na vizualizáciu riešení.
• - Obsadené stĺpce sa evidujú v jednorozmernom poli, riadky ošetruje samotná rekurzia.
• - Diagonály sa kódujú do dvoch polí s 15 prvkami: index r+s a index r−s+7 (posun kvôli indexovaniu od nuly v C).
• - Funkcia Hľadaj najprv označí obsadenosť a položí dámu, rekurzívne sa zavolá pre ďalší riadok a potom značky odoberie.
• - Úloha má 92 riešení, ktoré program vypíše do súboru.

Zhrnutie pripravené s pomocou AI z prepisu videa.