Řešení hlavonamů v Prologu

Tato práce vznikla jako součást zápočtového programu na předmětu Neprocedurální programování, MFF UK. Jedná se o řešení konkrétního druhu hlavolamu v programovacím jazyce Prolog.

Posouvací puzzle na obecném grafu

Popis problému

Mějme neorientovaný graf na n vrcholech, každý jeho vrchol je označen číslem z $[0, n-1]$ a zároveň obsahuje číslo z $[0, n-1]$. Vrcholu obsahujícímu $0$ říkejme "prázdný" vrchol. Čísla se posouvají mezi vrcholy s použitím prázdného vrcholu, tj. obsahy vrcholů $U$ a $V$ můžeme prohodit, pokud je mezi nimi hrana a jeden z nich obsahuje $0$.

Puzzle je vyřešeno, když obsah každého vrcholu odpovídá jeho označení.
Ukázka: čirou náhodou jsem na internetu našel flash hru (výše), která přesně odpovídá popisovanému problému (autorem je Douglas Ensley, FlashAndMath.com). Do stejné kategorie hlavolamů patří např. Patnáctka.

Poznatky Wilsona (1974)

• řešení může existovat pouze pro vrcholově 2-souvislé grafy (nemá smysl zkoumat např. stromy)
• obecně neřešitelné pro graf theta₀ a kružnice
• bipartitní graf (např. mřížka) - řešitelné pouze pro sudé permutace, kterých je polovina
• v ostatních případech řešitelné vždy

Algoritmus řešení

Řešíme postupným zkoušením všech možností, ovšem pouze do stanovené hloubky. V každém kroku vybíráme další krok prioritně dle heuristiky.

Heuristika

Definujme domácí vzdálenost vrcholu $v$ jako délku nejkratší cesty od označení $v$ do obsahu $v$, tj, nejmenší počet tahů pro posun "domů". Definujme rozladěnost grafu jako součet domácích vzdáleností přes všechny vrcholy. Puzzle je vyřešené, jakmile rozladěnost klesne na 0. Pokud z vrcholu obsahujícího $0$ máme více možností tahu, vybíráme z nich prioritně podle vlivu na rozladěnost grafu. Nejdříve ty, které ji zmenší, pak ty, co ji nezmění, nakonec ty, co ji zvětší.

Poznámky k mé implementaci

• Pro hledání nejkratších cest používám Floyd-Warshallův algoritmus.
• Pro seřazení vrcholů dle priority používám Insertion sort.
• Nedovoluji v řešení cykly délky 2 (Např. když hledáme řešení dlouhé do 10 kroků a řešením je [1,2,3,4], potom [1,2,1,2,3,4] nevrátím, ačkoli to je řešení a má do 10 kroků.

Zdrojový kód v Prologu

Stručná dokumentace k programu

Vstup

Vstupní graf může být definován kdekoli v souboru s programem použitím predikátu

graph(Název, g(V, E)). 

Název je název grafu, pomoci kterého k němu budeme přistupovat V značí seznam vrcholů ve tvaru

[označení-obsah, označení-obsah, ...]

E značí seznam hran ve tvaru

[e(označení, označení), e(označení, označení), ...]

Ukázka

graph(ctverec,  g( [0-1, 1-2, 2-3, 3-0],  
                [e(0,1), e(1,2), e(2,3), e(3, 0)] ) ).

Což znamena takovýto graf

Spuštění výpočtu

Výpočet se spustí predikátem

solve(Název, Max-tahů).

• Název je název grafu v predikátu "graph"
• Max-tahů je horní hranice pro počet tahů ve výstupních řešeních.

Výstup

Výstupem programu jsou všechny posloupnosti tahů do stanovené délky řešící hlavolam. Jsou ve tvaru

[vrchol, vrchol, vrchol, ...]

vrchol je označení vrcholu, který si v daném kroku prohazuje obsah s nulovým vrcholem. Tahy jsou uspořádány zleva. Pokud vám dané řešení nevyhovuje, vygenerujte si další zmáčknutím ";". Pro náš výše uvedený graf je řešením toto

[2, 1, 0]

Stejně jako toto

[0, 1, 2, 3, 0, 1, 2, 3, 0]

Již vložené vsupy

Pro účely testování jsem do souboru přepsal některé grafy z výše uvedené URL a je možné se na ně dotazovat. Jsou to: graph1, graph3, graph5, graph7, graph9, graph11, graph17, graph30. Vyzkoušejte např. solve(graph1, 8).

Nejkratší řešení hlavolamů výše

Zadal jsem některé hlavolamy ze výše uvedené hry do programu a toto je výstup. Pokud chcete, můžete zadat zbytek a vypočítat si další hlavolamy, Patnáctky apod.

Číslo	Řešení
1	[2,4,3,2,1,0], [2,3,4,2,1,0], [1,2,4,3,2,0], [1,2,3,4,2,0]
3	[4,3,0,2,1,0], [4,3,0,1,2,0], [3,4,0,2,1,0], [3,4,0,1,2,0], [2,1,0,4,3,0], [2,1,0,3,4,0], [1,2,0,4,3,0], [1,2,0,3,4,0]
5	[3,2,1,0,3,4,1,0], [1,4,3,0,1,2,3,0]
7	[5,4,1,2,5,4,1,0], [5,2,1,4,5,2,1,0], [1,4,5,2,1,4,5,0], [1,2,5,4,1,2,5,0],
9	[1,5,2,3,4,5,6,0]
11	[5,4,1,2,5,4,1,0], [5,2,1,4,5,2,1,0], [1,4,5,2,1,4,5,0], [1,2,5,4,1,2,5,0]
17	[1,2,5,4,3,2,1,0,5,4,3,2,1,0]
30	[7,6,3,2,7,0,1,2,3,4,5,6,7,0,1,2,3,4,5,6,3,2,7,0]