Fairy Chess is a sort of generalized chess that allows unconventional pieces. The eight queens puzzle is a classic problem where you have to put 8 queens on a chess board such that no two queens threaten each other. This challenge is sort of a generalized combination of the two.
Given a list of fairy chess pieces and their quantities, output a board such that all pieces are used and no piece threatens any other piece. The board is not directional and all pieces have symmetric movement. Your goal is to generate a solution on the smallest, squarest board you can in under 30 seconds.
Each piece has a list of valid move types. For the sake of simplicity, moves will be one of the following types:
- Leaper movement. A generalized form of knights. A leaper has two numbers,
nthat describe its movement. A leaper moves
mspaces in one orthogonal direction and then
nin a direction perpendicular to the other, "leaping" over intervening spaces.
- Rider movement. Moves in a straight line. Can be unlimited or restricted to a specific range. Can either be orthogonal or diagonal. It is possible for a piece to be in a rider's movement range without being threatened by it if there is a piece blocking its path that is too close to be captured. For instance, a 3-5 orthogonal rider could be blocked from taking a piece 4 spaces away if a non-threatening piece was one space away along the path
- Hopper movement. Hoppers are similar to riders in that they travel in a straight line, but they are different in that they have to "hop" over a piece to take the piece on the other side of the hopped-over piece. As such, they can only capture the second piece along a line of movement. Hoppers may also have minimum and maximum range.
How these are to be represented in the input is up to the implementation.
A 3-1 leaper moves like this: (
x represents spaces that can be moved to)
. . x . x . . . . . . . . . x . . . . . x . . . L . . . x . . . . . x . . . . . . . . . x . x . .
Note: in the following diagrams, rather than make a full diagram for each possible interaction, each row in the diagram represents one direction along the movement path.
A 3-5 hopper moves like this in each direction (
O represents another piece that cannot be taken)
H . . . . . . H O . x x x . H . O x x x . H . . O x x . H . . . O x . H . . . . O . H . . . . . O
Limited range on riders can have interesting effects when they have a minimum range. A 3-5 rider behaves in an interesting way when a piece is blocking its path to the minimum range. (
X represents another piece that can be taken.)
R . . x x x . R O . . . . . R . O . . . . R . . X . . . R . . x X . . R . . x x X . R . . x x x X
Hoppers can only take the second piece along their travel path. Once again, with the 3-5 range hopper:
H . . . . . . H O O . . . . H O O . . O . H . O x X . . H . . O X . . H . . . O x . H . . . . O O H . O . . . O
Your program input will be passed via stdin in lines of plain text, where each line describes the piece type and the number of instances of that piece. It follows this general format:
<Letter><copies, decimal>: <movements, comma separated>
Movements follow this format:
nare decimal digits representing the distances in each direction of movement.
xfor orthogonal or diagonal, respectively; and where
nare decimal digits representing the minimum and maximum distance, respectively.
nmay also be
-, indicating there is no maximum range.
nhave the same meanings as for riders.
Your program should output to stdout with each row of the board on each line. The letters in the piece definitions input should be used to represent each piece type and dots (
.) should be used to represent empty spaces on the board. Whitespace between board spaces are optional and will be ignored by the test driver. All solutions shown in the examples section are in a valid format.
Your solution should be a program that reads definitions from stdin (as a redirected file) and outputs boards to stdout. Logging, should you choose to use it, should go through stderr, as that is not captured by the test driver.
An example baseline solver can be found here. It's not very smart, but it does a decent job at making compact boards. There is room for improvement.
Your solution will be scored across 10 test cases (below) and each run will be scored with the following formula:
score = height **2 + width ** 2
This will be totaled across all solutions. Lowest score wins. All boards returned must be valid solutions and be calculated in under 15 seconds or else your solution will be disqualified.
Ties will be broken by first solution posted.
A test driver that scores solutions automatically can be found here. You will need Python 3.5+ to run it. There are no third-party dependencies.
With the input:
A2: L21 B1: Rx1- C2: H+1-
You have these pieces:
A) 2 Knights (2-1 Leapers)
B) 1 Unlimited-range diagonal rider
C) 2 Unlimited-range orthogonal hoppers
A valid solution is:
A . A B . . . . . . C . . . C
This solution would score 34 points (3*3 + 5*5 = 9 + 25 = 34)
With the input:
A5: L32 B1: R+1-,Rx1-,L21 C2: H+3- D4: Rx14,L30
You have these pieces:
A) 5 3-2 Leapers
B) 1 Unlimited-range 8-way rider with 2-1 Leaps (a queen and knight combined)
C) 2 Range 3+ orthogonal hoppers
D) 4 Range 4- diagonal riders with 3-0 leaps
A valid solution is:
. . . . . . . . . B A . . . . D . . . . . . . . . . . . . . . . . . . . . . D . . . . C D . . . . . . . . . . . . . A . . . . . D . . . . . A . . . . . . . . . . . . C A . . . . . . . . . . A . . . .
This solution would score 200 points (10*10 + 10*10 = 100 + 100 = 200)
The following test cases will be used for scoring:
Standard Chess Set (without pawns)
K2: L10,L11 Q2: R+1-,Rx1- R4: R+1- B4: Rx1- N4: L21
K2: L10,L11 A2: R+1-,Rx1-,L21 R4: R+1-,L11 B4: Rx1-,L10 C4: R+1-,L21 P4: Rx1-,L21
Archbishops and Super Rooks
B14: Rx1-,L10 R8: R+1-,L11
Wazirs and Ferzes
W21: L10 F24: L11
10 Lords-A-Leaping (x3)
W3: L10 F3: L11 D3: L20 N3: L21 A3: L22 H3: L30 L3: L31 J3: L32 G3: L33 X3: L40
20 Frog Queens
Things are Really Hoppin'
A12: Hx36 B8: H+36 C6: H+2- D10: Hx2-
A6: R+36,L22 B16: Hx59 C10: L21,L33 D6: Rx22,R+44 E6: H+47,L31 F8: H+22,Hx22
Rules and Notes
- No abusing standard loopholes
- Your program will be limited to running on a single CPU
- Final scoring will be done on my 2.8 GHz i5, using Windows Subsystem for Linux
- You may assume input files are valid.
- You may assume that leapers will never be
L00so that you never have to check for self-threatening.
- There is no hard limit on the size of board in a calculated solution. All that matters is that it is a valid solution.
tl;dr: Programs should try to make boards as small and as square as possible in less than 30 seconds. Lowest Score Wins. Ties will be broken by first solution posted. Once again, the test driver can be found here