Minesweeper ist ein beliebtes Puzzlespiel, bei dem Sie herausfinden müssen, welche Steine ​​"Minen" sind, ohne auf diese Steine ​​zu klicken. Stattdessen klicken Sie auf benachbarte Kacheln, um die Anzahl benachbarter Minen anzuzeigen. Ein Nachteil des Spiels ist, dass es möglich ist, in ein Szenario zu geraten, in dem es mehrere gültige Antworten gibt und Sie nur raten können. Nehmen Sie zum Beispiel die folgende Tafel:

1110
2*31
3*??
2*4?
112?

In diesem Format steht eine Zahl für die Anzahl benachbarter Minen, *eine bekannte Mine und ein "?" repräsentiert eine potentielle Mine. Das Unglückliche an diesem speziellen Rätsel ist, dass es vier verschiedene und gültige mögliche Lösungen gibt:

1110    1110    1110    1110    
2*31    2*31    2*31    2*31
3*4*    3*5*    3**2    3**1
2*42    2*4*    2*4*    2*42
112*    1121    1121    112*

Dies bedeutet, dass die Karte unlösbar ist . Hier ist ein Beispiel für eine lösbare Karte:

1121
1??*
12?*
0122

Diese Karte ist lösbar, da es nur eine mögliche gültige Lösung gibt:

1121
1*4*
12**
0122

Ihre Aufgabe ist es, entweder ein Programm oder eine Funktion zu schreiben, die ein gültiges Minensuchbrett benötigt und feststellt, ob es lösbar ist oder nicht. Mit "gültiges Minensuchbrett" meine ich, dass die Eingabe immer rechteckig ist, mindestens eine Lösung hat und keine ungültigen Zeichen enthält.

Ihre Eingabe kann ein Array von Zeichen, ein Array von Zeichenfolgen, eine Zeichenfolge mit Zeilenumbrüchen usw. sein. Die Ausgabe muss ein wahrer Wert sein, wenn sie lösbar ist, und ein falscher Wert, wenn dies nicht der Fall ist. Ich mache mir keine großen Sorgen um die Leistung, aber Ihre Lösung muss theoretisch für jede Eingabegröße funktionieren.

Wie üblich gelten Standardlücken und die kürzeste Lösung in Bytes gewinnt!

Beispiele:

Die folgenden Beispiele sind alle lösbar:

1121
1??*
12?*
0122

1110
1???
1110
0000

1110
3???
??20
*310

****
****
****
****

0000
0000
0000
0000

1100
*100
2321
??*2
13*2
1221
1*10
1110

1121
2*??
2*31
2220
1*10

Die folgenden Beispiele sind alle unlösbar:

1110
2*31
3*??
2*4?
112?

01??11*211
12??2323*1
1*33*2*210
12?2122321
13?3101**1
1***101221

1***
3*52
2*31
12??
02??
01??

00000111
000012*1
00001*21
22101110
**100111
?31123*1
?311**31
**113*20

GNU Prolog, 493 Bytes

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),[_]).

Ein zusätzliches Prädikat, das zum Testen nützlich sein kann (nicht Teil der Einreichung):

d([]).
d([H|T]):-format("~s~n",[H]),d(T).

Prolog ist definitiv die richtige Sprache, um diese Aufgabe aus praktischer Sicht zu lösen. Dieses Programm gibt so ziemlich nur die Regeln von Minesweeper an und lässt GNU Prologs Constraint Solver das Problem von dort aus lösen.

zund isind Utility-Funktionen ( zführt eine Art Fold-ähnliche Operation aus, jedoch mit Mengen von drei benachbarten Elementen anstelle von 2; itransponiert 3 Listen von n Elementen in eine Liste von n 3-Tupeln). Wir speichern eine Zelle intern als , wobei x 1 für eine Mine und 0 für eine Nichtmine ist und y die Anzahl benachbarter Minen ist; drückt diese Einschränkung an der Tafel aus. gilt für jede Reihe der Tafel; und prüft so , ob es sich um eine gültige Karte handelt.x/ycrcz(r,M)M

Leider ist das Eingabeformat, das erforderlich ist, um diese Funktion direkt auszuführen, nicht zumutbar. Daher musste ich auch einen Parser einbinden (der wahrscheinlich mehr Code als die eigentliche Regelengine enthält und die meiste Zeit mit dem Debuggen verbracht hat). Die Minesweeper-Regelengine hat ziemlich gut funktioniert Das erste Mal, aber der Parser war voll von Thinkos. qkonvertiert eine einzelne Zelle zwischen einem Zeichencode und unserem Format. konvertiert eine Zeile des Spielbretts (wobei eine Zelle, von der bekannt ist, dass sie keine Mine ist, jedoch eine unbekannte Anzahl benachbarter Minen aufweist, an jedem Rand der Zeile als Grenze verbleibt);x/ylpKonvertiert das gesamte Board (einschließlich des unteren Rahmens, jedoch ohne das obere). Alle diese Funktionen können entweder vorwärts oder rückwärts ausgeführt werden, wodurch das Board sowohl analysiert als auch schön gedruckt werden kann. (Es gibt einige nervige Bewegungen mit dem dritten Argument von p, das die Breite der Karte angibt. Dies liegt daran, dass Prolog keinen Matrixtyp hat. Wenn ich die Karte nicht auf rechteckig einschränke, wird das Programm ausgeführt eine Endlosschleife, in der immer breitere Ränder um das Brett gezogen werden.)

mist die Hauptauflösungsfunktion von Minesweeper. Es analysiert die Eingabezeichenfolge und generiert eine Platine mit einem korrekten Rand (indem das pmeiste der Platine in den rekursiven Fall konvertiert wird und dann der Basisfall direkt aufgerufen wird, um die obere Grenze zu generieren, die dieselbe Struktur wie die untere Grenze hat). Dann ruft esz(r,[R|M])um die Minesweeper Rules Engine auszuführen, die (mit diesem Aufrufmuster) zu einem Generator wird, der nur gültige Boards generiert. Zu diesem Zeitpunkt wird das Board immer noch als eine Reihe von Einschränkungen ausgedrückt, was für uns möglicherweise umständlich ist. wir könnten vielleicht eine einzige Reihe von Einschränkungen haben, die mehr als ein Board repräsentieren könnten. Außerdem haben wir noch nirgendwo angegeben, dass jedes Quadrat höchstens eine Mine enthält. Als solches müssen wir die Wellenform jedes Quadrats explizit "kollabieren", wobei es spezifisch entweder eine (einzelne) Mine oder eine Nichtmine sein muss, und der einfachste Weg, dies zu tun, besteht darin, es rückwärts durch den Parser zu laufen (die var(V)auf der q(63,V)case soll verhindern, dass das ?Gehäuse nach hinten läuft, und dass das Board durch das Deparsing vollständig erkannt wird). Zum Schluss geben wir das geparste Board abm; mSomit wird ein Generator, der eine teilweise unbekannte Karte nimmt und alle bekannten Karten in Übereinstimmung mit ihr erzeugt.

Das ist wirklich genug, um Minesweeper zu lösen, aber die Frage lautet ausdrücklich, ob es genau eine Lösung gibt, anstatt alle Lösungen zu finden. Als solches habe ich ein zusätzliches Prädikat geschrieben s, das den Generator einfach min eine Menge umwandelt und dann behauptet, dass die Menge genau ein Element enthält. Dies bedeutet, dass struthy ( yes) zurückgegeben wird, wenn es tatsächlich genau eine Lösung gibt, oder falsey ( no), wenn es mehr als eine oder weniger als eine gibt.

dist nicht Teil der Lösung und nicht im bytecount enthalten; Es ist eine Funktion zum Drucken einer Liste von Zeichenfolgen, als wäre es eine Matrix, die es ermöglicht, die von m(standardmäßig druckt GNU Prolog Zeichenfolgen als Liste von ASCII-Codes, da beide synonym behandelt werden; dieses Format) generierten Karten zu überprüfen ist ziemlich schwer zu lesen). Dies ist nützlich beim Testen oder wenn Sie meinen praktischen Minesweeper-Solver verwenden möchten (da ein Constraint-Solver verwendet wird, ist dieser sehr effizient).

Haskell, 193 169 168 Bytes

c '?'="*!"
c x=[x]
g x|t<-x>>" ",w<-length(words x!!0)+1=1==sum[1|p<-mapM c$t++x++t,and[sum[1|m<-[-1..1],n<-[j-w,j,j+w],p!!(m+n)=='*']==read[d]|(j,d)<-zip[0..]p,d>'/']]

Anwendungsbeispiel: g "1121 1??* 12?* 0122"-> True.

So funktioniert es: Liste aller möglichen Boards mit dem ?Ersetzten von entweder *oder !( !Mittel später ignorieren). Dies geschieht über mapM c, aber bevor wir dem Eingabe-String eine Reihe von Leerzeichen voranstellen und anhängen, damit unsere Indizierung nicht außerhalb des gültigen Bereichs liegt. Überprüfen Sie für jede dieser Karten, ob es sich um eine gültige Karte handelt, indem Sie alle Elemente (Index j) und, wenn es sich um eine Nummer ( d>'/') handelt, auch die Nachbarn (Index n, m) durchlaufen, *und vergleichen Sie sie mit der Nummer. Überprüfen Sie abschließend die Länge der Liste der gültigen Karten.

Mathematica, 214 192 190 180 176 174 168 165 Bytes

0&/@Cases[b="*";If[!FreeQ[#,q="?"],(x#0@MapAt[x&,#,#&@@#~Position~q])/@{b,0},BlockMap[If[#[[2,2]]==b,b,Count[#,b,2]]&,#~ArrayPad~1,{3,3},1]]&@#,#/.q->_,All]=={0}&

Enthält U + F4A1 (Privatgebrauch). Diese unbenannte Funktion findet alle möglichen Kombinationen für "?"(dh Ersetzen aller "?"s durch "*"oder 0) und prüft, ob es nur eine gültige Lösung gibt.

Erläuterung

b="*";

Stellen Sie bauf "*".

!FreeQ[#,q="?"]

Auf qden String setzen "?". Überprüfen Sie, ob es "?"in der Eingabe ist.

If[ ..., (x#0 ... ,0}, BlockMap[ ... ]]

Wenn True...

(x#0@MapAt[x&,#,#&@@#~Position~q])/@{b,0}

Ersetzen Sie das erste Vorkommen von q(= "?") durch b(= "*") oder 0(dh zwei Ausgänge) und wenden Sie die gesamte Funktion erneut an.

Wenn False...

#~ArrayPad~1

Füllen Sie den Eingang mit einer Schicht aus 0.

BlockMap[If[#[[2,2]]==b,b,Count[#,b,2]]&, ... ,{3,3},1]

Partitionieren Sie die Eingabe in 3 x 3 Matrizen mit Versatz 1. Wenden Sie für jede Partition eine Funktion so an, dass bei einem Mittelwert von b(= "*") die Ausgabe die b(= "*") und bei einem Mittelwert nicht die b(= "*") ist output ist die Anzahl b(= "*") in der Eingabe. Dieser Schritt wertet alle Nummernzellen neu aus.

Cases[ ... ,#/.q->_,All]

Suchen Sie aus allen Ergebnissen die Ergebnisse, die der Eingabe entsprechen

0&/@ ... =={0}

Überprüfen Sie, ob die Eingabe die Länge 1 hat.

Perl, 215 Bytes

213 Byte Code + -p0Flags (2 Byte).

/.*/;$c="@+";$_=A x$c."
$_".A x$c;s/^|$/A/mg;sub t{my($_)=@_;if(/\?/){for$i(0..8,"*"){t(s/\?/$i/r)}}else{$r=1;for$i(/\d/g){$r&=!/(...)[^V]{$c}(.$i.)[^V]{$c}(...)(??{"$1$2$3"=~y%*%%!=$i?"":R})/}$e+=$r}}t$_;$_=$e==1

Die Idee des Codes ist es, jede Möglichkeit zu testen und festzustellen, ob es eine einzige gibt, die zu einer vollständig gefüllten, gültigen Karte führt.

Besser lesbar sieht der Code so aus:

/.*/ ; $ c = "@ +" ; # Zähle die Größe einer Zeile. 
$ _ = A x $ c . "\ n $ _" . A x $ c ; # Fügen Sie am Anfang eine Zeile mit "A" und am Ende eine weitere Zeile mit "A" hinzu. 
s / ^ | $ / A / mg ; # Fügen Sie am Anfang und am Ende jeder Zeile ein "A" hinzu.                     

# Die Funktion, die das Problem tatsächlich löst. Sub t { my $ _ = pop ; # Holen Sie sich den Parameter, speichern Sie ihn in $ _ (Standardargument für Regex). Wenn ( / \? / ) { # kein unbekanntes Zeichen mehr ist, prüfen wir hier, ob die Karte gültig ist. 
        $ r = 1 ; # Wenn r == 1 am Ende ist, ist das Board gültig, andernfalls nicht
 
     
         # wenn es ein anderes unbekanntes Zeichen gibt. für $ i ( 0 . 8 , "*" ) { # versuchen , jede Möglichkeit 
            t ( s / \? / $ i / r ) # reccursive Anruf , wo die ersten unbekannten Zeichen ersetzt wurden } } else {
            
        
       
         für $ i ( / \ d / g ) { # für jede auf dem Board vorhandene Nummer entweder durch zu viel oder durch zu wenig Minen. # (wie es funktioniert: Magie!) 
         $ r & =! /(...)[^V{$c}(.$i.)[^V{$c}(...)(??{"$1$2$3"=~y%*%%! = $ i? "": R}) / } 
        $ e + = $ r # Erhöhe die Anzahl der gültigen Karten. } } 
t $ _ ;  
            
            
             
        
    
 # Vorherige Funktion 
aufrufen $ _ = $ e == 1 # Überprüft, ob es nur eine gültige Karte gibt ($ _ wird implizit mit dem Flag -p ausgegeben). 

Über den Regex in der Mitte:

/(...)[^V]{$c}(.$i.)[^V]{$c}(...)(??{"$1$2$3"=~y%*%%!=$i?"":R})/

Beachten Sie, dass [^V]nur für "ein beliebiges Zeichen, einschließlich \ n" steht.
Die Idee ist also: 3 Zeichen in einer Zeile, dann 3 in der nächsten (mit $iin der Mitte), dann 3 in der nächsten. Diese 3 Gruppen von 3 Zahlen sind dank ausgerichtet [^V]{$c}und die Zahl, an der wir interessiert sind, befindet sich in der Mitte.
Und dann "$1$2$3"=~y%*%%zählt die Anzahl der *(Bomben) unter den 9 Zeichen: wenn es aus anders ist $i, fügen wir eine leere Zeichenfolge übereinstimmen ( ""=> Instant - Matching, die regex true zurück), andernfalls zwingen wir nicht durch anzupassen versuchen R( was nicht in der Zeichenfolge sein kann).
Wenn der reguläre Ausdruck übereinstimmt, ist das Board nicht gültig, also setzen wir $rauf 0mit $r&=!/.../.
Und deshalb fügen wir einige hinzuAÜberall um jede Zeile: Wir müssen uns also nicht um Kanten kümmern. Fälle von Zahlen, die sich in der Nähe der Kanten des Bretts befinden: Sie haben ANachbarn, die keine Minen sind (natürlich könnte ungefähr jeder Saibling Arbeit haben). Ich wählte A).

Sie können das Programm folgendermaßen über die Befehlszeile ausführen:

perl -p0E '/.*/;$c="@+";$_=A x$c."\n$_".A x$c;s/^|$/A/mg;sub t{my($_)=@_;if(/\?/){for$i(0..8,"*"){t(s/\?/$i/r)}}else{$r=1;for$i(/\d/g){$r&=!/(...)[^V]{$c}(.$i.)[^V]{$c}(...)(??{"$1$2$3"=~y%*%%!=$i?"":R})/}$e+=$r}}t$_;$_=$e==1' <<< "1121
1??*
12?*
0122"

Die Komplexität könnte nicht schlimmer sein: O(m*9^n)Hier nbefindet sich die Anzahl der ?auf dem Board befindlichen mZellen und die Anzahl der Zellen auf dem Board (ohne die Komplexität des Regex in der Mitte zu berücksichtigen, was wahrscheinlich ziemlich schlimm ist). Auf meinem Computer funktioniert es ziemlich schnell für bis zu 4 ?und beginnt langsamer zu werden 5, dauert ein paar Minuten für 6 und ich habe keine größeren Zahlen versucht.

JavaScript (ES6), 221 229

g=>(a=>{for(s=i=1;~i;g.replace(x,c=>a[j++],z=j=0).replace(/\d/g,(c,p,g)=>([o=g.search`
`,-o,++o,-o,++o,-o,1,-1].map(d=>c-=g[p+d]=='*'),z|=c)),s-=!z)for(i=a.length;a[--i]='*?'[+(c=a[i]<'?')],c;);})(g.match(x=/\?/g)||[])|!s

Wenn erwartet wird, dass alle Eingaben gültig sind - also mit mindestens 1 Lösung -, kann ich ein Byte speichern, das sich s==1mit änderts<2

Weniger golfen

g=>{
  a = g.match(/\?/g) || []; // array of '?' in a
  s = 1; // counter of solutions
  for(i=0; ~i;) // loop to find all configurations of ? and *
  {
    // get next configuration
    for(i = a.length; a[--i] = '*?'[+( c = a[i] < '?')], c; );
    z = 0; // init at 0, must stay 0 if all cells count is ok
    g
    .replace(/\?/g,c=>a[j++],j=0) // put ? and * at right places
    .replace(/\d/g,(c,p,g)=>(
       // look for mines in all 8 directions
       // for each mine decrease c
       // if c ends at 0, then the count is ok
       [o=g.search`\n`,-o,++o,-o,++o,-o,1,-1].map(d=>c-=g[p+d]=='*'),
       z|=c // z stays at 0 if count is ok
    )) // check neighbour count
    s-=!z // if count ok for all cells, decrement number of solutions
  }
  return s==0 // true if exactly one solution found
}

Prüfung

F=
g=>(a=>{for(s=i=1;~i;g.replace(x,c=>a[j++],z=j=0).replace(/\d/g,(c,p,g)=>([o=g.search`
`,-o,++o,-o,++o,-o,1,-1].map(d=>c-=g[p+d]=='*'),z|=c)),s-=!z)for(i=a.length;a[--i]='*?'[+(c=a[i]<'?')],c;);})(g.match(x=/\?/g)||[])|!s

out=x=>O.textContent+=x+'\n'

Solvable=['1121\n1??*\n12?*\n0122'
,'1110\n1???\n1110\n0000'
,'1110\n3???\n??20\n*310'
,'****\n****\n****\n****'
,'0000\n0000\n0000\n0000'
,'1100\n*100\n2321\n??*2\n13*2\n1221\n1*10\n1110'
,'1121\n2*??\n2*31\n2220\n1*10']
Unsolvable=['1110\n2*31\n3*??\n2*4?\n112?'
,'01??11*211\n12??2323*1\n1*33*2*210\n12?2122321\n13?3101**1\n1***101221'
,'1***\n3*52\n2*31\n12??\n02??\n01??'
,'00000111\n000012*1\n00001*21\n22101110\n**100111\n?31123*1\n?311**31\n**113*20']
out('Solvable')
Solvable.forEach(t=>out(t+'\n'+F(t)+'\n'))
out('Unsolvable')
Unsolvable.forEach(t=>out(t+'\n'+F(t)+'\n'))

<pre id=O></pre>

JavaScript (Node.js) , 167 Byte

s=>g=(r=c='',[p,...q]=s,w)=>w?0:p?(g(r+0,q,p=='*')+g(r+1,q,1/p),c==1):c-=-![...s].some((p,i)=>p>' '&&[-1,1,-q,-1-q,-2-q,q,q+1,q+2].map(j=>p-=~~r[i+j])|p,q=s.search`
`)

Probieren Sie es online!

Obwohl "Eingabe immer rechteckig ist, mindestens eine Lösung hat", stimmt die falsche Stichprobe 3 nicht überein, daher benötige ich immer noch 1 Lösung, nicht <2 Lösung

s=>(        // p.s. Here "block" can also mean \n
  c=0,          // possible mine count
  g=(           // recursive
    r='',       // mine states
    [p,...q]=s, // known info to check possible state for a block
    w           // invert condition, stop if true
  )=>
    w?0:
      p?(       // for each block
        g(r+0,q,p=='*')+   // possibly not bomb if doesn't say so
        g(r+1,q,1/p),      // number/newline can't be bomb
        c==1               // only one bomb
      ):
        c-=-![...s].some(  // no block doesn't satisfy
          (p,i)=>
            p>' '&& // \n don't mean number
                    // other symbols turn into NaN when counting
            [-1,1,-q,-1-q,-2-q,q,q+1,q+2].map(j=>p-=~~r[i+j])
                    // subtract each neighbor, OOB = 0
            |p,     // difference between intended and actual
            q=s.search('\n') // how many blocks in a line
        )
)