Napisz solver przepływu ASP / Prolog / SAT

Flow Free to wciągająca gra na Androida, w której musisz łączyć pary elementów za pomocą nienakładających się węży i ​​wypełniać całą siatkę. Opis znajduje się tutaj:

https://play.google.com/store/apps/details?id=com.bigduckgames.flow&hl=en

Mam rozwiązanie ASP (programowanie zestawu odpowiedzi), które jest tylko kilkoma zasadami i nie sądzę, że możliwe jest sformułowanie tego samego rozwiązania prawie tak zwięźle jak instancja SAT, ale byłbym zainteresowany, aby udowodnić, że się mylę.

Każdy język jest w porządku, ale wątpię, że można to zrobić zwięźle bez uruchamiania jakiegoś solvera, dlatego nazwałem go ASP / Prolog / SAT

Zwycięzcą jest najmniej znaków.

Możesz założyć, że problem został zdefiniowany przy użyciu predykatów:

v(V). % A vertex

a(V,W). % V and W are adjacent

c(C). % A color

s(V,C). % V is an endpoint of color C

Ponadto dane wejściowe są satysfakcjonujące

a(W,V) :- a(V,W) % Adjacencies are bidirectional

2{s(V,C) : v(V)}2 :- c(C). % Every color has exactly two endpoints

Predykat rozwiązania będzie miał formę

e(V,W,C).

Mówiąc, że istnieje granica między V i W koloru C.

Krawędzie muszą być dwukierunkowe (tego samego koloru). Każdy wierzchołek musi mieć krawędzie do i z dokładnie jednego koloru. Punkty końcowe mają dokładnie jedną krawędź, wszystkie pozostałe wierzchołki mają dokładnie dwie krawędzie. Nie ma pętli, każdy wąż musi być identyfikowalny z powrotem do dwóch punktów końcowych.

Oto przykładowe dane wejściowe do przetestowania (5x5 poziom 2 w zwykłym pakiecie):

v(v11; v12; v13; v14; v15).
v(v21; v22; v23; v24; v25).
v(v31; v32; v33; v34; v35).
v(v41; v42; v43; v44; v45).
v(v51; v52; v53; v54; v55).

a(v11, v12).
a(v12, v13).
a(v13, v14).
a(v14, v15).
a(v12, v11).
a(v13, v12).
a(v14, v13).
a(v15, v14).
a(v11, v21).
a(v12, v22).
a(v13, v23).
a(v14, v24).
a(v15, v25).

a(v21, v22).
a(v22, v23).
a(v23, v24).
a(v24, v25).
a(v22, v21).
a(v23, v22).
a(v24, v23).
a(v25, v24).
a(v21, v31).
a(v22, v32).
a(v23, v33).
a(v24, v34).
a(v25, v35).
a(v21, v11).
a(v22, v12).
a(v23, v13).
a(v24, v14).
a(v25, v15).

a(v31, v32).
a(v32, v33).
a(v33, v34).
a(v34, v35).
a(v32, v31).
a(v33, v32).
a(v34, v33).
a(v35, v34).
a(v31, v41).
a(v32, v42).
a(v33, v43).
a(v34, v44).
a(v35, v45).
a(v31, v21).
a(v32, v22).
a(v33, v23).
a(v34, v24).
a(v35, v25).

a(v41, v42).
a(v42, v43).
a(v43, v44).
a(v44, v45).
a(v42, v41).
a(v43, v42).
a(v44, v43).
a(v45, v44).
a(v41, v51).
a(v42, v52).
a(v43, v53).
a(v44, v54).
a(v45, v55).
a(v41, v31).
a(v42, v32).
a(v43, v33).
a(v44, v34).
a(v45, v35).

a(v51, v52).
a(v52, v53).
a(v53, v54).
a(v54, v55).
a(v52, v51).
a(v53, v52).
a(v54, v53).
a(v55, v54).
a(v51, v41).
a(v52, v42).
a(v53, v43).
a(v54, v44).
a(v55, v45).

s(v11, yellow).
s(v45, yellow).
s(v41, blue).
s(v55, blue).
s(v51, red).
s(v43, red).
s(v42, green).
s(v33, green).

c(red; green; blue; yellow).

I przetestować wyjście

shouldbe(v33,v32,green).
shouldbe(v42,v32,green).
shouldbe(v43,v53,red).
shouldbe(v51,v52,red).
shouldbe(v55,v54,blue).
shouldbe(v41,v31,blue).
shouldbe(v45,v35,yellow).
shouldbe(v11,v12,yellow).
shouldbe(v12,v11,yellow).
shouldbe(v35,v45,yellow).
shouldbe(v31,v41,blue).
shouldbe(v54,v55,blue).
shouldbe(v52,v51,red).
shouldbe(v53,v43,red).
shouldbe(v32,v42,green).
shouldbe(v32,v33,green).
shouldbe(v53,v52,red).
shouldbe(v52,v53,red).
shouldbe(v54,v44,blue).
shouldbe(v31,v21,blue).
shouldbe(v35,v25,yellow).
shouldbe(v12,v13,yellow).
shouldbe(v13,v12,yellow).
shouldbe(v25,v35,yellow).
shouldbe(v21,v31,blue).
shouldbe(v44,v54,blue).
shouldbe(v44,v34,blue).
shouldbe(v21,v22,blue).
shouldbe(v25,v15,yellow).
shouldbe(v13,v14,yellow).
shouldbe(v14,v13,yellow).
shouldbe(v15,v25,yellow).
shouldbe(v22,v21,blue).
shouldbe(v34,v44,blue).
shouldbe(v34,v24,blue).
shouldbe(v22,v23,blue).
shouldbe(v15,v14,yellow).
shouldbe(v14,v15,yellow).
shouldbe(v23,v22,blue).
shouldbe(v24,v34,blue).
shouldbe(v24,v23,blue).
shouldbe(v23,v24,blue).

:-not e(V,W,C),shouldbe(V,W,C).
:-e(V,W,C),not shouldbe(V,W,C).

Również poziom 21 5x5 powinien być pierwszą łamigłówką z więcej niż 1 rozwiązaniem (konkretnie jest 9 rozwiązań, a nie 40) Aby ustawić poziom 21, ustaw kilka ostatnich wierszy wejścia na

s(v55, yellow).
s(v44, yellow).
s(v15, blue).
s(v45, blue).
s(v51, red).
s(v53, red).
s(v22, green).
s(v14, green).
s(v23, orange).
s(v43, orange).

c(red; green; blue; yellow; orange).

ASP (clingo), 180 bajtów

{e(V,W,C):a(V,W),c(C)}.r(V):-s(V,_).r(V):-r(W),e(W,V,_).o(V):-r(V),{e(V,W,_):v(W);s(V,_)}=2.:-e(V,_,C),e(V,_,D),C!=D.:-e(V,W,C),not e(W,V,C).:-v(V),not o(V).:-s(V,C),e(V,_,D),C!=D.

Jestem nowy w ASP, więc byłem podekscytowany znalezieniem tego zadania, nawet jeśli jest ono trochę stare. Miło było zobaczyć, że są miejsca na wariacje i możliwość gry w golfa, która doprowadziła do granic mojego zrozumienia (mam nadzieję, że nadal jest poprawna, wydaje się, że tak jest).

Oto skomentowana wersja:

% Select some edges e(V,W,C) s.t. V and W are adjacent and C is a color.
{e(V,W,C):a(V,W),c(C)}.

% Auxilary predicates:

% A vertex is reachable from an endpoint if
% it is an endpoint ...
r(V):-s(V,_).
% ... or it has an edge to it from a reachable vertex.
r(V):-r(W),e(W,V,_).

% A vertex is okay if it is reachable and either
% is an endpoint with one edge or is not an endpoint and has two edges.
% This is golfed to: the set of edges from V and endpoints V has
% cardinality 2.
o(V):-r(V),{e(V,W,_):v(W);s(V,_)}=2.

% Constraints:  We do not want ...

% edges from the same vertex with different colors:
:-e(V,_,C),e(V,_,D),C!=D.

% edges without their inverses:
:-e(V,W,C),not e(W,V,C).

% vertices that are not okay:
:-v(V),not o(V).

% edges from endpoints with the wrong color
:-s(V,C),e(V,_,D),C!=D.

% We're only interested in the e predicate:
#show e/3.

Nie wiem o różnych rozwiązaniach ASP, ale użyłem clingo, które w debianie jest zawarte w pakiecie gringo.

Jeśli masz problem w pliku probi mój kod w pliku solve, zadzwoń clingo 0 prob solve. Dla każdego rozwiązania otrzymasz listę kolorowych krawędzi, których używa (i wszystkie inne predykaty, jeśli używasz wersji golfowej, która nie ma #showlinii). Jeśli chcesz tylko liczbę rozwiązań, dodaj opcję -q. Jeśli chcesz tylko wiedzieć, czy istnieje co najmniej jedno rozwiązanie, zadzwoń bez 0.