Dnešní zadání bude poněkud těžší a obávám se, že je bez počítače prakticky neřešitelné. Dávám jej sem proto, že se jedná o velice zajímavý problém.
Někteří jej budete možná znát. Jedná se o tzv. Lloydovo bludiště.
Máte zadánu matici 23x23 čísel 0 až 9. (Tuto matici najdete v souboru ZADANI31.DAT). Vaše výchozí pozice je v jejím středu. Tam naleznete číslo 3 a to pro Vás znamená, že z něj můžete skočit kterýmkoliv z 8 směrů (tedy i úhlopříčně) právě o 3 čísla. Číslo, které naleznete tam, udává opět počet políček, které můžete opět libovolným směrem překonat.
Cílem je co nejkratším počtem skoků dospět na 0, přičemž musíte na ni dospět tak, abyste po cestě žádnou nepřeskakovali, čili PRÁVĚ na 0.
Samozřejmě nesmíte vyskočit ven z obrazu, ani na nepoužitá vykřížkovaná místa v rozích matice.
Přeji Vám mnoho úspěchů a očekávám na své adrese Vaše připomínky, náměty, odpovědi, případně listingy Vašich programů.
Jan Walla
! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! !!!Pozor!!! ! ! ! ! Protože se jedná o poměrně ! ! složitý problém, bude následovat ! ! drobná nápověda. Ti z vás, kteří se ! ! chcete s problémem "porvat" tak jak ! ! je, nečtěte dál! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! !
Nápověda:
Tady již nevystačíte s metodou zkoušení všech pokusů, protože těch je nekonečně mnoho. Počet skoků také velmi rychle roste. Pokud budete brát počet skoků k počtu kombinací zjistíte, že je v poměru n:8 na n-tou, (protože skákat můžete i zpět a přesto skočíte jinam, protože bude odlišný počet přeskočených políček). Pro 3 skoky je to 512 kombinací, pro čtyři 4 096 a pro deset skoků již 1 073 741 824 a nikdo vám nezaručí že řešení má 11 skoků.
Přesto existuje algoritmus, který Vám najde všechna i sebedelší řešení. Je nutné si všímat ne skoků, kterých je nekonečně mnoho, ale pouze čísel, kterých je konečný počet. Můžete mi věřit, že existují POUZE DVĚ DEVÍTISKOKOVÁ ŘEŠENÍ. Teď je jen nalézt...
Mnoho štěstí
Jan Walla