Schachbrett Labyrinth

14

Schachfiguren (Könige, Königinnen, Türme, Bischöfe und Ritter) und Bauern befinden sich auf einem Brett, jedoch nicht auf dem Feld a1 oder h8 . Deine Aufgabe ist es, von den leeren Feldern a1 zu den leeren Feldern h8 zu gelangen und dabei nur leere Felder zu durchqueren. Die Bewegungsregeln sind wie folgt:

  1. Sie können von einem beliebigen leeren Feld zu einem beliebigen leeren Feld daneben gehen (gleicher Rang, nächste oder vorherige Datei; oder gleiche Datei, nächster oder vorherige Rang).
  2. Sie können von einem beliebigen leeren Feld zu einem beliebigen leeren Feld diagonal daneben gehen (nächster oder vorhergehender Rang, nächste oder vorhergehende Datei), vorausgesetzt , die Catty-Corner-Felder enthalten entweder (a) zwei Bauern oder (b) Bauern / gegnerische Steine Farbe. (Zwei nicht bäuerliche Figuren oder eine nicht bäuerliche Figur und eine bäuerliche Figur derselben Farbe sind stark genug, um den Fortschritt über die Ecke zu verhindern, aber zwei Bauern sind es nicht; und Figuren mit entgegengesetzter Farbe funktionieren nicht.) Konzert, um dir den Weg zu versperren.) Zum Beispiel, wenn du auf bist c4 sind und d5 leer ist, können Sie damit fortfahren, vorausgesetzt, c5 und d4 enthalten Bauern oder Teile / Bauern mit entgegengesetzter Farbe. Im Abschnitt "Beispieldiagonalen" unten finden Sie Abbildungen.

Eingang

FEN Board Beschreibung. Das heißt: Die Eingabe ist eine Zeichenfolge, die eine Beschreibung von Rang 8 , einen Schrägstrich ( /), eine Beschreibung von Rang 7 , einen Schrägstrich, ... und eine Beschreibung von Rang 1 enthält . Die Beschreibung jedes Ranges umfasst Zahlen und Buchstaben von Datei a bis Datei h , wobei die Buchstaben Teile und Bauern bezeichnen (die schwarzen sind)p = Bauer, n= Ritter, b= Bischof, r= Turm, q= Dame, k= König und die weißen Einsen sind großgeschriebene Versionen desselben) und die Zahlen geben die aufeinanderfolgende Anzahl leerer Quadrate an. Zum Beispiel rnbqkbnr/pppppppp/8/8/4P3/8/PPPP1PPP/RNBQKBNist das Brett nach einem Lagenzug (Königspfand auf e4)) in einem Schachspiel.

a1 und h8 sind in der Eingabe leer; dh der erste Schrägstrich hat eine Ziffer vor sich und der letzte Schrägstrich hat eine Ziffer nach sich.

Ausgabe

Wahrheit oder Falschheit, die angibt, ob eine erfolgreiche Passage nach h8 möglich ist.

Wenn der Eingang keine gültige FEN-Board-Beschreibung ist (dh eine, die meiner obigen Erklärung entspricht) oder wenn a1 oder h8 belegt ist, kann der Ausgang alles oder nichts sein. (Mit anderen Worten: Sie können davon ausgehen, dass die Eingabe die oben genannten Anforderungen erfüllt.)

Wertung

Das ist Code Golf: Wenigste Bytes gewinnen.

Beispiel für Ein- und Ausgabe

Beachten Sie, dass Ihr Code für alle gültigen Eingaben funktionieren muss, nicht nur für die Beispiele.

Fügen Sie wnach jeder FEN ein Leerzeichen und ein hinzu , um es bei zu visualisieren http://www.dhtmlgoodies.com/scripts/chess-fen/chess-fen-3.html. (Beachten Sie, dass einige andere Online-FEN-Visualisierer keine im Schach illegalen Bretter zulassen, z. B. mit einem Bauern auf Rang 1 oder 8 , und daher nicht für unsere Zwecke verwendet werden können.)

Wahrheitsbeispiele

  • 8/8/8/8/8/8/8/8 - das leere Brett
  • 1p1Q4/2p1Q3/2p1Q3/2p1Q3/2p1Q3/2p1Q3/Q1p1Q3/1q3q2- Es gibt einen Pfad a1 , b2 , b3 , b4 , b5 , b6 , b7 , c8 , d7 ( nicht e8 , der blockiert ist, aber) d6 , d5 , d4 , d3 , d2 , d1 , e1 , f2 , f3 , f4 , f5 , f6 , f7 , f8 , g8 , h8
  • 8/8/KKKKK3/K3K3/K1K1p3/Kp1K4/K1KK4/2KK4 - Ein Beispiel, bei dem ein an einer Stelle blockiertes Quadrat später durchlaufen werden muss (um sicherzustellen, dass Sie keine Quadrate als unpassierbar festlegen).
  • K1k1K1K1/1K1k1K1k/K1K1k1K1/1k1K1K1k/K1k1K1k1/1K1k1k1K/K1K1k1K1/1k1k1K1k- Es gibt einen einzigen Weg (folgen Sie einfach Ihrer Nase: Es gibt nur ein Feld, zu dem Sie sich bei jedem Schritt bewegen können, es sei denn, Sie machen einen Schritt zurück). Dies ist auch ein Beispiel, bei dem ein Quadrat an einer Stelle blockiert ist, aber später benötigt wird

Falsche Beispiele

  • 6Q1/5N2/4Q3/3N4/2Q5/1N6/2Q5/1N6 - Jeder Wegeversuch muss durch zwei diagonal angeordnete gleichfarbige Teile verlaufen
  • N1q1K1P1/1R1b1p1n/r1B1B1Q1/1p1Q1p1b/B1P1R1N1/1B1P1Q1R/k1k1K1q1/1K1R1P1r- Der einzige Weg durch die Diagonale a8-h1 ist bei f2-g3 , aber das würde den Durchgang durch e1-d2 oder f2-e3 erfordern , die beide unmöglich sind.
  • 4Q3/4q3/4Q3/5Q2/6Q1/3QqP2/2Q5/1Q6
  • 4q3/4Q3/4q3/5q2/6q1/3qQp2/2q5/1q6

Beispieldiagonalen

Für den Fall, dass die obige Prosa unklar war, hier einige Bilder.

Passable Diagonalen

Bauern der gleichen Farbe Bauern in entgegengesetzten Farben Türme von entgegengesetzten Farben

Unüberwindliche Diagonalen

ein Turm und ein Bauer der gleichen Farbe gleichfarbige Türme

msh210
quelle
Es tut mir leid, ich bin mir nicht sicher, was die Stanadard-Golfregeln angeht: Was passiert, wenn Sie eine ungültige Zeichenfolge einfügen? Darf irgendein Verhalten auftreten?
Alex Bern
@alexberne Ich glaube das deckt es ab: "Dein Code muss für alle gültigen Eingaben funktionieren ".
Rainbolt
@alexberne habe ich bearbeitet. Ist es jetzt klar?
msh210
ja dank. Ich bin neu hier, also könnte es übliches Zeug für Golfer sein, aber für mich war es unklar :)
Alex Bern
Ich wollte mich nur für ein tolles Puzzle @ msh210 bedanken. Ich verstehe nicht, warum es keine weiteren Antworten gibt.
Joffan

Antworten:

6

VBA 668 666 633 622 548 510 489 435 331 322 319 315 Bytes

Function Z(F):Dim X(7,7):While Q<64:R=R+1:V=Asc(Mid(F,R))-48:If V>9 Then X(Q\8,Q Mod 8)=(3+(V\8=V/8))*Sgn(48-V):V=1
Q=Q-V*(V>0):Wend:X(7,0)=1:For W=0 To 2E3:Q=W Mod 8:P=W\8 Mod 8:For T=Q+(Q>0) To Q-(Q<7):For S=P+(P>0) To P-(P<7):If X(S,T)=0 Then X(S,T)=(1=X(P,Q))*(6>X(P,T)*X(S,Q))
Next S,T,W:Z=X(0,7):End Function

Das Lesen der Eingabezeichenfolge belegt bis zu 'Wend'. Ein netter Nebeneffekt: Sobald das Board [X] vollständig codiert ist, wird der Eingabe-String aufgegeben, sodass Sie am Ende eine Beschreibung hinterlassen können.

In der Boardcodierung sind die Bauern 2, die anderen 3, Schwarz ist negativ. Bauern werden durch 'P' & 'p' mit durch 8 teilbaren Zeichencodes erkannt.

'X (7,0) = 1', Einstellung a1 zugänglich, beginnen die Pfadprüfungen. Das Board wird wiederholt gescannt, wobei versucht wird, zugängliche Felder aus den bisher als zugänglich (1) markierten Feldern hinzuzufügen. Diagonaler Zugriff und Belegung werden in einem IF + -Logic-Calc überprüft, der früher in einer Funktion lebte, jetzt aber in verschachtelten Nachbarschleifen sitzt. Die diagonale Zugangskontrolle basiert auf dem Produkt der beiden Kitty-Eckquadrate, das nur bei 6 oder mehr Stücken dieselbe Farbe hat und bei mindestens einem Stück kein Bauer ist.

Tabellenkalkulation aufrufen; Gibt den Wert in X (0,7) - 1 zurück, wenn auf h8 zugegriffen werden kann, und 0, wenn nicht -, den Excel als wahr / falsch erkennt. = WENN (Z (C2), "ja", "nein")

Bildbeschreibung hier eingeben

Ich habe mich vielleicht von der Arbeit mit dem Code hinreißen lassen, also ist hier eine kommentierte halb-ungolfed Version:

Function MazeAssess(F)  'input string F (FEN)
Dim X(7, 7)             'size/clear the board; also, implicitly, Q = 0: R = 0
'Interpret string for 8 rows of chessboard
While Q < 64
    R = R + 1           ' next char
    V = Asc(Mid(F, R)) - 48  ' adjust so numerals are correct
    If V > 9 Then X(Q \ 8, Q Mod 8) = (3 + (V \ 8 = V / 8)) * Sgn(48 - V): V = 1 ' get piece type (2/3) and colour (+/-); set for single column step
    Q = Q - V * (V > 0) ' increment column (unless slash)
Wend
'Evaluate maze
X(7, 0) = 1             ' a1 is accessible
For W = 0 To 2000       ' 1920 = 30 passes x 8 rows x 8 columns, golfed to 2E3
    Q = W Mod 8         ' extracting column
    P = W \ 8 Mod 8     ' extracting row
    For T = Q + (Q > 0) To Q - (Q < 7)     ' loop on nearby columns Q-1 to Q+1 with edge awareness
        For S = P + (P > 0) To P - (P < 7) ' loop on nearby rows (as above)
            If X(S, T) = 0 Then X(S, T) = (1 = X(P, Q)) * (6 > X(P, T) * X(S, Q)) ' approve nearby empty squares if current square approved and access is possible
        Next 'S
    Next 'T
Next 'W
MazeAssess = X(0, 7)    ' report result for h8
End Function

Fortschrittsaufzeichungen

Edit 1: Der Code ist jetzt nicht mehr als 666-teuflisch :-D und hat seine Funktionen verloren; Ich fand einen kurzen Weg, sie zu schreiben, um den Overhead zu vermeiden.

Edit 2: Ein weiterer großer Sprung nach vorne, der die Arbeit des Entfernens der Inc / Dec-Funktionen, des Seufzens und der Verwendung einiger Globals effektiv beendet. Ich könnte endlich den Dreh raus bekommen ...

Die Codierung von Teilen und Quadraten wurde geändert. Keine Auswirkung auf die Codelänge.

Bearbeiten 3: Rückkehr von (gefälschten) Funktionen, Entfernen all dieser lästigen CallBytes und einiger anderer Verbesserungen.

Bearbeiten 4: Durchbrechen der großen 500, woohoo - die 3 For-Schleifen in 1 geglättet.

Bearbeiten 5: Jiminy Cricket, ein weiterer großer Tropfen, als ich die beiden Funktionen zusammengeschmissen habe - meine diagonale Zugriffskontrolle gilt immer für benachbarte Felder, also ...

Bearbeiten 6: Heilige Knabbereien, ein weiterer massiver Tropfen. Auf Wiedersehen zu externen Funktionen und damit zu Globals ... Ich bin auf weniger als die Hälfte der ursprünglich geposteten Länge gegangen ....

Bearbeiten 7: Ungolfed Version hinzufügen

Bearbeiten 8: Der Lesevorgang wurde für ein paar Dollar mehr überarbeitet

Bearbeiten 9: Drückte ein paar Ausdrücke für die letzten Blutstropfen

Edit 10: CompundNext Anweisung wirft einige Bytes ab


Bei Interesse sind Grafiken der Tafeln nach der Zugänglichkeitsanalyse (die Codenummern sind veraltet, aber ...) zugängliche Quadrate grün, nicht zugängliche Quadrate weiß und andere Farben sind Teile oder Bauern.

3 erfolgreiche Boards 3 blockierte Bretter

Ein paar Challenge Boards: h8 in beiden :

  • P1Pq2p1 / 1P1R1R1p / 1K2R1R1 / 1p1p1p2 / p1b1b1np / 1B1B1N1k / Q1P1P1N1 / 1r1r1n2 - 10 Durchgänge zum Lösen
  • P1P3r1 / 1P1R2r1 / 1N1R1N2 / 1P1P1P2 / 1n1p1ppp / 1B1B4 / 1b1pppp1 / 1P6 - ein Wicklungsweg
Joffan
quelle
1
Sehr schön und +1, aber: (1) Sind Sie sicher, dass 960 Schritte ausreichen? (2) Können Sie einige Bytes einsparen, indem Sie das Board verkehrt herum betrachten? If V>9 Then X(7-P,C)=würde ich denken (nicht dass ich VBA kenne) werden If V>9 Then X(P,C)=.
msh210
Eigentlich spart diese Technik das Initialisieren von P, also danke für die Frage :-). Und ja, ich bin sicher, dass 15 Pässe des Boards ausreichen. Ich habe ziemlich viel nachgesehen. Tatsächlich habe ich es nicht über 10 Pässe geschoben, aber 640 und 960 haben die gleiche Anzahl von Zeichen, also gehe ich auf Nummer sicher. ABER wenn ich das Board auf den Kopf stelle, KÖNNTE es mehr als 10 Durchgänge und vielleicht mehr als 15 dauern - es sei denn, ich habe das Board auch auf den Kopf gestellt, was einen Overhead hätte.
Joffan
@ msh210 1 zusätzliche Beobachtung - 15 Loops reichen gerade aus, um das gesamte Board zu analysieren, der schlimmste Fall, aber 10 Loops reichen aus, um den Status von h8 zu erhalten, also habe ich wirklich einen großen Spielraum. Der Grund dafür ist, dass das Auffinden von Pfaden in Bewertungsrichtung viel schneller vonstatten geht und die Anzahl der Zeilen und Spalten erhöht. Solange der Pfad nach oben oder rechts verläuft, wird er in einem einzigen Durchgang abgeschlossen. Wenn Sie nach links oder unten gehen, gelangen Sie mit jedem Durchgang nur einen Schritt weiter.
Joffan
@ msh210 Im Rahmen einer Überarbeitung des Lesevorgangs - die die Möglichkeit, einen Kommentar zum Ende des FEN-Strings zu hinterlassen, eng begrenzte - habe ich die von Ihnen vorgeschlagene Boardumkehr hinzugefügt. Einige Boards benötigen nun mehr als 15 Durchgänge (bis zu 17) Die Funktion wurde auf 30 Durchgänge der Platine erhöht.
Joffan
@Joffan Sie können 3 Bytes löschen, indem Sie alle Instanzen von [some non-letter character] Toto[some non-letter character]To
Taylor Scott
3

Matlab, 636 887 Bytes wie gespeichert (einschließlich Einrückung)

Diese Lösung ist nicht sonderlich gut, aber ich wollte weitermachen und sie aufstellen.

function[n] = h(x)
o=[];
for i=x
 b={blanks(str2num(i)),'K','k',i};o=[o b{~cellfun(@isempty,regexp(i,{'\d','[NBRQK]','[nbrqk]','p|P'}))}];
end
o=fliplr(reshape(o,8,8))
for i=1:64
 b=i-[-8,8,7,-1,-9,1,9,-7];
 if mod(i,8)==1
  b=b(1:5);
 elseif mod(i,8)==0
  b=b([1,2,6:8]);
 end
 b=b(b<65&b>0);c=o(b);dn=b(isspace(c)&ismember(b,i-[9,7,-9,-7]));
 for j=dn
  g=o(b(ismember(b,j-[-8,8,7,-1,-9,1,9,-7])));
  if ~isempty(regexp(g,'pk|kp|PK|KP|kk|KK'));c(b==j)='X';end;
 end
 Bc{i}=b(c==32);
end
n=Bc{1};
on=[];
while length(n)>length(on)
 on=n;
 for i=1:length(n)
  n=unique([n Bc{n(i)}]);
 end
end
any(n==64)
end

Liest eine Board-Zeichenfolge xwie oben angegeben und wandelt sie in die vollständigere Darstellung um o, findet dann alle Bewegungen (Diagrammkanten) zwischen Leerzeichen und stellt dann fest, welche Bewegungen möglich sind (nicht in gefüllte Leerzeichen), und stellt dann fest, welche möglichen Bewegungen " Tore "aus zwei Teilen, zwischen denen man hindurchgehen kann, und dann herausfindet, ob das Tor offen (Bauern, gegenüberliegende Farben) oder geschlossen (gleiche Farbe und mit einem Nichtbauern) ist. Dann sucht es nach Orten, die über Pfade vom unteren linken Quadrat aus erreichbar sind. Wenn ein Pfad Platz 64 erreichen kann, handelt es sich um eine Ja-Tafel.

sintax
quelle
1
Cool. Haben Sie es mit meinen Beispiel-FENs in der Frage getestet, um sicherzustellen, dass es für jedes das richtige Ergebnis zurückgibt? Auch, da dies eine Code-Golf- Frage ist, sollten Sie dies wirklich Golf spielen. Wenn nichts anderes, können Sie die Einrückung entfernen (oder statt vier Leerzeichen nur ein Leerzeichen oder einen Tabulator verwenden)? und / oder die Leerzeichen um das =s fallen lassen? (Ich weiß nicht, MATLAB: Vielleicht sind die unmöglich.)
msh210
Ja, und vielleicht mache ich das in meiner nächsten Pause. Ich habe es an all Ihren Beispielen getestet und an einigen. Sollte ich das irgendwie anzeigen?
sintax
Keine Ahnung; Ich habe mich nur gefragt.
msh210