Tulis pemecah aliran ASP / Prolog / SAT

Flow Free adalah gim android yang adiktif di mana Anda harus menghubungkan pasangan elemen secara bersamaan melalui ular yang tidak tumpang tindih dan mengisi seluruh kotak. Untuk keterangannya, lihat di sini:

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

Saya punya solusi ASP (answer set programming) yang hanya beberapa aturan dan saya tidak berpikir itu mungkin untuk mengutarakan solusi yang sama hampir sama ringkasnya dengan contoh SAT, tapi saya tertarik untuk terbukti salah.

Bahasa apa pun baik-baik saja, tapi saya ragu itu bisa dilakukan secara ringkas tanpa menjalankan semacam solver yang mengapa saya menamakannya ASP / Prolog / SAT

Pemenang adalah karakter paling sedikit.

Anda dapat mengasumsikan masalah didefinisikan menggunakan predikat:

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

Selanjutnya, input memuaskan

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

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

Predikat solusi akan berupa

e(V,W,C).

Mengatakan ada batas antara V dan W warna C.

Tepi harus dua arah (dengan warna yang sama). Setiap dhuwur harus memiliki tepi ke dan darinya dengan tepat satu warna. Endpoint memiliki tepat satu tepi, semua simpul lainnya memiliki tepat dua tepi. Tidak ada loop, setiap ular harus dapat dilacak kembali ke dua titik akhir.

Berikut ini contoh input untuk mengujinya (5x5 Level 2 di Paket Reguler):

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

Dan untuk menguji output

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

Level 21 5x5 juga harus menjadi puzzle pertama dengan lebih dari 1 solusi (khusus, ada 9 solusi, bukan 40). Untuk mengatur level 21, atur beberapa baris terakhir input ke

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 byte

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

Saya baru mengenal ASP, jadi saya senang menemukan tugas ini, meskipun itu agak lama. Sungguh menyenangkan melihat ada tempat-tempat untuk variasi dan kesempatan untuk bermain golf yang mengarah ke batas pemahaman saya (saya harap itu masih benar, sepertinya).

Ini adalah versi yang dikomentari:

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

Saya tidak tahu tentang pemecah ASP yang berbeda, tetapi saya menggunakan clingo, yang dalam debian terkandung dalam paket gringo.

Jika Anda memiliki masalah dalam file probdan kode saya di file solve, hubungi clingo 0 prob solve. Untuk setiap solusi, Anda akan mendapatkan daftar tepi berwarna yang digunakannya (dan semua predikat lainnya jika Anda menggunakan versi golf yang tidak memiliki #showgaris). Jika Anda hanya menginginkan jumlah solusi, tambahkan opsi -q. Jika Anda hanya ingin tahu jika setidaknya ada satu solusi, teleponlah tanpa 0.