Minesweeper Solver

34

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.

W:

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

W:

2
x x x
1 ! x
1 1 x

Out (dowolny z tych):

0 0 0
0 0 1
0 1 2
0 2 2
1 0 2

W:

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

W:

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
1
Prawdopodobnie Flub Plepiej wygląda flaga niż !:)
VisioN
1
@JonathanVanMatre Pole jest puste, ale gwarantuje się, że twoje pierwsze otwarcie nie jest kopalnią, ponieważ kopalnie są umieszczane po pierwszym kliknięciu :)
TimWolla
2
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

Odpowiedzi:

17

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:

  1. Pobierz http://pastebin.com/asLC47BW i zapisz go jako * .CDF
  2. 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