14
\$\begingroup\$

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

pawns of the same color pawns of opposite colors rooks of opposite colors

Impassable diagonals

a rook and a pawn of the same color rooks of the same color

\$\endgroup\$
  • \$\begingroup\$ I'm sorry, i'm not sure about stanadard golf rules: What happens, if you insert a illegal String ? May any behavior occur? \$\endgroup\$ – alex berne Jun 21 '16 at 19:04
  • \$\begingroup\$ @alexberne I believe this covers it: "your code must work for all valid inputs". \$\endgroup\$ – Rainbolt Jun 21 '16 at 19:15
  • \$\begingroup\$ @alexberne, I've edited. Is it clear now? \$\endgroup\$ – msh210 Jun 21 '16 at 20:31
  • \$\begingroup\$ yes, thanks. I'm new here, so it might be usal stuff for golfer, but for me it was unclear :) \$\endgroup\$ – alex berne Jun 21 '16 at 20:49
  • \$\begingroup\$ Just wanted to say thanks for a great puzzle @msh210 . I don't understand why there aren't more answers. \$\endgroup\$ – Joffan Jun 23 '16 at 15:49
6
\$\begingroup\$

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")

enter image description here

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.

3 successful boards 3 blocked boards

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
\$\endgroup\$
  • 1
    \$\begingroup\$ Very nice, and +1, but: (1) Are you sure 960 steps suffice? (2) Can you save some bytes by looking at the board upside-down? If V>9 Then X(7-P,C)= would I think (not that I know VBA) become If V>9 Then X(P,C)=. \$\endgroup\$ – msh210 Jun 24 '16 at 5:39
  • \$\begingroup\$ Actually that technique saves initializing P, so thanks for asking :-). And yes, I'm sure 15 passes of the board is enough; I did quite a lot of checking. I haven't actually been able to push it past 10 passes, in fact, but 640 and 960 have the same number of characters so I'll play it safe. BUT if I bult the board upside down, it COULD take more than 10 passes, and maybe more than 15 - unless I traversed the board upside down also, which would have an overhead. \$\endgroup\$ – Joffan Jun 24 '16 at 5:45
  • \$\begingroup\$ @msh210 1 additional observation - 15 loops is just enough to analyze the whole board, worst case, but 10 loops is enough to get the status of h8, so I have a large margin really. The reason is that finding paths works much faster in the direction of assessment, increasing row# and column# - as long as the path is going up or right, it will be completed in a single pass. Going left or down only gets a single step further per pass. \$\endgroup\$ – Joffan Jun 24 '16 at 16:21
  • \$\begingroup\$ @msh210 As part of a revamp on the read process - which narrowly kept the facility to leave a comment on the end of the FEN string - I added the board reversal you suggested - some boards now take over 15 passes (up to 17) so the function has increased to 30 passes of the board. \$\endgroup\$ – Joffan Jun 24 '16 at 23:31
  • \$\begingroup\$ @Joffan you can drop 3 Bytes by condensing all instances of [some non-letter character] To to [some non-letter character]To \$\endgroup\$ – Taylor Scott Mar 28 '17 at 23:20
3
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ Cool. Did you test it against my example FENs in the question to make sure it returns the correct result for each? Also, since this is a code-golf question, you really should golf this. If nothing else, can you get rid of the indentation (or make it a single space or tab instead of four spaces)? and/or drop the spaces around the =s? (I don't know MATLAB: maybe those are impossible.) \$\endgroup\$ – msh210 Jul 11 '16 at 17:34
  • \$\begingroup\$ Yeah, and I might do some of that during my next break. I did test it against all of your examples and then some. Should I indicate that in some way? \$\endgroup\$ – sintax Jul 11 '16 at 17:36
  • \$\begingroup\$ Dunno; I was just wondering. \$\endgroup\$ – msh210 Jul 11 '16 at 17:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.