GNU Prolog, 493 bajtów
z(_,[_,_]).
z(F,[A,B,C|T]):-call(F,A,B,C),z(F,[B,C|T]).
i([],[],[],[]).
i([H|A],[I|B],[J|C],[H-I-J|T]):-i(A,B,C,T).
c(A/_-B/_-C/_,D/_-_/T-E/_,F/_-G/_-H/_):-T#=A+B+C+D+E+F+G+H.
r(A,B,C):-i(A,B,C,L),z(c,L).
q(63,V):-var(V).
q(42,1/_).
q(X,0/Y):-Y#=X-48.
l([],[0/_]).
l([H|T],[E|U]):-q(H,E),l(T,U).
p([],[[0/_,0/_]],0).
p([],[[0/_|T]],N):-M#=N-1,p([],[T],M).
p([H|T],[[0/_|E]|U],N):-p(T,U,N),l(H,E).
m([H|A],B):-length(H,N),p([],[R],N),p([H|A],M,N),z(r,[R|M]),p(B,M,N).
s(A):-setof(B,m(A,B),[_]).
Dodatkowy predykat, który może być przydatny do testowania (nie stanowi części zgłoszenia):
d([]).
d([H|T]):-format("~s~n",[H]),d(T).
Prolog jest zdecydowanie właściwym językiem do rozwiązania tego zadania z praktycznego punktu widzenia. Ten program w zasadzie określa tylko zasady Saperów i umożliwia rozwiązanie problemu ograniczeniom GNU Prolog.
zi isą funkcjami użytkowymi ( zwykonuje rodzaj operacji składania, ale na zestawach trzech sąsiednich elementów zamiast 2; itransponuje 3 listy n elementów na listę n 3-krotek). Wewnętrznie przechowujemy komórkę jako , gdzie x wynosi 1 dla kopalni, a 0 dla kopalni, a y jest liczbą sąsiednich kopalń; wyraża to ograniczenie na tablicy. dotyczy każdego rzędu planszy; i dlatego sprawdza, czy jest to ważna tablica.x/ycrcz(r,M)M
Niestety format wejściowy wymagany do bezpośredniego działania tej funkcji jest nieuzasadniony, więc musiałem także dołączyć parser (który prawdopodobnie odpowiada za więcej kodu niż rzeczywisty silnik reguł i przez większość czasu spędzanego na debugowaniu; silnik reguł Saper właściwie działał za pierwszym razem, ale parser był pełen myśli). qkonwertuje pojedynczą komórkę między kodem znaków a naszym formatem. konwertuje jedną linię planszy (pozostawiając jedną komórkę, o której wiadomo, że nie jest kopalnią, ale z nieznaną liczbą sąsiadujących min, na każdej krawędzi linii jako granicę);x/ylpkonwertuje całą planszę (w tym dolną ramkę, ale wyłączając górną). Wszystkie te funkcje można uruchamiać do przodu lub do tyłu, dzięki czemu można zarówno analizować, jak i ładnie drukować tablicę. (Jest trochę denerwujące poruszanie się z trzecim argumentem do p, który określa szerokość tablicy; dzieje się tak, ponieważ Prolog nie ma typu matrycy, a jeśli nie ograniczę płytki do prostokątności, program przejdzie do nieskończona pętla próbująca stopniowo poszerzać granice wokół planszy.)
mjest główną funkcją rozwiązywania Saperów. Analizuje ciąg wejściowy, generując tablicę z poprawną ramką (poprzez użycie rekurencyjnego przypadku pdo konwersji większości tablicy, a następnie wywołanie skrzynki bazowej bezpośrednio w celu wygenerowania górnej granicy, która ma taką samą strukturę jak dolna granica). Potem dzwoniz(r,[R|M])do uruchomienia silnika reguł Saper, który (przy tym wzorcu wywołań) staje się generatorem generującym tylko prawidłowe tablice. W tym momencie tablica jest nadal wyrażana jako zestaw ograniczeń, co jest dla nas potencjalnie niezręczne; moglibyśmy mieć jeden zestaw ograniczeń, które mogłyby reprezentować więcej niż jedną tablicę. Ponadto nie określono jeszcze nigdzie, że każdy kwadrat zawiera co najwyżej jedną kopalnię. W związku z tym musimy wyraźnie „zwinąć kształt fali” każdego kwadratu, wymagając, aby była to konkretnie (pojedyncza) kopalnia lub kopalnia, a najłatwiejszym sposobem na to jest przepuszczenie go przez parser do tyłu ( var(V)na q(63,V)obudowa jest zaprojektowana w taki sposób, aby zapobiec ?przesuwaniu się obudowy do tyłu, a zatem odłożenie płyty wymusza jej pełną znajomość). Na koniec zwracamy przeanalizowaną tablicęm; mw ten sposób staje się generatorem, który bierze częściowo nieznaną płytkę i generuje wszystkie znane tablice z nią zgodne.
To naprawdę wystarczy, aby rozwiązać Saper, ale pytanie wyraźnie dotyczy sprawdzenia, czy istnieje dokładnie jedno rozwiązanie, zamiast znalezienia wszystkich rozwiązań. Jako taki napisałem dodatkowy predykat, sktóry po prostu przekształca generator mw zestaw, a następnie zapewnia, że zestaw ma dokładnie jeden element. Oznacza to, że szwróci prawdę ( yes), jeśli rzeczywiście istnieje dokładnie jedno rozwiązanie, lub falsey ( no), jeśli istnieje więcej niż jedno lub mniej niż jedno.
dnie jest częścią rozwiązania i nie jest uwzględniony w bajcie; jest to funkcja służąca do drukowania listy ciągów, tak jakby to była matryca, co umożliwia sprawdzenie wygenerowanych kart m(domyślnie GNU Prolog drukuje ciągi jako listę kodów ASCII, ponieważ traktuje oba synonimy; ten format jest dość trudny do odczytania). Jest przydatny podczas testowania lub jeśli chcesz używać go mjako praktycznego solvera Saperów (ponieważ używa solvera ograniczeń, jest bardzo wydajny).
2?nie ma rozwiązań, co oznacza, że nie może pochodzić z prawdziwej gry Saper. Dlatego nie jest uważany za „planszę