Minesweeper Solver

34

Wir haben bereits Minesweeper-Felder erzeugt , aber jemand muss diese erzeugten Minen wirklich fegen, bevor PCG explodiert!

Ihre Aufgabe ist es, einen Minesweeper-Solver zu schreiben, der mit einer leicht modifizierten Version der akzeptierten Lösung von "Working Minesweeper" kompatibel ist (Aktionen werden durch Leerzeichen getrennt, um größere Felder zuzulassen).

Eingabe: Ein Minesweeper-Feld, Felder durch Leerzeichen getrennt. Die erste Zeile gibt die Gesamtzahl der Minen an.

  • x: Unberührt
  • !: Flagge
  • Ziffer: Anzahl der Minen um dieses Feld

Beispiel:

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

Ausgabe: Ihr nächster Schritt im Format action row column(beginnend bei Null)

Gültige Aktionen:

  • 0: Öffne es
  • 1: Platziere eine Flagge

Beispiel:

0 1 2

Regeln:

  • Sie schreiben ein vollständiges Programm, das ein einzelnes Feld als Eingabe (entweder STDIN oder Befehlszeilenargumente) und eine einzelne Aktion (STDOUT) ausgibt. Aus diesem Grund können Sie keine Status speichern, außer für !.
  • Ihre Wahl muss den besten Überlebenschancen folgen. (dh wenn es einen 100% sicheren Zug gibt, nimm ihn)
  • Das ist ; die kürzeste Lösung (in UTF-8 Bytes) gewinnt

Tests:

Diese Tests dienen dem Zweck, auf häufig auftretende eindeutige Situationen zu prüfen. Ihr Programm muss für jedes Testfeld geeignet sein.

Im:

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

Out (eine davon):

1 1 2
0 0 2
0 1 3

Im:

2
x x x
1 ! x
1 1 x

Out (eine davon):

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

Im:

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 (eine davon):

1 1 5
1 0 2

Im:

2
x x x
2 3 1
! 1 0

Out (eine davon):

0 0 1
1 0 0
1 0 2
TimWolla
quelle
Nett! 1) Vielleicht sollte jemand zum Testen ein Testgeschirr schreiben: Wenn ein Feld angegeben ist, druckt es jeden Schritt und ob das Programm gewinnt. Das Programm sollte auf Karten ohne Mehrdeutigkeit gewinnen. 2) Ich frage mich, ob jemand die Flag-Aktion verwenden wird. Scheint, als sollte es niemals notwendig sein.
Claudiu
Für den ersten Test. Warum sind Sie bewegen können 0 0 2oder 0 1 3. Ich kann nicht sehen, wie einer der beiden als sicher gelten würde. (Ich muss im Minensuchboot nicht gut genug sein ...)
FDinoff
1
Möglicherweise Foder Psieht besser aus Flagge als !:)
VisioN
1
@JonathanVanMatre Das Feld ist leer, aber es ist garantiert, dass Ihre erste Öffnung keine Mine ist, da die Minen nach dem ersten Klick platziert werden :)
TimWolla
2
Unterhaltsame Tatsache: Es gibt nur eine begrenzte Anzahl an verfügbaren Boards (zumindest in der XP-Version, die in der Wettbewerbsszene die kanonische ist). Das Spielfeld wird verschoben, wenn Sie auf die erste Stelle klicken, um sicherzustellen, dass Sie nicht auf eine Mine klicken. Ansonsten ist bereits entschieden, welches Spielfeld Sie verwenden.
Undergroundmonorail

Antworten:

17

Mathematica

Immer noch nicht golfen. Benötigt weitere Arbeiten an E / A-Formaten.

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}}
*)

Bearbeiten: Bonustrack

Ich habe mir einen interaktiven Spielplatz ausgedacht, der die Bombenwahrscheinlichkeiten berechnet, indem ich alle möglichen Lösungen für eine bestimmte Konfiguration berechnet habe:

Mathematica-Grafiken

Anleitung zum Testen ohne Mathematica:

  1. Laden Sie http://pastebin.com/asLC47BW herunter und speichern Sie es als * .CDF
  2. Laden Sie die kostenlose CDF-Umgebung von Wolfram Research unter https://www.wolfram.com/cdf-player/ herunter (keine kleine Datei).

Der Schieberegler ändert die Brettabmessungen. Dies ist nur ein skizzenhaftes Programm, nicht vollständig getestet. Bitte melden Sie alle Fehler. Ich habe die Funktion "Gesamtzahl der verfügbaren Bomben an Bord" nicht implementiert. Es wird unendlich angenommen.

Dr. belisarius
quelle