23.01.2017

Ahoj,
zadanie bolo nájsť najkratšie riešenie Loydovej 15tky, ale s rozmermi 3x3.

Bolo treba odlíšiť riešiteľný a neriešiteľný vstup.
Potom zadával nejaké vstupy (nepamätám si aké konkrétne):

1. počet krokov mal byť 31

2. 32

3. nemalo riešenie

Úspešnosť:
v riadnom čase to dali asi 3, na konci po predĺžení o 45 min. 5/17. Dvaja alebo traja mali ešte mail poslať.

Osobne som to vyriešil cez heuristiku (počet zle uložených políčok + počet ťahov). Načítal som si vstup a z neho generoval ďalšie stavy, ktoré som vkladal do prioritnej haldy a vyberal som stav s najmenším ohodnotením.

Ahoj,
správným řešením byla modifikace BFSka, kde vrcholy byly rozložení 3x3 mřížky. BFS se zastaví až dojde do mřizky {{1,2,3},{4,5,6},{7,8,0}}

Mřížka se dala třeba reprezentovat pomocí bitových operací/polynomu v unsignedlonglongu.
Tohle číslo se dá použít třeba do unordered_map na pamatování si tahů.
Pro zjednodušení se hodí napsat si funkce, které z čísla mřížky vyrobí neco jako array<array<int,3>,3> a naopak.
Zdroják jsem si zapomněl schovat.

Ahoj,

já jsem si taky zapomněl schovat zdroják :-D. Jak již bylo nicméně řečeno, stačí si to představit jako procházení grafem, pak kupříkladu BFS. Jednotlivé stavy jsem si ukládal jako stringy, pak je potřeba jen vyřešit, jak se z jednoho stavu dostat do druhého (existují čtyři hrany) a ukládat si, kde jsem už byl. (v mém případě to byl unsigned_map<std::string, std::pair<std::string, int> >, tedy jsem si pro každý stav ukládal jeho vzdálenost od počátku a jeho předchůdce v BFS stromě pro rekonstrukci cesty).

Mimochodem, ten člověk (Přemysl Čech) byl hodně hodný a na kód koukal jen tak letmo - alespoň u mě jen ověřil, že to má hlavu a patu (a je to napsané v C++ :-D) a dal to vyzkoušet na několika vstupech.

Pokud byste si to někdo chtěli nakódit, tak pro půlku vstupů to nejde (záleží na znaménku permutace), pro tenhle vstup do jde asi na 31 tahů (což je nejhorší případ). Mělo by to seběhnout tak do vteřiny (=>ve Visual Studiu v debug módu do minuty :-D).

8 6 7
2 5 4
3 1

Ahoj, narazil jsem na oficiální zadání, tak ho sem přidávám

Attachments:

• LoydPuzzle.pdf