Hráli jste někdy šachy? Pokud ano, tak už víte, že dáma je nejdůležitější figurou a že se může posunout o libovolný počet polí vertikálně, horizontálně nebo diagonálně. Pokud ne, nezoufejte: dnes se pouze naučíme, jak umístit 8 dam na šachovnici tak, aby se žádná dáma nemohla přesunout na pole obsazené jinou dámou. V šachovém žargonu říkáme, že dámy na sebe nebudou moci útočit. Jak toho dosáhneme? Použijeme backtracking.
Algoritmus backtrackingu nachází řešení problémů, ve kterých je třeba dodržet určitá omezení. Testuje všechna možná řešení, dokud nenajde to správné. Vyzkoušejme si příklad se čtyřmi dámami a malou šachovnicí. Začneme umístěním první dámy:
The second step is to place the second queen in a safe position, and then the third one:
At this point, there is no safe square on which we can place the last queen. So, we will change the position of the previous one. This is backtracking!
As you can see, there is no other square to safely place the third queen, different than the one we tried. Hence, this will require multiple backtracks. We will have to go back again and change the position of the second queen we placed.
We will have to perform multiple backtracks again to place all queens correctly and finally obtain a solution:
If you want to learn more how multiple backtracking steps inevitably lead you to a solution, check out Computer Science Distilled. Ukáže vám také mnoho dalších výpočetních strategií, které vám pomohou řešit zajímavé problémy!“
Teď, když víte, jak funguje backtracking, můžeme vyřešit problém 8 královen v plné velikosti. Níže je uvedena šachovnice, se kterou si můžete hrát, abyste si procvičili své dovednostia našli řešení. Začněte umístěním první dámy kliknutím na levé horní pole šachovnice. Uvidíte, že vámi umístěná dáma bude uvedena v seznamu „Aktuální dámy“.
Aktuální dámy
Nyní můžete umístit další dámu do pozice, která jim zabrání ve vzájemném útoku. Naše první dáma je na a8, druhou můžeme umístit například na c7. Pokračujte v umisťování dam, dokud na šachovnici nezbude žádné bezpečné pole. V tu chvíli je čas vrátit se zpět kliknutím na tlačítko „undo“. Tím zrušíte poslední umístěnou dámu a budete si moci vybrat jiné pole pro její umístění. Dámu můžete ze šachovnice odstranit také kliknutím přímo na ni.
Při hraní interaktivní hry můžete začít získávat cit pro backtracking. Jako pro lidi pro nás může být obtížné sledovat všechna předchozí umístění královen. V tom vám pomůže programování! Níže naleznete animaci vygenerovanou programem, který předvádí své bezchybné schopnosti zpětného sledování:
Pseudokód:
- Začneme umístěním první dámy na levé horní pole šachovnice.
- Pokud jsme umístili 8 dam, skončili jsme. V opačném případě je možné umístit další dámu na bezpečnou pozici?
- Pokud ano, označíme to jako součást řešení a vrátíme se k bodu 2.
- Pokud ne, změníme pozici předchozí dámy (backtracking) a vrátíme se k bodu 2.