Průvodce IB000 Matematické základy informatiky
Za oponou logické hry Antivirus
Na obrázku vidíte desku i s kameny zábavné logické hry Antivirus (koupit si ji můžete v mnohých hračkářstvích - ne, neberu za tuto reklamu žádné peníze). Tento bonusový úkol si hraje s touto skládačkou, ale jde "za oponu" ve smyslu, že po vás požaduje řešit a dokazovat problémy, které jsou dosti odlišné od základního úkolu této skládačky. Před samotným zadáním našich bonusových problémů se však musíme nejprve seznámit s danými pravidly skládačky Antivirus:
Předpokládáme, že uvedená anglická pravidla přečíst dokážete, takže jen stručně: Pohybovat s kameny (barevnými) můžete jen diagonálně, nic jiného, lze však pohybovat více než jedním kamenem souběžně. Navíc každý ze dvou speciálních bílých kamenů sedí na svém místě jako přilepený a nepohnete s ním (na obrázku nahoře jsou v dolních rozích, ale umístit je lze kamkoliv jinam na desku). Cílem skládačky je z počátečního rozmístění pohybovat barevnými kameny podle pravidel tak dlouho, až červený kámen (krátká "červená dvojka") vyjede z desky ven. Oproti uvedeným pravidlům pohybu ve skládačce uvádím ještě jedno metapravidlo: "červená dvojka" musí být vždy od začátku natočena ve směru '\' vzhledem k předpokladu, že deska má "díru" vlevo nahoře, kdežto "světlemodrá dvojka" musí být vždy ve směru '/' (mimo jiné z toho vyplývá, že "světlemodrá" nemůže z desky vyjet ven). Ostatní kameny lze na počátku vložit na desku natočené jakkoliv (pochopitelně to fyzicky jde jen v násobcích otočení o 90° oproti stavu na první fotce), ale při pohybu už se otáčet taky nemohou. A na závěr ještě fotka všech kamenů samostatně:
Vaše úkoly
Řešte kterýkoliv z níže uvedených úkolů, nemusíte odpovídat na vše. Je lepší krásně a do hloubky zpracovat odpověď na jednu z otázek, než na každou odpovídat jen povrchně.- Pro každé počáteční rozmístění dvou bílých pevných kamenů zjistěte, zda lze zbytek desky kompletně vyplnit barevnými kameny (nezapomeňte na správné natočení "červené" a "světlemodré"). Vzhledem k množství možností k probírání asi budete tento bod chtít řešit počítačem. Musíte však dodat důkaz, že váš algoritmus skutečně prošel vše a odpověděl správně.
- Určitě dokážete najít nějaké povolené počáteční rozmístění části kamenů na desku, ze kterého nelze žádnou posloupností platných tahů vysvobodit "červenou dvojku" (tj. vyjet s ní z desky ven). Toto rozestavení
může i nemusínově nesmí vůbec používat bílé pevné kameny. Aby to však nebylo tak jednoduché,jako že jenom bílým kamenem zablokujeme díru,tak navíc požadujeme, aby v tom povoleném počátečním rozmístění byl i jiný barevný kámen než červený a po odebrání kteréhokoliv barevného ne-červeného kamene již bylo možné vysvobodit "červenou". Fakt, že z počátečního rozmístění nelze vysvobodit "červenou", musíte také být schopni dokázat ručně zapsaným důkazem (ne jen počítačem). Najděte nějaké takové počáteční rozmístění, pro které ručně dokážete nemožnost vysvobození "červené" a ve kterém se použije co nejméně kamenů, a volitelně také takové, ve kterém se použije co nejvíce kamenů (v té "nejvíce" variantě můžete použít i bílé kameny). - Naopak pro mnohá jiná povolená počáteční rozmístění části kamenů na desku lze najít posloupnosti tahů, které vedou k vysvobození "červené". Určitě lze (aspoň hrubou silou) pro každý řešitelný začátek nalézt nejkratší posloupnost tahů, která vysvobodí "červenou". Vymyslete na toto hledání nejkratší posloupnosti vysvobozujících tahů algoritmus, dokažte jeho správnost a naprogramujte jej. Vašim úkolem je pak nalézt nějaké počáteční rozmístění, pro které lze "červenou" vysvobodit, ale pro které i ta nejkratší posloupnost vysvobozujících tahů je hooodně dlouhá (snažte se ji vynutit co nejdelší). Nepoužívejte však rozmístění, která jsou uvedená v návodu ke hře - vymýšlejte svoje.