The N Queens Problem, but with Fairy Chess Pieces

Question

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.

Challenge

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.

Pieces

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, m and n that describe its movement. A leaper moves m spaces in one orthogonal direction and then n in 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.

Piece Examples

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

Input

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:

• Leaper: Lmn, where m and n are decimal digits representing the distances in each direction of movement.
• Rider: Rdmn, where d is + or x for orthogonal or diagonal, respectively; and where m and n are decimal digits representing the minimum and maximum distance, respectively. n may also be -, indicating there is no maximum range.
• Hopper: Hdmn, where d, m, and n have the same meanings as for riders.

Output

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.

Coding

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.

Scoring

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.

Examples

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)

Test Cases

The following test cases will be used for scoring:

8 Queens

Q8: R+1-,Rx1-

Standard Chess Set (without pawns)

K2: L10,L11
Q2: R+1-,Rx1-
R4: R+1-
B4: Rx1-
N4: L21

10 Amazons

A10: R+1-,Rx1-,L21

Compound Pieces

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

A20: H+1-,Hx1-

Things are Really Hoppin'

A12: Hx36
B8: H+36
C6: H+2-
D10: Hx2-

Blindspots

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 L00 so 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