Rozwiąż dla mnie ten Alcazar

Ostatnio gram w grę o nazwie Alcazar. Jest to planszowa gra logiczna, w której Twoim celem jest wejście od jednych drzwi, przejście przez wszystkie kwadraty i wyjście przez inne drzwi. Jedyne zasady to:

Wejdź raz, zostaw raz;
Przejdź przez wszystkie kwadraty;
Nie przechodź przez kwadrat więcej niż raz

Poniższy obrazek pokazuje przykład planszy Alcazar i, po prawej stronie, rozwiązaną łamigłówkę (oczywiście jest to łatwa):

Więcej zagadek można znaleźć na stronie http://www.theincrediblecompany.com/try-alcazar i pobrać grę na PlayStore (PS: To nie jest reklama).

Mój problem polega na tym, że prawie skończyłem grę, z wyjątkiem jednego poziomu. Po prostu nie mogę znaleźć rozwiązania tego problemu. Wyzwaniem, które proponuję, jest: stworzyć algorytm, który rozwiąże każdy normalny poziom ^{1 do} rozwiązania ² Alcazar.

Oczywiście nie proszę nikogo, aby zbudował interpreter obrazu, aby odczytał obraz i rozwiązał zagadkę (czy jestem?). Więc przerobiłem powyższą łamigłówkę, używając postaci do rysowania w polu. Układanka i jej rozwiązanie wyglądałyby tak:

╔═══════╗         ╔═══════╗
║▒ ▒ ▒ ▒║         ║┌─┐ ┌─┐║
║     ║ ║         ║│ │ │║│║
╣▒ ▒ ▒║▒╠         ╣│ └─┘║└╠
║ ══╦═╩═╣         ║│══╦═╩═╣
║▒ ▒║▒ ▒║         ║└─┐║┌─┐║
║   ║   ║   ==>   ║  │║│ │║
╣▒ ▒║▒ ▒║         ╣┐ │║│ │║
║ ║ ║   ║         ║│║│║│ │║
╣▒║▒ ▒ ▒║         ╣│║└─┘ │║
║ ║     ║         ║│║    │║
║▒ ▒ ▒ ▒║         ║└─────┘║
╚═══════╝         ╚═══════╝

Na planszy powyżej ▒znajdują się komórki do wypełnienia.

Można zaobserwować, że pomiędzy komórkami jest pionowy i poziomy szpara. Jest tak, ponieważ musiałem wstawić spację między komórkami, aby dodać ściany. Oznacza to, że jedynymi ważnymi komórkami są komórki powyżej, poniżej, po lewej i po prawej stronie każdej komórki. Przekątne można usunąć bez utraty informacji. Na przykład na poniższej planszy oba przedstawiają tę samą łamigłówkę:

╔════╩╗         ═ ═ ╩ 
║▒ ▒ ▒║        ║▒ ▒ ▒║
║ ═══ ║           ═   
║▒ ▒ ▒║   ==   ║▒ ▒ ▒║
║     ║               
║▒ ▒ ▒║        ║▒ ▒ ▒║
╚╦════╝         ╦═ ══

Dotyczy to również rozwiązań. Oznacza to, że nie jest wymagane łączenie komórek:

╔════╩╗        ╔════╩╗        ╔════╩╗
║▒ ▒ ▒║        ║┌───┘║        ║┌ ─ ┘║
║ ═══ ║        ║│═══ ║        ║ ═══ ║
║▒ ▒ ▒║   ==   ║└───┐║   =>   ║└ ─ ┐║
║     ║        ║    │║        ║     ║
║▒ ▒ ▒║        ║┌───┘║        ║┌ ─ ┘║
╚╦════╝        ╚╦════╝        ╚╦════╝

W powyższym przykładzie oba rozwiązania oznaczają to samo.

Tak, przypadki testowe. Tutaj są:

Łamigłówka 1

╔════╩╗        ╔════╩╗
║▒ ▒ ▒║        ║┌ ─ ┘║
║ ═══ ║        ║ ═══ ║
║▒ ▒ ▒║   =>   ║└ ─ ┐║
║     ║        ║     ║
║▒ ▒ ▒║        ║┌ ─ ┘║
╚╦════╝        ╚╦════╝

Puzzle 2

╔═════╗        ╔═════╗
║▒ ▒ ▒║        ║┌ ─ ┐║
║   ║ ║        ║   ║ ║
╣▒ ▒║▒║        ╣└ ┐║│║
║ ║ ║ ║   =>   ║ ║ ║ ║
╣▒║▒ ▒╠        ╣┐║│ │╠
║ ║   ║        ║ ║   ║
║▒ ▒ ▒║        ║└ ┘ │║
╚════╦╝        ╚════╦╝

Puzzle 3

╔════╩══╗        ╔════╩══╗
║▒ ▒ ▒ ▒║        ║┌ ┐ └ ┐║
║ ║   ║ ║        ║ ║   ║ ║
╣▒║▒ ▒║▒╠        ╣┘║└ ┐║│╠
║ ╚══ ║ ║        ║ ╚══ ║ ║
║▒ ▒ ▒ ▒╠   =>   ║┌ ─ ┘ │╠
║   ═══ ║        ║   ═══ ║
║▒ ▒ ▒ ▒║        ║│ ┌ ┐ │║
║   ║   ║        ║   ║   ║
║▒ ▒║▒ ▒║        ║└ ┘║└ ┘║
╚═══╩═══╝        ╚═══╩═══╝

puzzle 4

╔═══════╗        ╔═══════╗
║▒ ▒ ▒ ▒║        ║┌ ┐ ┌ ┐║
║     ║ ║        ║     ║ ║
╣▒ ▒ ▒║▒╠        ╣│ └ ┘║└╠
║ ══╦═╩═╣        ║ ══╦═╩═╣
║▒ ▒║▒ ▒║        ║└ ┐║┌ ┐║
║   ║   ║   =>   ║   ║   ║
╣▒ ▒║▒ ▒║        ╣┐ │║│ │║
║ ║ ║   ║        ║ ║ ║   ║
╣▒║▒ ▒ ▒║        ╣│║└ ┘ │║
║ ║     ║        ║ ║     ║
║▒ ▒ ▒ ▒║        ║└ ─ ─ ┘║
╚═══════╝        ╚═══════╝

Puzzle 5

╔══╩══════╗        ╔══╩══════╗
║▒ ▒ ▒ ▒ ▒║        ║┌ ─ ┐ ┌ ┐║
║   ║     ║        ║   ║     ║
║▒ ▒║▒ ▒ ▒╠        ║└ ┐║└ ┘ │╠
║   ╠════ ║        ║   ╠════ ║
║▒ ▒║▒ ▒ ▒║   =>   ║┌ ┘║┌ ─ ┘║
║   ║     ║        ║   ║     ║
║▒ ▒║▒ ▒ ▒╠        ║└ ┐║└ ─ ─╠
║   ╠═════╣        ║   ╠═════╣
║▒ ▒║▒ ▒ ▒║        ║┌ ┘║┌ ─ ┐║
║   ║     ║        ║   ║     ║
║▒ ▒ ▒ ▒ ▒║        ║└ ─ ┘ ┌ ┘║
╚══╦═══╦══╝        ╚══╦═══╦══╝

Łamigłówka 6

╔═══════════╗        ╔═══════════╗
║▒ ▒ ▒ ▒ ▒ ▒║        ║┌ ┐ ┌ ┐ ┌ ┐║
║           ║        ║           ║
║▒ ▒ ▒ ▒ ▒ ▒║        ║│ └ ┘ └ ┘ │║
║       ═══ ║        ║       ═══ ║
║▒ ▒ ▒ ▒ ▒ ▒║        ║└ ┐ ┌ ─ ─ ┘║
║     ═══   ║        ║     ═══   ║
╣▒ ▒ ▒ ▒ ▒ ▒╠   =>   ╣┐ │ │ ┌ ┐ ┌╠
║           ║        ║           ║
║▒ ▒ ▒ ▒ ▒ ▒║        ║│ │ │ │ │ │║
║   ║   ║   ║        ║   ║   ║   ║
║▒ ▒║▒ ▒║▒ ▒║        ║│ │║│ │║│ │║
║   ║   ║   ║        ║   ║   ║   ║
║▒ ▒ ▒ ▒ ▒ ▒║        ║└ ┘ └ ┘ └ ┘║
╚═══════════╝        ╚═══════════╝

Puzzle 7

╔════╩════════╦╩╗        ╔════╩════════╦╩╗
║▒ ▒ ▒ ▒ ▒ ▒ ▒║▒║        ║┌ ─ ─ ─ ─ ─ ┐║│║
║ ║       ║   ║ ║        ║ ║       ║   ║ ║
║▒║▒ ▒ ▒ ▒║▒ ▒ ▒║        ║│║┌ ─ ─ ┐║┌ ┘ │║
║ ║ ║ ═══ ║     ║        ║ ║ ║ ═══ ║     ║
║▒ ▒║▒ ▒ ▒ ▒ ▒ ▒╠        ║│ │║┌ ─ ┘ └ ┐ │╠
║   ║           ║        ║   ║           ║
║▒ ▒ ▒ ▒ ▒ ▒ ▒ ▒║        ║│ │ └ ┐ ┌ ┐ └ ┘║
║     ║ ║     ══╣        ║     ║ ║     ══╣
║▒ ▒ ▒║▒║▒ ▒ ▒ ▒║        ║│ └ ┐║│║│ └ ─ ┐║
║     ║ ║       ║        ║     ║ ║       ║
║▒ ▒ ▒ ▒ ▒ ▒ ▒ ▒║        ║│ ┌ ┘ │ └ ┐ ┌ ┘║
║           ║ ══╣   =>   ║           ║ ══╣
║▒ ▒ ▒ ▒ ▒ ▒║▒ ▒║        ║└ ┘ ┌ ┘ ┌ ┘║└ ┐║
╠══       ║ ╚══ ║        ╠══       ║ ╚══ ║
║▒ ▒ ▒ ▒ ▒║▒ ▒ ▒║        ║┌ ┐ └ ┐ │║┌ ─ ┘║
║     ║ ║ ║     ║        ║     ║ ║ ║     ║
║▒ ▒ ▒║▒║▒ ▒ ▒ ▒║        ║│ └ ┐║│║│ └ ─ ┐║
║ ║   ║ ║ ╔══   ║        ║ ║   ║ ║ ╔══   ║
║▒║▒ ▒ ▒ ▒║▒ ▒ ▒║        ║│║┌ ┘ │ │║┌ ┐ │║
║ ║     ║ ║     ║        ║ ║     ║ ║     ║
║▒ ▒ ▒ ▒║▒ ▒ ▒ ▒║        ║│ └ ─ ┘║└ ┘ │ │║
║       ╚══     ║        ║       ╚══     ║
║▒ ▒ ▒ ▒ ▒ ▒ ▒ ▒║        ║└ ─ ─ ─ ─ ─ ┘ │║
╚════╦═╦═╦═════╦╝        ╚════╦═╦═╦═════╦╝

Puzzle 8 (Przepraszam, naprawdę nie mam rozwiązania tego)

╔══╩╦══╩═══╩═╩═╩═══╩╗
║▒ ▒║▒ ▒ ▒ ▒ ▒ ▒ ▒ ▒║
║   ║               ║
╣▒ ▒║▒ ▒ ▒ ▒ ▒ ▒ ▒ ▒║
║   ╚══ ╔══     ╔═══╣
╣▒ ▒ ▒ ▒║▒ ▒ ▒ ▒║▒ ▒╠
║       ║   ╔══ ║   ║
╣▒ ▒ ▒ ▒ ▒ ▒║▒ ▒ ▒ ▒╠
║           ║       ║
║▒ ▒ ▒ ▒ ▒ ▒ ▒ ▒ ▒ ▒╠
║           ║       ║
╣▒ ▒ ▒ ▒ ▒ ▒║▒ ▒ ▒ ▒╠
║   ╔═══╗   ╚══     ║
╣▒ ▒║▒ ▒║▒ ▒ ▒ ▒ ▒ ▒║
║   ║   ║           ║
╣▒ ▒║▒ ▒║▒ ▒ ▒ ▒ ▒ ▒╠
║ ══╝   ║       ╔══ ║
║▒ ▒ ▒ ▒║▒ ▒ ▒ ▒║▒ ▒║
║   ══╗ ╚══ ╔══ ║   ║
╣▒ ▒ ▒║▒ ▒ ▒║▒ ▒ ▒ ▒╠
║     ║     ║   ║   ║
╣▒ ▒ ▒ ▒ ▒ ▒ ▒ ▒║▒ ▒║
║   ═══   ══╗   ║   ║
╣▒ ▒ ▒ ▒ ▒ ▒║▒ ▒ ▒ ▒╠
╠══ ║       ║   ╔══ ║
║▒ ▒║▒ ▒ ▒ ▒ ▒ ▒║▒ ▒╠
║   ╚══ ║   ║   ║   ║
╣▒ ▒ ▒ ▒║▒ ▒║▒ ▒ ▒ ▒╠
║       ║   ║       ║
║▒ ▒ ▒ ▒ ▒ ▒ ▒ ▒ ▒ ▒║
╚══╦═══╦═══╦═╦═╦═╦═╦╝

Wejście

Dane wejściowe kodu mogą mieć dowolną reprezentację, pod warunkiem przestrzegania następujących reguł:

Musi to być wejście graficzne. Nie można na przykład odczytać listy współrzędnych.
Poziome ściany, pionowe ściany i drzwi muszą być wyraźne i muszą być wykonane z widocznego znaku (bez pustych znaków).
▒Można zastąpić spacjami. Po prostu użyłem innej postaci, aby je podświetlić.

Wydajność

Dane wyjściowe mogą mieć również dowolną reprezentację, pod warunkiem przestrzegania następujących reguł:

Musi to być wynik graficzny. Oznacza to, że ścieżkę można zobaczyć, patrząc na nią.
Zasada numer 1 zakłada, że znaki ścieżki są różne. Oznacza to, że będzie co najmniej 6 znaków ścieżki; poziomy, pionowy i narożniki.
Aby odpowiedź była poprawna, dane wyjściowe muszą być tej samej tablicy co dane wejściowe (oczywiście) z ▒wypełnionymi wszystkimi komórkami (w mojej reprezentacji ). Wypełnianie luk między komórkami jest opcjonalne.

Punktacja

To jest golf golfowy , więc wygrywa najkrótszy kod w bajtach.

¹ Istnieje kilka poziomów Alcazar, które mają opcjonalne komórki i tunele. Nie będą brane pod uwagę.

² Niektóre plansze Alcazar są niemożliwe.

code-golf ascii-art puzzle-solver Phelype Oleinik
źródło

Mój program nie znalazł rozwiązania zagadki 8. Czy jesteś pewien, że można ją rozwiązać? Może literówka?

edc65

@ edc65 to samo tutaj - brak rozwiązania dla # 8

ngn

Odpowiedzi:

Python 3 , 809 728 723 714 693 688 684 663 657 641 639 627 610 571 569 bajtów

Edycja: Zapisano 55 bajtów dzięki @Felipe Nardi Batista

Nie uruchamia ostatniego przypadku testowego w ciągu 60 sekund na TIO, ale mimo to powinien działać poprawnie. Zwraca listę współrzędnych ścieżki. Około 400 bajtów jest używanych do pobierania list danych z I / O.

A=enumerate
I,J="═║"
B=range
L=len
K=-1
Z=1,0
X=0,1
C=K,0
V=0,K
E=lambda a,b,p:(((a,b)in d)*L(p)==H*h)*p or max([E(q+a,w+b,p+[(q+a,w+b)])for q,w in y[a][b]if~-((q+a,w+b)in p)*-h>w+b>K<q+a<H]+[[]])
x=input().split("\n")
h=L(x[0])//2
H=L(x)//2
y=[[{C,Z,V,X}for i in B(h)]for j in B(H)]
d=[]
exec('d+=[(%s,i)for i,a in A(x[%s][1::2])if I<a]\nfor i,u in A(x[%s:%s:2]):\n d+=[(i,0)]*(J<u[0])+[(i,h-1)]*(J<u[K])\n for j,w in A(u[%s:%s:2]):\n  if"%s"==w:y[i][j]-={%s};y[i+%s][j+%s]-={%s}\n'*2%(0,*X,"",2,K,J,X,*X,V,H-1,K,2,K,1,"",I,Z,*Z,C))
print(max(E(*D,[D])for D in d))

Wypróbuj online!

Halvard Hummel
źródło

@HalvardHummel Cóż, przepraszam za złe sformułowanie wyzwania. Więc proponuję następujące. Wynik oblicza się poprzez pomnożenie liczby bajtów przez czas wykonania, więc zarówno czas wykonania, jak i liczba bajtów zostaną nagrodzone. Co myślisz?

Phelype Oleinik

@PhelypeOleinik Nie sądzę, że jest to bardzo dobry system punktacji. Trzymanie go w golfie Coed jest lepszym rozwiązaniem, ale jeśli naprawdę szukasz rozwiązania, jestem pewien, że można go zmodyfikować, aby był bardziej wydajny.

caird coinheringaahing

@cairdcoinheringaahing Rozumiem, że najbardziej eleganckim rozwiązaniem jest zachować taką, jaka jest. Ale algorytm, który zajmuje „dni lub nawet miesiące”, aby rozwiązać planszę 8 x 12, jest w jakiś sposób nieefektywny, nie sądzisz? Z mojego punktu widzenia algorytm, który rozwiązuje problem w krótszym czasie, powinien zostać nagrodzony, nawet jeśli jest nieco dłuższy.

Phelype Oleinik,

@PhelypeOleinik „Wydajność” kodu jest nieistotna. Rzuciłeś nam wyzwanie do napisania krótkiego kodu i to jest podstawa twojego wyzwania. Dodanie prędkości, z jaką program działa do miksu, komplikuje niepotrzebnie rzeczy i może być również wykorzystane do uzyskania absurdalnych wyników. Niestandardowe systemy oceniania zwykle nie działają. Jeśli chcesz mieć krótki kod, zrób pytanie w golfa. Jeśli chcesz szybkiego kodu, zadaj pytanie o najszybszym kodzie. Próbowanie ich mieszania nie jest dobrym pomysłem.

LyricLy

W twoim exec(...)ciągu znajduje się pięć nowych wierszy, reprezentowanych jako \n5 * 2 = 10 bajtów. Użycie potrójnego cudzysłowu dodałoby 4 bajty ( ...''...''...), a następnie usunęło 5 bajtów, ponieważ można by użyć rzeczywistych znaków nowej linii. W sumie może to zaoszczędzić jeden bajt.

Jonathan Frech,

APL (Dyalog Classic) , 319 bajtów

i←N⍴j←⍳1+n←×/N←⌊2÷⍨⍴a←⎕⋄e←↑⊃,/{(,~'#='∊⍨a[(⍵⌽⍳2)∘+¨2×⍳N+⍵=⍳2])/,2,/[⍵]⊃,[⍵]/n i n}¨⍳2
r←{e g c←⍵⋄d←+/j∘.=∊g⋄e⌿⍨←(≠/c[e])∧2>⌈/d[e]⋄n≡≢g:g⍪j/⍨d=1⋄0≡≢e:0⋄2>⌊/d+D←+/j∘.=,e:0⋄u←,¯1↑e←e[⍒⌊/D[e];]⋄e↓⍨←¯1⋄0≢r←∇e(g⍪u)(c-(-/c[u])×c=c[⊃u]):r⋄∇e g c}e(0↑e)j
a[1+2×⍳N]←' ??┌?─┐┬?└│├┘┴┤┼'[2⊥(↑(⊂i),¨¨{⊖∘⍉⍣⍵⊢n⍪¯1↓⌽∘⍉⍣⍵⊢i}¨⍳4)∊↓r⍪⌽r]
a

Wypróbuj online!

Wprowadzanie używa =#F7LJ<>^v.zamiast ═║╔╗╚╝╣╠╩╦▒, aby zmieścić się w klasycznym zestawie znaków .

Wszystkie przypadki testowe z wyjątkiem ostatniego przechodzą w ciągu kilku sekund.

Ostatni test trwa 47 minut na moim komputerze i nie daje rozwiązania.

Gdy powstała ścieżka korzysta z drzwi w pobliżu rogu, może być renderowana niepoprawnie (to tak, jakby szlak rozwidla się i przechodzi przez dodatkowe wyobrażone drzwi), ale nadal jest dostrzegalny i jednoznaczny.

ngn
źródło

Bardzo dobre! Jeśli mogę zapytać, jakiego podejścia używa Twój kod do rozwiązania? Wyczerpujące wyszukiwanie czy coś bardziej eleganckiego? Jak już powiedziałem, nie rozwiązałem ręcznie ostatniej układanki. Nie ma jasnego rozwiązania krok po kroku i wymaga nawet domysłów, aby znaleźć odpowiedzi. Ta łamigłówka jest zawarta w oryginalnej grze, ale może nie mieć rozwiązania, więc prawdopodobnie nie powinna być brana pod uwagę.

Phelype Oleinik,

@PhelypeOleinik Tak, to raczej mało wyszukane, ekshibicjonalne wyszukiwanie. Powodem, dla którego szybko znajduje istniejące rozwiązania, jest to, że najpierw próbuje bardziej prawdopodobnego przypadku (z vs bez pewnej krawędzi na wykresie - moja heurystyka to min stopni dwóch wierzchołków, niższe jest bardziej prawdopodobne). Powodem, dla którego działa okropnie w ostatnim przypadku, jest to, że i tak testuje wszystkie możliwości i przycina rekurencję tylko na oczywistych sprzecznościach. Wydaje się, że nie są znane dobre algorytmy ścieżki hamiltonowskiej, nawet w szczególnym przypadku grafów stopnia ograniczonego (≤4 sąsiadów).

ngn

JavaScript (ES6), 274 bajty

Wprowadzany jako ciąg wielowierszowy, każdy wiersz zakończony znakiem nowej linii. Drzwi są oznaczone znakiem „2”

Wyjście w postaci ciągu wielowierszowego ze ścieżką oznaczoną znakiem „1”, bardzo łatwo rozpoznawalnym.

Jest to wyszukiwanie głębokie , polegające na wypróbowaniu wszystkich ścieżek i cofnięciu się, gdy utkniesz. To wcale nie jest wydajne, ale może rozwiązać zagadki 1 .. 6 w mniej niż 1 minutę.

z=>(w=z.search`
`+1,t=(w-2)*(z.length/w-1)/4,z=[...z],R=(p,l,q)=>[1,-1,w,-w].some(d=>l<t?z[q=p+d]<1&z[q+d]<1&&(R(q+d,++z[q]+l)||--z[q]):z[p+d]>1&&--z[p+d],++z[p])||--z[p],z.some((c,i)=>-c&&(x=i%w,R(i<w?i+w:x?x>w-3?i-1:i-w:i+1,--z[i])||++z[i]*0))&&z.join``.replace(/0/g,' '))

Mniej golfa

z => (
  w = z.search`\n`+1, // board width and offset to next row
  t = (w-2)*(z.length/w-1)/4, // total size of board, number of cells that must be filled
  z = [...z], // convert string to array
  d = [1, -1, w, -w], // delta to next position in all directions
  // recursive search
  // given a current position, try to move in all directions
  // if the board is not full, look for an emoty cell
  // if the board is full, look for a door
  R = (p, // current position
       l, // fill level
       q  // parameter used as a local variable
      ) => (
        ++z[p], // mark current position
        // .some will terminate early if the called function returns true
        // in case of return true the recursive function returns all way up leaving the path marked
        // in case of return false we need to unmark path and backtrack
        d.some( d => // for each direction, offset in d
          l < t // check if board is full
          ? z[q=p+d] < 1 & z[q+d] < 1 // not full, try to advance 
            && (++z[q], // mark intermediate cell
                R(q+d, 1+l) // recursive call incrementing fill level
                || --z[q] // if R return false, backtrack: unmark intermediate cell
               )
          : z[p+d] > 1 && --z[p+d]
        ) // full, ok only if I find a door nearby
        || --z[p], // if some returns false, unmark and backtrak
  // look for doors and for each door call R 
  // when R returns true, stop and return the marked board
  // if R returns false for each door, no solution, return false
  z.some((c,i) => 
   -c && // if numeric and != 0
    (x = i%w,
     z[i]=1, // marking starting position (door)
     R(i<w ? i+w : x ? x > w-3 ? i-1 : i-w : i+1, 1)
     || (z[i] = 2, false) // if R returned false, unmark a return false
    ) 
  ) && z.join``.replace(/0/g,' ') 
)

Wewnątrz fragmentu testowego znajduje się rozwiązanie wykorzystujące DFS z pewnym ograniczeniem, które rozwiązuje zagadkę 7 w mniej niż minutę (na moim komputerze). Puzzle 8 nie ma rozwiązania. Ograniczenia:

Wszystkie puste komórki muszą być osiągalne z bieżącej komórki - pustej przestrzeni nie można dzielić na dwie części
Muszą być dostępne drzwi
Konfiguracji komórek nie można zbadać więcej niż jeden raz
Nie można pominąć komórki, która ma tylko jedną pustą sąsiednią komórkę

Test

Uwaga, układanka 7 znacznie przekracza limit czasu na wykonanie javascript w dowolnej przeglądarce (przy użyciu solvera Short i Slow)

Pokaż fragment kodu

var Short=
z=>(w=z.search`
`+1,t=(w-2)*(z.length/w-1)/4,z=[...z],R=(p,l,q)=>[1,-1,w,-w].some(d=>l<t?z[q=p+d]<1&z[q+d]<1&&(R(q+d,++z[q]+l)||--z[q]):z[p+d]>1&&--z[p+d],++z[p])||--z[p],z.some((c,i)=>-c&&(x=i%w,R(i<w?i+w:x?x>w-3?i-1:i-w:i+1,--z[i])||++z[i]*0))&&z.join``.replace(/0/g,' '))

var Fast=
b=>{
N=0
console.clear()
    F=(b,p,n) => D.reduce((n,d) => b[p+d] < 1 && b[p+d+d] < 1? F(b, p+d+d, n) : n, n+1, b[p]=1)
    A=(s, f, o, q, k)=>{
        D.map(d => b[s[1] + d] == 2 && (++o, q = s[1] + d));

        ++b[s[0]];
        if (++f < t)
        {
            if (o < m && !K[k=b.reduce((k,c,i)=>c>3?k+' '+i:k,s[1])] && F(b.slice(), s[K[k] = 1], f) >= t
                && R(D.reduce((n,d) =>(b[s[1] + d] == 0 && b[s[1] + d + d ] == 0 && n.push([s[1] + d, s[1] + d + d ]),n),[]),f,o,b[s[1]]=4))
                return 1;
        }
        else
        {
            b[s[1]] = 4;
            if (q) return b[q]++;
        }
        --b[s[0]]
        b[s[1]]=0
    }

    R=(s, f, o)=>{
        if (!s[1]) return A(s[0], f, o);
        var e, n, z=[];
        if (s.some(s =>(
                n = D.reduce( (n,d) => b[s[1]+d]>1 || (b[s[1]+d]<1 && b[s[1]+d+d]<1) ? n+1 : n, 0),
                n>2 ? !z.push(s) 
                : n>1 ? !z.unshift(s) 
                : n>0 && (e||(e=s,0))
        ))) return 0
        if (e) return A(e, f, o);
        return z.some(s => A(s, f, o))
    }

    w = b.search`\n` + 1;
    h = b.length / w;
    t = (w - 2) * (h - 1) / 4;
    D = [ 1, -1, w, -w ];
    b = [...b];
    K = {};
    s = [];
    b.forEach( (c,i) => -c ?  
        m = s.push( [i,i < w ? i + w : (x = i % w) > w - 3 ? i - 1 : x ? i - w : i + 1]):0
    )
    R(s, 0, 0);
    return b.join``.replace(/\d/g, c => ' oXOo'[c])
}

Out=(e,s)=>e.textContent = s

function Test(num)
{  
  var puzzle = document.getElementById('Z'+num).textContent;
  var solver = MF.checked ? Fast : Short
  Out(S,'...wait...')
  Out(T,'');
  
  var t0=performance.now()
  setTimeout(_=>(
    Out(S,solver(puzzle)),Out(T,((performance.now()-t0)/1000).toFixed(3)+' sec')
  ),10)
}

td { border: 1px solid #000; font-family: helvetica; font-size:12px; vertical-align: top; }
pre { line-height: 13px; }

Short and slow <input type='radio' value='S' name='M' id='MS'>
Long and faster <input type='radio' checked value='F'name ='M' id='MF'>
<table >
<tr>
<td id=T>Solution</td>
<td>Puzzle 1<input type='radio' name='T' onclick="Test(1)"></td>
<td>Puzzle 2<input type='radio' name='T' onclick="Test(2)"></td>
<td>Puzzle 3<input type='radio' name='T' onclick="Test(3)"></td>
<td>Puzzle 4<input type='radio' name='T' onclick="Test(4)"></td>
<td>Puzzle 5<input type='radio' name='T' onclick="Test(5)"></td>
<td>Puzzle 6<input type='radio' name='T' onclick="Test(6)"></td>
<td>Puzzle 7<input type='radio' name='T' onclick="Test(7)"></td>
</tr>
<tr>
<td><pre id=S></pre></td>
<td><pre id='Z1'>╔════2╗
║     ║
║ ═══ ║
║     ║
║     ║
║     ║
╚2════╝
</pre></td>
<td><pre id='Z2'>╔═════╗
║     ║
║   ║ ║
2   ║ ║
║ ║ ║ ║
2 ║   2
║ ║   ║
║     ║
╚════2╝
</pre></td>
<td><pre id='Z3'>╔════2══╗
║       ║
║ ║   ║ ║
2 ║   ║ 2
║ ╚══ ║ ║
║       2
║   ═══ ║
║       ║
║   ║   ║
║   ║   ║
╚═══╩═══╝
</pre></td>
<td><pre id='Z4'>╔═══════╗
║       ║
║     ║ ║
2     ║ 2
║ ══╦═╩═╣
║   ║   ║
║   ║   ║
2   ║   ║
║ ║ ║   ║
2 ║     ║
║ ║     ║
║       ║
╚═══════╝
</pre></td>
<td><pre id='Z5'>╔══2══════╗
║         ║
║   ║     ║
║   ║     2
║   ╠════ ║
║   ║     ║
║   ║     ║
║   ║     2
║   ╠═════╣
║   ║     ║
║   ║     ║
║         ║
╚══2═══2══╝
</pre></td>
<td><pre id='Z6'>╔═══════════╗
║           ║
║           ║
║           ║
║       ═══ ║
║           ║
║     ═══   ║
2           2
║           ║
║           ║
║   ║   ║   ║
║   ║   ║   ║
║   ║   ║   ║
║           ║
╚═══════════╝
</pre></td>
<td><pre id='Z7'>╔════2════════╦2╗
║             ║ ║
║ ║       ║   ║ ║
║ ║       ║     ║
║ ║ ║ ═══ ║     ║
║   ║           2
║   ║           ║
║               ║
║     ║ ║     ══╣
║     ║ ║       ║
║     ║ ║       ║
║               ║
║           ║ ══╣
║           ║   ║
╠══       ║ ╚══ ║
║         ║     ║
║     ║ ║ ║     ║
║     ║ ║       ║
║ ║   ║ ║ ╔══   ║
║ ║       ║     ║
║ ║     ║ ║     ║
║       ║       ║
║       ╚══     ║
║               ║
╚════2═2═2═════2╝
</pre></td>
</tr>
</table>

Rozwiń fragment kodu

edc65
źródło