Написать решатель потока ASP / Prolog / SAT

Flow Free - захватывающая игра на андроид, в которой вам нужно соединять пары элементов вместе через неперекрывающихся змей и заполнять всю сетку. Описание смотрите здесь:

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

У меня есть решение ASP (программирование набора ответов), которое представляет собой всего лишь пару правил, и я не думаю, что можно сформулировать то же решение почти так же кратко, как экземпляр SAT, но мне было бы интересно, чтобы меня опробовали.

Любой язык хорош, но я сомневаюсь, что это может быть сделано кратко без запуска какого-либо решателя, поэтому я назвал его ASP / Prolog / SAT

Победителем становится наименьшее количество персонажей.

Вы можете предположить, что проблема определена с использованием предикатов:

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

Кроме того, вход удовлетворяет

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

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

Предикат решения будет иметь вид

e(V,W,C).

Скажем, есть грань между V и W цвета C.

Края должны быть двунаправленными (одного цвета). Каждая вершина должна иметь ребра ровно одного цвета. Конечные точки имеют ровно одно ребро, все остальные вершины имеют ровно два ребра. Там нет петель, каждая змея должна прослеживаться до двух конечных точек.

Вот пример входных данных для тестирования (5x5 Уровень 2 в Regular Pack):

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).

И проверить вывод

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).

Также уровень 21 5x5 должен быть первой загадкой с более чем 1 решением (в частности, есть 9 решений, а не 40). Чтобы настроить уровень 21, установите последние несколько строк ввода в

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 (клинго), 180 байт

{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.

Я новичок в ASP, поэтому я был рад найти эту задачу, даже если она несколько старая. Было приятно видеть, что есть места для вариаций и возможность игры в гольф, что привело к ограничению моего понимания (я надеюсь, что это все еще правильно, кажется, что).

Вот прокомментированная версия:

% 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.

Я не знаю о различных решателях ASP, но я использовал clingo, который в debian содержится в пакете gringo.

Если у вас есть проблема в файле probи мой код в файле solve, позвоните clingo 0 prob solve. Для каждого решения вы получите список цветных ребер, которые он использует (и все остальные предикаты, если вы используете версию для гольфа, в которой отсутствует #showлиния). Если вам нужно только количество решений, добавьте эту опцию -q. Если вы хотите узнать, есть ли хотя бы одно решение, позвоните без 0.