Simultaneous Chess Moves

Hard

An 8×8 board holds one to four pieces: rooks, queens and bishops. Piece i is of type kinds[i] ("rook", "queen" or "bishop") and stands on cells[i] = [r, c], with rows and columns numbered 1 to 8. Each piece is given a destination it can reach by moving in a straight line: a rook horizontally or vertically, a bishop diagonally, a queen in any of those eight directions. The destination may also be the square the piece is already on. All pieces start at the same moment and move one square towards their destination every second; once there, a piece stays put. A plan (a choice of destinations for all pieces) is invalid if at some moment two pieces are on the same square. Two neighbouring pieces swapping places within one second do not collide. Return the number of valid plans.

Example 1

kinds=['bishop'], cells=[[1, 1]] → 8

A bishop in the corner can slide 1 to 7 squares along its diagonal or stay put: 8 options.

Example 2

kinds=['rook'], cells=[[5, 4]] → 15

The rook can go to any of the 14 squares in its row and column or stay: 15 options.

Example 3

kinds=['rook', 'rook'], cells=[[1, 1], [1, 2]] → 196

Constraints

1 ≤ len(kinds) = len(cells) ≤ 4
kinds[i] is "rook", "queen" or "bishop"
At most one queen
1 ≤ r, c ≤ 8
All squares in cells are distinct

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Array String Backtracking Simulation