Odpověď na názor

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.