Hlavní navigace

Futoshiki - klasicky

5. 11. 2021 0:00 Jiří Raška

Sdílet

  • 8. 11. 2021 21:07

    Hynek

    Místo "if from_index < self.size:" má být "if from_index < self.size ** 2:", jinak to někdy skončí moc brzo nedořešené.

    Například: [[0 0 0], [0 0<0], [0<0<0]], které má jednoznačné řešení [[2 3 1], [3 1 2], [1 2 3]].

    (Mimochodem u matice 2x2 stačí zadat jakoukoli jednu nerovnost a řešení je už jednoznačné, ale v tom případě by ten program ještě fungoval.)

  • 9. 11. 2021 14:46

    Hynek

    Oceňuji zjednodušený funkční kód na hranici rozsahu, jaký se hodí do článku, demonstrující použití backtrackingu, bez implementace dalších poznatků o řešené úloze. Šlo by to samozřejmě zrychlit sledováním, které číslo se vyskytuje pouze jednou v daném řádku nebo sloupci v množinách možných hodnot pro jednotlivá neznámá pole a hned ho dosadit. Dále je možné ořezávat množiny v sousedních polích, mezi kterými je nerovnost A<B, aniž by se hned musely hned zkoušet hodnoty pomocí backtrackingu. Vyloučí se všechny hodnoty A větší nebo rovny max(B) a stejně tak se vyloučí všechny hodnoty B menší nebo rovny max(A). Tímto způsobem lze hned určit v předchozím příkladu celý poslední řádek [1<2<3] dvojí opakovanou aplikací uvedených pravidel, respektive opakováním pravidel, pokud se zmenšil rozsah alespoň jedné množiny. Tím jsou pokryté všechny intuitivní strategie, které jsou mimochodem popsané v radách na https://www.futoshiki.org/ , kromě poslední strategie - naslepo či intuitivně zkoušet možnosti, které lze vyloučit, na což se už hodí backtracking. K němu je pak vhodné si pamatovat celý seznam množin možných hodnot pro jednotlivá pole, aby se po návratu z rekurze nemusely znovu provádět stejné iterace pro ořezání množin.

    Server Futoshiki obsahuje zřejmě předgenerovaných 10000 úloh pro každé z šesti velikostí 4x4 až 9x9 a čtyř obtížností. Zkusil jsem výše uvedená vylepšení na prvních 2000 úlohách nejvyšší obtížnosti s velikostí pole 8x8 a s ověřením, že pro každou úlohu existuje jen jedno řešení. Výsledky jsou: průměrná doba řešení byly 3 sekundy, přičemž 20% úloh bylo hotových do 0.1 sekundy, 50% do 0.5 sekundy, 90% do 7 sekund, 99% do 80 sekund a 0.75% úloh neřeším, protože trvaly déle než 100 sekund.

    Další možné zlepšení by zřejmě bylo vylučování řady slepých uliček nejdříve v jedné úrovni do šířky, než se bude postupovat do hloubky. Tím se totiž vyřeší problém například v případě většiny vstupních pravidel umístěných ve spodní polovině (viz ukázka s nerovnostmi pod diagonálou zobecnitelná na jakoukoli velikost), zatímco jednoduchý backtracking postupoval shora a příliš narůstal řešený stavový prostor. Krok hledání zřejmých slepých uliček má polynomiální složitost, zatímco backtracking už bude odpovídat něčemu podobného faktoriálu.

    O tomhle chci přemýšlet až po dalším dílu.