Minesweeper Solver

Wygenerowaliśmy już pola Saper , ale ktoś naprawdę musi zamiatać wygenerowane miny, zanim PCG wybuchnie!

Twoim zadaniem jest napisanie Minesweeper Solver, który będzie kompatybilny z nieco zmodyfikowaną wersją zaakceptowanego rozwiązania „Working Sinesweeper” (akcje są oddzielone spacjami, aby pozwolić na większe pola).

Dane wejściowe: pole Saper, pola oddzielone spacjami. Pierwszy wiersz oznacza całkowitą liczbę min.

x: Nietknięty
!: Flaga
Cyfra: liczba min wokół tego pola

Przykład:

10
0 0 1 x x x x x
0 0 2 x x x x x
0 0 2 ! x x x x
0 0 1 2 x x x x
0 0 0 1 x x x x
1 1 0 2 x x x x
x 1 0 2 x x x x
1 1 0 1 x x x x

Wyjście: Twój następny krok w formacie action row column(od zera)

Prawidłowe działania:

0: Otwórz to
1: Umieść flagę

Przykład:

0 1 2

Zasady:

Piszesz kompletny program, który przyjmuje pojedyncze pole jako dane wejściowe (argumenty STDIN lub wiersz poleceń) i wyprowadza pojedyncze działanie (STDOUT). Dlatego nie można zapisywać stanów, z wyjątkiem !.
Twój wybór musi być zgodny z najlepszymi szansami na przetrwanie. (tzn. jeśli istnieje 100% bezpieczny ruch, weź go)
To jest golf golfowy ; najkrótsze rozwiązanie (w bajtach UTF-8) wygrywa

Testy:

Testy te służą do testowania typowych wyraźnych sytuacji; twój program musi działać dla każdego pola testowego.

4
x x x x
1 2 x x
0 1 2 x
0 0 1 x

Out (dowolny z tych):

1 1 2
0 0 2
0 1 3

2
x x x
1 ! x
1 1 x

Out (dowolny z tych):

10
x x x x x x x x
1 3 3 x x x x x
0 1 ! 3 3 4 x x
0 2 3 ! 2 3 x x
0 1 ! 2 2 ! x x

Out (dowolny z tych):

1 1 5
1 0 2

2
x x x
2 3 1
! 1 0

Out (dowolny z tych):

0 0 1
1 0 0
1 0 2

code-golf game minesweeper

— TimWolla
źródło

Miły! 1) Być może do przetestowania ktoś powinien napisać uprząż testową: dane pole wypisuje każdy wykonany krok i czy program wygrywa. Program powinien wygrywać na mapach bez żadnych dwuznaczności. 2) Zastanawiam się, czy ktokolwiek użyje akcji flagi. Wydaje się, że to nigdy nie powinno być konieczne.

— Claudiu

Do pierwszego testu. Dlaczego możesz przenieść się do 0 0 2lub 0 1 3. Nie rozumiem, jak którykolwiek z nich byłby uważany za bezpieczny. (Nie mogę być wystarczająco dobry w

— trałowcu

Prawdopodobnie Flub Plepiej wygląda flaga niż !:)

— VisioN

@JonathanVanMatre Pole jest puste, ale gwarantuje się, że twoje pierwsze otwarcie nie jest kopalnią, ponieważ kopalnie są umieszczane po pierwszym kliknięciu :)

— TimWolla

Ciekawostka: dostępna jest tylko ograniczona liczba plansz (przynajmniej w wersji XP, która jest kanoniczną na scenie konkursowej). Plansza jest przesuwana, gdy klikniesz pierwsze miejsce, aby upewnić się, że nie klikasz kopalni, ale poza tym już zdecydowano, z której planszy będziesz korzystać.

— undergroundmonorail

Matematyka

Wciąż nie grałem w golfa. Potrzebuje dodatkowej pracy nad formatami we / wy.

t = {{0, 0, 1, x, x, x, x, x}, {0, 0, 2, x, x, x, x, x}, {0, 0, 2, F, x, x, x, x}, 
     {0, 0, 1, 2, x, x, x, x}, {0, 0, 0, 1, x, x, x, x}, {1, 1, 0, 2, x, x, x, x}, 
     {x, 1, 0, 2, x, x, x, x}, {1, 1, 0, 1, x, x, x, x}};
(*Sqrt[2] is  1.5*)
c = Sequence; p = Position;
nums = p[t, _?NumberQ];
fx = Nearest[p[t, x]];
flagMinus[flag_] := If[Norm[# - flag] < 1.5, t[[c @@ #]]--] & /@ nums
flagMinus /@ p[t, F];
g@x_List := Tr[q[#] & /@ x]
eqs = MapIndexed[t[[c @@ (nums[[#2]][[1]])]] == g[#1] &, (fx[#, {8, 1.5}] & /@nums)];
vars = Union@Cases[eqs, _q, 4];
s = Solve[Join[eqs, Thread[0 <= vars < 2]], vars, Integers];
res = (Transpose@s)[[All, All, 2]];
i = 1; plays = Select[{i++, #[[1]], Equal @@ #} & /@ res, #[[3]] &];
Flatten /@ ({#[[2]] /. 1 -> F, List @@ vars[[#[[1]]]] - 1} & /@ plays)

(*
{{0, 0, 3}, {F, 1, 3}, {F, 2, 4}, {0, 3, 4}, {0, 4, 4}, 
 {F, 5, 4}, {F, 6, 0}, {F, 6, 4}, {0, 7, 4}}
*)

Edycja: Tor bonusowy

Stworzyłem interaktywny plac zabaw, który oblicza prawdopodobieństwo bombardowania, obliczając wszystkie możliwe rozwiązania dla danej konfiguracji:

Grafika matematyczna

Instrukcje testowania bez zainstalowanego Mathematica:

Pobierz http://pastebin.com/asLC47BW i zapisz go jako * .CDF
Pobierz bezpłatne środowisko CDF z Wolfram Research na https://www.wolfram.com/cdf-player/ (nie mały plik)

Suwak zmienia wymiary planszy. To tylko szkicowy program, nie w pełni przetestowany, zgłoś wszelkie błędy. Nie wdrożyłem funkcji „całkowitej liczby dostępnych bomb na pokładzie”. Zakłada się, że jest nieskończony.

— Dr Belizariusz
źródło