Queens Around Obstacles
Count the ways to place n queens on an n by n chessboard so that no two queens share a row, a column or a diagonal, with one extra rule: the cells listed in blocked, given as [row, col] pairs with 0-based indices, cannot hold a queen. Return the number of valid placements. Two placements are different when some queen stands on a different cell.
For example, with n = 4 and no blocked cells there are 2 placements; blocking the cell [0, 1] rules out one of them, leaving 1.
Example 1
The two classic 4-queen placements put the first-row queen in column 1 or in column 2.
Example 2
Blocking row 0, column 1 removes the placement that uses that cell, so one placement remains.
Constraints
1 <= n <= 80 <= len(blocked) <= 16, every pair lies on the board and no pair is repeated
Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.
More Recursion problems
- Signs Between the DigitsHard
- Spell It With TilesHard
- Swap the Balanced PiecesHard
- Times Before PlusHard
- Valleys in the Folded StripHard
- Count the BoxesBeginner
- Digit TallyBeginner
- Equal NeighboursBeginner