Úloha 4.u4: Historie tahů piškvorek (4 b)

Zadáno v čísle 24.4.

Řešeno v čísle 24.6.

Zadání

Martin chce naprogramovat hru piškvorky na „piškvorkovnici“ $200\times 200$ políček. A zrovna si láme hlavu nad dílčí úlohou – chce ukládat historii hry, jak šly tahy od začátku po sobě, aby bylo možné vracet partii o libovolný počet tahů zpět.

Každý tah je jednoznačně určen svou $x$-ovou souřadnicí (hodnota 0 až 199), $y$-ovou souřadnicí (hodnota 0 až 199) a typem (buď křížek, nebo kolečko). Protože se hráči pravidelně střídají, tak víme-li číslo tahu, je už jasné, zda to byl křížek, nebo kolečko. Z pravidel piškvorek je pro nás dále důležité vědět, že hra končí, když se na ploše objeví 5 stejných symbolů vedle sebe v libovolném (i šikmém) směru.

Martin nechce plýtvat místem, a proto chce, aby stav hry, ze kterého půjde jednoznačně určit celá historie tahů, byl uložen v poli o velikosti $200\times 200$ bytů (byte má rozsah hodnot 0 až 255).

Jak to má udělat? Pomohou mu jiné číselné soustavy nebo šikovné kódování? Anebo to vůbec nejde?