# The N Queens Problem, but with Fairy Chess Pieces

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>

• 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

• If we are being tested on only test cases we have access to the optimal solutions for each can theoretically be attached to something which reads the input for uniqueness. – fəˈnɛtɪk May 20 at 1:55
• in under 15 seconds I suggest that you remove this constraint. If you intend to encourage optimization, perhaps you could use the tag fastest-algorithm, which would require the answerers to include the time complexity of their solutions. Alternatively, you could employ a time-complexity constraint. Right now, the strict time requirement seems to do more harm than good (and with a complex challenge like this, an added constraint would discourage people from even attempting to create a solution). – JungHwan Min May 20 at 2:09
• @fəˈnɛtɪk: that sounds like abuse of a standard loophole. – Beefster May 20 at 2:19
• @JungHwanMin: The reason for the time limit is twofold (though it could perhaps be longer- maybe 30s to 1 minute). 1. I don't want runaway solutions that take an hour to score. 2. It allows for more variance in algorithmic choice. There is definitely an optimum size for all boards that is an upper bound, which brute-force solutions can (at least theoretically) find. A time limit forces cleverness. – Beefster May 20 at 2:28
• I guess a time complexity constraint would solve #1, but I feel it's too easy to calculate wrong. I guess I could require polynomial complexity or make it O(n^4) or so, but that also bans backtracking solutions. I think time limits are the way to go, but I sorta see your point, so I raised the time limit to 30 seconds. – Beefster May 20 at 2:42