Las piezas de ajedrez (reyes, reinas, torres, obispos y caballeros) y los peones están en un tablero, pero no en el cuadrado a1 o h8 . Su tarea es viajar desde los cuadrados vacíos a1 hasta los cuadrados vacíos h8 , pasando solo por cuadrados vacíos. Las reglas de movimiento son las siguientes:

1. Puede pasar de cualquier cuadrado vacío a cualquier cuadrado vacío al lado (mismo rango, archivo siguiente o anterior; o mismo archivo, rango siguiente o anterior).
2. Puede pasar de cualquier cuadrado vacío a cualquier cuadrado vacío diagonalmente a su lado (rango siguiente o anterior, archivo siguiente o anterior), siempre que los cuadrados de esquina de gato contengan (a) dos peones o (b) peones / piezas opuestas color. (Dos piezas sin peón, o una pieza sin peón y un peón, del mismo color son lo suficientemente fuertes como para impedir su progreso en la esquina, pero dos peones no lo son; y las piezas / peones del color opuesto no funcionan en concierto para bloquear su camino.) Por ejemplo, si está en c4 y d5 está vacío, puede proceder a él siempre que c5 y d4 contengan peones o piezas / peones de color opuesto. Consulte la sección "Ejemplo de diagonales", a continuación, para ver imágenes.

Entrada

Descripción de la junta de FEN . Es decir: la entrada será una cadena que incluye una descripción del rango 8 , una barra inclinada ( /), una descripción del rango 7 , una barra inclinada, ... y una descripción del rango 1 . La descripción de cada rango comprende números y letras que van del archivo a al archivo h , donde las letras indican piezas y peones (los negros son p= peón, n= caballero, b= alfil, r= torre, q= reina, k= rey, y el blanco las versiones en mayúscula son iguales) y los números indican el número sucesivo de cuadrados vacíos. Por ejemplo, rnbqkbnr/pppppppp/8/8/4P3/8/PPPP1PPP/RNBQKBNes el tablero después de un movimiento de capas (peón del rey a e4) en un juego de ajedrez.

a1 y h8 estarán vacíos en la entrada; es decir, la primera barra tiene un dígito antes y la última barra tiene un dígito después.

Salida

Verdad o falsey, que indica si es posible el paso exitoso a h8 .

Si la entrada no es una descripción válida de la placa FEN (es decir, una que coincida con mi explicación anterior), o si a1 o h8 está ocupada, entonces la salida puede ser cualquier cosa o nada. (En otras palabras: puede suponer que la entrada cumple con los requisitos anteriores).

Puntuación

Este es el código de golf: menos bytes gana.

Ejemplo de entrada y salida

Tenga en cuenta que su código debe funcionar para todas las entradas válidas, no solo para los ejemplos.

Agregue un espacio y un wdespués de cada FEN para visualizarlo en http://www.dhtmlgoodies.com/scripts/chess-fen/chess-fen-3.html. (Tenga en cuenta que algunos otros visualizadores FEN en línea no permitirán un tablero que sea ilegal en el ajedrez, por ejemplo, con un peón en el rango 1 u 8 , por lo que no se puede usar para nuestros propósitos).

Ejemplos de verdad

• 8/8/8/8/8/8/8/8 - el tablero vacío
• 1p1Q4/2p1Q3/2p1Q3/2p1Q3/2p1Q3/2p1Q3/Q1p1Q3/1q3q2- hay una ruta a1 , b2 , b3 , b4 , b5 , b6 , b7 , c8 , d7 , ( no e8 , que está bloqueada, pero) d6 , d5 , d4 , d3 , d2 , d1 , e1 , f2 , f3 , f4 , f5 , f6 , f7 , f8 , g8 , h8
• 8/8/KKKKK3/K3K3/K1K1p3/Kp1K4/K1KK4/2KK4 - un ejemplo donde un cuadrado que está bloqueado en un punto debe pasarse más tarde (para asegurarse de que no establezca cuadrados como intransitables)
• K1k1K1K1/1K1k1K1k/K1K1k1K1/1k1K1K1k/K1k1K1k1/1K1k1k1K/K1K1k1K1/1k1k1K1k- hay un solo camino a través (solo sigue tu nariz: solo hay un cuadrado para moverte en cada paso, a menos que des un paso hacia atrás); Este también es un ejemplo en el que un cuadrado está bloqueado en un punto pero es necesario más tarde

Ejemplos de Falsey

• 6Q1/5N2/4Q3/3N4/2Q5/1N6/2Q5/1N6 - cualquier intento de un camino tendrá que pasar a través de dos piezas del mismo color situadas en diagonal
• N1q1K1P1/1R1b1p1n/r1B1B1Q1/1p1Q1p1b/B1P1R1N1/1B1P1Q1R/k1k1K1q1/1K1R1P1r- la única forma de atravesar la diagonal a8-h1 es en f2-g3 , pero eso requeriría pasar a través de e1-d2 o f2-e3 , que son imposibles.
• 4Q3/4q3/4Q3/5Q2/6Q1/3QqP2/2Q5/1Q6
• 4q3/4Q3/4q3/5q2/6q1/3qQp2/2q5/1q6

Diagonales de ejemplo

En caso de que la prosa anterior no estuviera clara, aquí hay algunas fotos.

Diagonales transitables

Diagonales intransitables

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

La lectura de la cadena de entrada ocupa hasta 'Wend'. Buen efecto secundario: abandona la cadena de entrada una vez que la placa [X] está completamente codificada, por lo que puede dejar una descripción al final.

En la codificación del tablero, los peones son 2, otras piezas son 3, el negro es negativo. Los peones son reconocidos por 'P' y 'p' que tienen códigos de caracteres divisibles por 8.

'X (7,0) = 1', configuración a1 accesible, es donde comienzan las comprobaciones de ruta. Esto escanea repetidamente el tablero tratando de agregar cuadrados accesibles desde los cuadrados marcados como accesibles (1) hasta ahora. El acceso diagonal y la ocupación se verifican en un cálculo lógico IF + que una vez vivió en una función pero ahora se encuentra en bucles vecinos anidados. La verificación de acceso diagonal se basa en el producto de los dos cuadrados de las esquinas del gatito, que es solo de 6 o más si las piezas son del mismo color y al menos una es una pieza, no un peón.

Llamar en hoja de cálculo; devuelve el valor en X (0,7) - 1 si h8 es accesible y 0 si no - que Excel reconoce como verdadero / falso. = SI (Z (C2), "sí", "no")

Tal vez me dejé arrastrar por el código, arriba, así que aquí hay una versión comentada semi-sin golf:

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

Notas de progreso

Edición 1: El código ahora no es como 666-devilish :-D y ha perdido sus funciones; Encontré una forma lo suficientemente corta de escribirlos para evitar la sobrecarga.

Edición 2: Otro gran salto hacia adelante, terminando efectivamente el trabajo de eliminar las funciones de inc / dec, suspirar y usar un par de globales. Finalmente podría estar entendiendo esto ...

La codificación de piezas y cuadrados cambió. Sin efecto en la longitud del código.

Edición 3: retorno de funciones (falsas), eliminando todas esas molestasCall bytes y algunos otros ajustes.

Editar 4: Rompiendo las 500 grandes, woohoo - suavizó los 3 bucles For en 1.

Editar 5: Jiminy Cricket, otra gran caída cuando suavicé las dos funciones juntas: mi verificación de acceso diagonal siempre pasa por cuadrados adyacentes, así que ...

Editar 6: Niblicks sagrados, otra caída masiva. Adiós a funciones externas y, por lo tanto, globales ... He llegado a menos de la mitad de la longitud original publicada ...

Edición 7: Agregar versión sin golf

Edición 8: Se revisó el proceso de lectura por unos pocos dólares más.

Edición 9: exprimí un par de expresiones para las últimas gotas de sangre

Edición 10: la Nextdeclaración de compilación arroja algunos bytes

Por interés, los gráficos de los tableros después del análisis de accesibilidad (los números de código están desactualizados pero ...) los cuadrados accesibles son verdes, los cuadrados inaccesibles blancos y otros colores son piezas o peones.

Un par de placas de desafío: h8 es accesible en ambos:

• P1Pq2p1 / 1P1R1R1p / 1K2R1R1 / 1p1p1p2 / p1b1b1np / 1B1B1N1k / Q1P1P1N1 / 1r1r1n2 - 10 pases para resolver
• P1P3r1 / 1P1R2r1 / 1N1R1N2 / 1P1P1P2 / 1n1p1ppp / 1B1B4 / 1b1pppp1 / 1P6: un camino sinuoso

Matlab, 636887 bytes como guardados (incluida la sangría)

Esta solución no está muy desarrollada, pero quería seguir adelante y presentarla.

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

Lee una cadena de tablero xcomo se especifica arriba y la convierte en la más completamente representada o, luego encuentra todos los movimientos (bordes del gráfico) entre espacios, luego determina qué movimientos son posibles (no en espacios rellenos), luego determina qué movimientos posibles tienen " puertas "de dos piezas para pasar entre ellas, luego se da cuenta si la puerta está abierta (peones, colores opuestos) o cerrada (mismo color e incluye un no peón). Luego, camina para encontrar ubicaciones accesibles por caminos desde el cuadrado inferior izquierdo y si un camino puede alcanzar el espacio 64, es un tablero de Sí.