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:
- 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).
- 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.
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
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.
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.)
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.)
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
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.
In case the prose above was unclear, here are some pictures.