Is this Chessboard Reachable?
The goal of this challenge is to determine, given the state of a
chessboard, whether or not that chessboard can actually be reached in
the course of standard play. Of course, doing this in general is a
rather hard problem, so we'll be simplifying the problem to a set of a
few rules which should approximate the "reachability" constraint.
Your input will be a chessboard, specifying what pieces are at what
positions on the 8x8 board. At each position, there can be either
nothing or a piece. If there is a piece, it is either a pawn, bishop,
knight, rook, queen, or king, and it is either white or black. Input
can be taken in any reasonable form. Your output should be truthy or
falsy, indicating whether all of the below rules are satisfied.
For the below rules, I'll be using standard chess notation to refer to
the squares on the board. That is, I'll be referring to squares on the
board by their rank (1-8) and their file (a-h), as such
8........
7........
6........
5........
4........
3........
2........
1........
abcdefgh
where the white player starts on ranks 1-2 and the black player starts
on ranks 7-8. Obviously, you don't have to use the same notation, and
if it's easier for you to take the board input flipped or rotated,
that's fine too as long as you specify it in your answer.
For one of the rules, you have to distinguish between white and black
squares on the board. The board is layered with a checkerboard
pattern, so white squares are always immediately surrounded by black
on all four sides, and vice versa. In typical chess, the a1 square is
black, but that doesn't really matter for the below criteria.
The Rules
In order for a board to be considered reachable, it must satisfy all
of the following rules. This is decision-problem, so you don't have
to tell me which rule an unreachable board violated; all I expect of
your output is a "yes" or a "no".
White and black each have exactly one king on the board: no more,
no less.
Pawns cannot appear on rank 1 or rank 8.
Each player has a maximum of 16 pieces on the board total. These
pieces must be a subset of the following: 2 bishops, 2 rooks, 2
knights, 1 queen, 1 king, and 8 wildcards. The "wildcard" pieces
can be any piece they please (since we assume pawns could have been
promoted).
For either player, if that player has at least two bishops, and
those two bishops cannot have been promoted from pawns (i.e. they
must be the "bishops" in rule 3, not the "wildcards"), then that
player must have at least one bishop on a white square and at least
one bishop on a black square.
All of a player's pawns must be able to reach the square they're
occupying. More formally, for each player, there must be an
assignment (an injective function) from the set of that player's
surviving pawns to the files (a-h) they started on, such that each
pawn can reach its current position from its starting position with
only forward and forward-diagonal movements.
Pawn Movements
Rule 5 may require some elaboration. Suppose a white pawn is on d5. Then it could have come from the following
places (indicated by X)
8........
7........
6........
5...♙....
4..XXX...
3.XXXXX..
2XXXXXXX.
1........
abcdefgh
So it could have started on a2, b2, c2, d2, e2, f2, or g2, but not h2.
There must be an assignment of pawns to starting positions such that
no two pawns started at the same position and every pawn can reach its
current position from where it began. A black pawn follows the same
rules but started on rank 7 and moves down rather than up. So a black
pawn at the same position could have come from b7, c7, d7, e7, or f7,
as follows.
8........
7.XXXXX..
6..XXX...
5...♟....
4........
3........
2........
1........
abcdefgh
Notes
- Only the rules above apply. Other complexities of a standard game
of chess (in particular, castling or en passant) are not part of
this problem and should not be considered.
- This is code-golf, so the shortest solution wins.
- Input can be taken in whatever form is most convenient. Output
follows the usual decision-problem rules, so any two distinct
outputs for truthy/falsy are acceptable.
- This is an oversimplification of the reachability problem in chess.
As such, an answer which provably enumerates every chessboard and
tests for membership is not correct.
Examples
Reachable chessboards (true):
8♜♞♝♛♚♝♞♜
7♟♟♟♟♟♟♟♟
6........
5........
4........
3........
2♙♙♙♙♙♙♙♙
1♖♘♗♕♔♗♘♖
abcdefgh
8........
7........
6........
5........
4........
3........
2..♚.....
1.....♔..
abcdefgh
8........
7.....♚..
6.♛......
5...♟....
4........
3.....♕..
2........
1...♔....
abcdefgh
8.....♚..
7♟♟♟♟♟♟♟♟
6........
5........
4........
3........
2♙♙♙♙♙♙♙♙
1....♔...
abcdefgh
8.....♚...
7♟♟♟♟♟♟♟♟
6........
5........
4........
3........
2♙♙♙♙♙♙♙♙
1....♔...
abcdefgh
8........
7.♚......
6...♕♕♕♕.
5..♕....♕
4..♕..♔.♕
3.......♕
2........
1........
abcdefgh
8........
7...♚.♟.♙
6.♙.♙..♙.
5.....♘..
4.♕..♕♘♗♖
3.....♘♗♖
2..♕....♖
1......♔.
abcdefgh
8♜..♛♚♜♜♜
7♟♟♟♟♟♟..
6........
5........
4........
3........
2♙♙♙♙♙♙♙♙
1♖♘♗♕♔♗♘♖
abcdefgh
8♜♞♝♛♚♝♞♜
7♟♟♟♟♟♟♟♟
6........
5........
4........
3........
2♙♙♙♙♙♙♙.
1♖♗♘♕♔♗♘♖
abcdefgh
8♛♛♛♛♛♛.♛
7........
6......♚.
5.♝.♝....
4.....♟..
3........
2..♖♖♖.♔.
1........
abcdefgh
8.....♚..
7........
6........
5........
4........
3.♙♙.....
2..♙♙♙♙♙♙
1.....♔..
abcdefgh
8.....♚..
7........
6........
5........
4........
3.....♙..
2...♙♙♙.♙
1.....♔..
abcdefgh
8.....♚..
7........
6.♟♟♟♟...
5.♟♟.....
4........
3........
2........
1.....♔..
abcdefgh
Unreachable chessboards (false):
(Rule 1: Not enough kings)
8........
7........
6........
5........
4........
3........
2........
1........
abcdefgh
(Rule 1: Too many kings)
8♚♚♚♚♚♚♚♚
7♚♚♚♚♚♚♚♚
6♚♚♚♚♚♚♚♚
5♚♚♚♚♚♚♚♚
4♚♚♚♚♚♚♚♚
3........
2........
1...♔....
abcdefgh
(Rule 2: Bad white pawn placement)
8.....♚..
7♟♟♟♟♟♟♟♟
6........
5........
4........
3........
2.♙♙♙♙♙♙♙
1♙...♔...
abcdefgh
(Rule 2: Bad black pawn placement)
8.♟...♚..
7♟.♟♟♟♟♟♟
6........
5........
4........
3........
2♙♙♙♙♙♙♙♙
1....♔...
abcdefgh
(Rule 3: Too many white queens)
8........
7.♚......
6...♕♕♕♕.
5..♕....♕
4..♕..♔.♕
3..♕....♕
2........
1........
abcdefgh
(Rule 3: Too many black pieces)
8♜♞♝♛♚♝♞♜
7♟♟♟♟♟♟♟♟
6......♟.
5........
4........
3........
2♙♙♙♙♙♙♙♙
1♖♘♗♕♔♗♘♖
abcdefgh
(Rule 3: Too many white pieces)
8........
7...♚.♙.♙
6.♙.♙..♙.
5.....♘..
4.♕..♕♘♗♖
3.....♘♗♖
2..♕....♖
1......♔.
abcdefgh
(Rule 3: Too many black rooks)
8♜..♛♚♜♜♜
7♟♟♟♟♟♟♟.
6........
5........
4........
3........
2♙♙♙♙♙♙♙♙
1♖♘♗♕♔♗♘♖
abcdefgh
(Rule 4: White bishops are the same color)
8♜♞♝♛♚♝♞♜
7♟♟♟♟♟♟♟♟
6........
5........
4........
3........
2♙♙♙♙♙♙♙♙
1♖♗♘♕♔♗♘♖
abcdefgh
(Rule 4: Black bishops are the same color)
8♛♛♛♛♛♛♛♛
7........
6......♚.
5.♝.♝....
4.....♟..
3........
2..♖♖♖.♔.
1........
abcdefgh
(Rule 5: White pawn placement is impossible)
8.....♚..
7........
6........
5........
4........
3..♙.....
2.♙♙♙♙♙♙♙
1.....♔..
abcdefgh
(Rule 5: White pawn placement is impossible)
8.....♚..
7........
6........
5........
4........
3.....♙.♙
2...♙♙♙.♙
1.....♔..
abcdefgh
(Rule 5: Black pawn placement is impossible)
8.....♚..
7.♟♟♟♟...
6........
5.♟♟.....
4.♟♟.....
3........
2........
1.....♔..
abcdefgh
Example Implementation (Python 3)
# Takes input from stdin in the form shown above (a grid of Unicode
# chess characters and dots). Prints True if reachable. Prints False
# and the first rule number which is violated if unreachable.
import sys
from collections import defaultdict, namedtuple
Piece = namedtuple('Piece', ['color', 'type'])
# Read in the data from stdin.
data = []
for line in sys.stdin:
chars = list(filter(lambda x: x in ".♟♙♝♗♞♘♜♖♛♕♚♔", line))
if chars:
data.append(chars)
if len(data) == 8:
break
assert len(data) == 8
for line in data:
assert len(line) == 8
# Parse it into a more convenient format.
translation = {
".": None,
"♟": Piece('black', 'pawn'),
"♙": Piece('white', 'pawn'),
"♝": Piece('black', 'bishop'),
"♗": Piece('white', 'bishop'),
"♞": Piece('black', 'knight'),
"♘": Piece('white', 'knight'),
"♜": Piece('black', 'rook'),
"♖": Piece('white', 'rook'),
"♛": Piece('black', 'queen'),
"♕": Piece('white', 'queen'),
"♚": Piece('black', 'king'),
"♔": Piece('white', 'king'),
}
for rank in data:
for i in range(8):
rank[i] = translation[rank[i]]
# Count the number of each piece that each player has, slotting
# necessary pawn promotions into their own category.
allowed = { 'bishop': 2, 'rook': 2, 'knight': 2, 'king': 999, 'queen': 1, 'pawn': 0 }
pieces = defaultdict(lambda: 0)
for rank in data:
for piece in rank:
if piece is None:
continue
if pieces[piece] >= allowed[piece.type]:
# Already have too many; it's a promoted pawn
pieces[Piece(piece.color, 'pawn')] += 1
else:
# Count it normally
pieces[piece] += 1
# Rule 1: Each color should have exactly one king.
if pieces[Piece('white', 'king')] != 1 or pieces[Piece('black', 'king')] != 1:
print(False, 1)
exit(0)
# Rule 2: Pawns cannot appear on rank 1 or rank 8.
for piece in data[0] + data[7]:
if piece is not None and piece.type == 'pawn':
print(False, 2)
exit(0)
# Rule 3: Since we already put any "overflow" pieces at the pawn key,
# we just need to make sure we have at most eight pawns.
for color in ['white', 'black']:
if pieces[Piece(color, 'pawn')] > 8:
print(False, 3)
exit(0)
# Rule 4: If we have both bishops and our pawns are all accounted for,
# then we have to have a bishop in each color.
for color in ['white', 'black']:
if pieces[Piece(color, 'bishop')] >= 2 and pieces[Piece(color, 'pawn')] >= 8:
squares = { 'white': False, 'black': False }
for y, rank in enumerate(data):
for x, piece in enumerate(rank):
square_color = 'white' if (x + y) % 2 == 0 else 'black'
if piece == Piece(color, 'bishop'):
squares[square_color] = True
if not (squares['white'] and squares['black']):
print(False, 4)
exit(0)
# Rule 5: All pawns must be able to get to where they are. I solve
# this here by brute force (simply trying every possible permutation),
# which is exponentially inefficient, but it'll do for this example.
def recursive_assign(taken, choices, i):
if i >= len(choices):
return True
current = choices[i]
for x in current:
if x not in taken:
if recursive_assign(taken + [x], choices, i + 1):
return True
return False
for color in ['white', 'black']:
starting_file = 6 if color == 'white' else 1
choices = []
for y, rank in enumerate(data):
for x, piece in enumerate(rank):
if piece == Piece(color, 'pawn'):
possibilities = range(8)
possibilities = filter(lambda i: abs(i - x) <= abs(y - starting_file), possibilities)
choices.append(list(possibilities))
if not recursive_assign([], choices, 0):
print(False, 5)
exit(0)
print(True)
Proposed Tags
Sandbox Concerns
- I worry Rules 4 and 5 are still not clear enough. I tried to write
them in a way that was as clear as possible while still being
mathematically unambiguous.
