Chessboard maze

Question

Chess pieces (kings, queens, rooks, bishops, and knights) and pawns are on a board, but not on the a1 or h8 square. Your task is to travel from the empty a1 to the empty h8 squares, passing through only empty squares. The rules of movement are as follows:

1. You can proceed from any empty square to any empty square next to it (same rank, next or preceding file; or same file, next or preceding rank).
2. You can proceed from any empty square to any empty square diagonally next to it (next or preceding rank, next or preceding file), provided that the catty-corner squares contain either (a) two pawns or (b) pawns/pieces of opposite color. (Two non-pawn pieces, or a non-pawn piece and a pawn, of the same color are strong enough to bar your progress across the corner, but two pawns are not; and pieces/pawns of opposite color don't work in concert to bar your way.) For example, if you're on c4 and d5 is empty, you can proceed to it provided c5 and d4 contain pawns or contain pieces/pawns of opposite color. See the "Example diagonals" section, below, for pictures.

Input

FEN's board description. That is: The input will be a string that includes a description of rank 8, a slash (/), a description of rank 7, a slash, …, and a description of rank 1. The description of each rank comprises numbers and letters running from file a to file h, where the letters indicate pieces and pawns (the black ones are p= pawn, n=knight, b=bishop, r=rook, q=queen, k=king, and the white ones are capitalized versions of the same) and the numbers indicate the successive number of empty squares. For example, rnbqkbnr/pppppppp/8/8/4P3/8/PPPP1PPP/RNBQKBN is the board after one ply move (king's pawn to e4) in a chess game.

a1 and h8 will be empty in the input; i.e., the first slash has a digit before it, and the last slash has a digit after it.

Output

Truthy or falsey, indicating whether successful passage to h8 is possible.

If the input is not a valid FEN board description (meaning, one that matches my explanation above), or if a1 or h8 is occupied, then the output can be anything or nothing. (In other words: you may assume the input meets the requirements above.)

Scoring

This is code golf: fewest bytes wins.

Example input and output

Note that your code must work for all valid inputs, not only the examples.

Add a space and a w after each FEN to visualize it at http://www.dhtmlgoodies.com/scripts/chess-fen/chess-fen-3.html. (Note that some other online FEN visualizers will not allow a board that's illegal in chess, e.g. with a pawn on rank 1 or 8, so can't be used for our purposes.)

Truthy examples

• 8/8/8/8/8/8/8/8 — the empty board
• 1p1Q4/2p1Q3/2p1Q3/2p1Q3/2p1Q3/2p1Q3/Q1p1Q3/1q3q2 — there's a path a1, b2, b3, b4, b5, b6, b7, c8, d7, (not e8, that's blocked off, but) d6, d5, d4, d3, d2, d1, e1, f2, f3, f4, f5, f6, f7, f8, g8, h8
• 8/8/KKKKK3/K3K3/K1K1p3/Kp1K4/K1KK4/2KK4 — an example where a square that's blocked at one point must be passed through later on (to make sure you don't set squares as impassable)
• K1k1K1K1/1K1k1K1k/K1K1k1K1/1k1K1K1k/K1k1K1k1/1K1k1k1K/K1K1k1K1/1k1k1K1k — there's a single path through (just follow your nose: there's only one square to move to at each step, unless take a step backward); this is also an example where a square is blocked at one point but necessary later

Falsey examples

• 6Q1/5N2/4Q3/3N4/2Q5/1N6/2Q5/1N6 — any attempt at a path will have to pass through two diagonally situated same-color pieces
• N1q1K1P1/1R1b1p1n/r1B1B1Q1/1p1Q1p1b/B1P1R1N1/1B1P1Q1R/k1k1K1q1/1K1R1P1r — the only way through the a8-h1 diagonal is at f2-g3, but that would require passage through e1-d2 or f2-e3, which are both impossible.
• 4Q3/4q3/4Q3/5Q2/6Q1/3QqP2/2Q5/1Q6
• 4q3/4Q3/4q3/5q2/6q1/3qQp2/2q5/1q6

Example diagonals

In case the prose above was unclear, here are some pictures.

Passable diagonals

Impassable diagonals

Answer 1

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

Reading the input string occupies up to 'Wend'. Nice side effect - this abandons the input string once the board [X] is fully coded, so you can leave a description on the end.

In the board coding, pawns are 2, other pieces are 3, black is negative. Pawns are recognized by 'P' & 'p' having character codes divisible by 8.

'X(7,0)=1', setting a1 accessible, is where the path checks start. This repeatedly scans the board trying to add accessible squares from squares marked as accessible (1) so far. Diagonal access and occupancy are checked in a IF + logic-calc which once lived in a function but now sits in nested neighbour loops. The diagonal access check relies on the product of the two kitty-corner squares, which is only at 6 or more if pieces there are the same colour and at least one is a piece not a pawn.

Call in spreadsheet; returns the value in X(0,7) - 1 if h8 accessible and 0 if not - which Excel recognizes as truthy / falsy. =IF(Z(C2), "yes","no")

I maybe got carried away with scrunching the code down, above, so here is a semi-ungolfed commented 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

---

Progress notes

Edit1: The code is now not as 666-devilish :-D and has lost its functions; I found a short-enough way to write them to avoid the overhead.

Edit2: Another biggish leap forward, effectively finishing the work of removing the inc/dec functions, sigh, and using a couple of globals. I might finally be getting the hang of this....

The coding of pieces & squares changed. No effect on code length.

Edit3: Return of (fake) functions, removing all those annoying Call bytes, and some other tweaks.

Edit4: Breaking through the big 500, woohoo - smooshed the 3 For loops into 1.

Edit5: Jiminy Cricket, another big drop when I smooshed the two functions together - my diagonal access check always passes for adjacent squares, so...

Edit6: Holy niblicks, another massive drop. Buh-bye to external functions and thus globals... I have gone to under half the original posted length....

Edit7: Add ungolfed version

Edit8: Revised the read process for a few dollars more

Edit9: Squeezed a couple of expressions for the last few drops of blood

Edit10: Compund Next statement sheds a few bytes

---

For interest, graphics of the boards after accessibility analysis (the code numbers are out of date but...) accessible squares are green, inaccessible squares white and other colours are pieces or pawns.

A couple of challenge boards: h8 is accessible in both:

• P1Pq2p1/1P1R1R1p/1K2R1R1/1p1p1p2/p1b1b1np/1B1B1N1k/Q1P1P1N1/1r1r1n2 - 10 passes to solve
• P1P3r1/1P1R2r1/1N1R1N2/1P1P1P2/1n1p1ppp/1B1B4/1b1pppp1/1P6 - a winding path

Answer 2

Matlab, 636 887 bytes as saved (including indentation)

This solution is not very golfed, but I wanted to go ahead and put it up.

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

Reads a board string x as specified above and turns it into the more completely represented o, then finds all the moves (graph edges) between spaces, then figures out which moves are possible (not into filled spaces), then figures out which possible moves have "gates" of two pieces to pass between, then figures out if the gate is open (pawns, opposite colors) or closed (same color and including a non-pawn). Then, it walks through to find locations reachable by paths from the lower left square and if a path can reach space 64, it's a Yes board.