Matematické Fórum

ouh sorry přepis tam mělo bějt běžná hned to edituju :-D

↑ Mr.Pinker: a taky to asi měla bejt šachovnice;)

Ahoj, to je typická úloha na prohledávání do šířky. Postupně budeš pomocí fronty zkoušet všechny možnosti na 1 tah, 2 tahy, 3 tahy, až jednou narazíš na situaci, kdy dojde k vynucenému matu. Avšak těch možností tahů bude velmi mnoho a program to nebude schopen spočítat, protože vynucený mat muže nastastat v nejhorším případě i po více než 20 tazích (40 půltazích).
I kdybych použil heuristiku, že moje věž se v každém tahu může posunout o jedno políčko blíže soupeřevu králi horizontálně nebo vertikálně (2 možnosti) a můj král buď vždy se může posunout za věž buď horizontálně nebo vertikálně (2 možnosti, tedy celkem 4 možnosti mých tahů). Soupeřův král se může posunout buď blíže k věži (pokud to lze - 1 tah), pokud to nejde, tak o jedno políčko dál od věže, horizontálním nebo vertikálním směrem (zde 2 možnosti, tedy max 2 možnosti). V každém tahu tedy proběhně maximálně 8 možností tahů bílého a černého dohromady, za 20 tahů to bude 8^20, tedy 2^60, což je pořád obrovské číslo a nelze v rozumném čase propočítat.

Jiné řešení nebo vylepšení mě nenapadá, ale zajímalo by mě, jak se to dá řešit efektivněji.

To je dosti málo informací. Už jen pro to že nevíme co má dělat král "kterého máme vymatovat". Jestli stojí na místě. Pomáhá ke své "vraždě". Nebo se snaží unikat. V posledním případě by to bylo asi nejsložitější, protože by jsi musel napsat pro něj "podle čeho" má kam utíkat. Takže čím lepší utíkací algoritmus by jsi napsal, tím složitější by byl algoritmus na jeho zastavení. A najítí počtu tahů delší.

Za předpokladu že stojí na místě, bylo by to asi nejsnazší. Já bych si pomocí souřadnice krále zjistil kde musí stát jiné figurky aby byl mat. Pak by stačilo "šachově"(kůň do L, atd.) procházet po šachovnici. Jakmile by byla figurka tam kde má být. Zastavil bych procházení. Při každém posunu zvětšit počet tahů.