Chess Club Spotlight Budget
Minimum-cost usable cells, one per grid row, with no column or diagonal conflicts
A chess club is preparing a queen-placement exhibit on an n × n board. Each usable square has a signed setup cost: negative costs represent sponsorship credits.
You are given board, where board[r][c] is '.' for a usable square or '#' for an unavailable square, and costs, where costs[r][c] is the setup cost of that square. Costs on unavailable squares are ignored.
Place exactly one queen in every row, using only usable squares. No two queens may share a column or a diagonal. In particular, queens at (r1, c1) and (r2, c2) conflict diagonally when abs(r1 - r2) == abs(c1 - c2).
Return a list columns of length n, where columns[r] is the zero-based column chosen for row r. Minimize the sum of the chosen squares' costs. If multiple placements have the same minimum cost, return the lexicographically smallest list: at the first differing row, prefer the smaller column.
Return [] if no valid placement exists.
Examples
Example 1
Input: board = ["....","....","....","...."], costs = [[0,0,-2,0],[-2,0,0,0],[0,0,0,-2],[0,-2,0,0]] Output: [2,0,3,1]
There are two valid placements on this open board. The placement beginning in column 2 uses the four squares with negative costs, so it is preferred despite starting in a larger column.
Example 2
Input: board = ["....","....","....","...."], costs = [[5,5,5,5],[5,5,5,5],[5,5,5,5],[5,5,5,5]] Output: [1,3,0,2]
Every usable square has the same cost. The two valid placements tie, so the placement beginning in column 1 is selected by the lexicographic rule.
Example 3
Input: board = [".###",".###",".###",".###"], costs = [[1,0,0,0],[2,0,0,0],[3,0,0,0],[4,0,0,0]] Output: []
Each row has a usable square, but all usable squares are in the same column. No valid exhibit can be built.
Constraints
- 1 <= n == board.length <= 12
- Every string in board has length n and contains only '.' and '#'.
- costs has n rows, each containing n integers.
- -1000000 <= costs[r][c] <= 1000000
The intended solution uses backtracking with bitmasks and an admissible cost bound. Increasing-column traversal visits complete placements in lexicographic order, so branches whose lower bound equals the best known cost can be pruned. A conservative complexity bound is O(n! + n^2 * 2^n) time and O(n^2 + 2^n) auxiliary space.
Hints
Show hint 1Hint 1
Place queens row by row, tracking occupied columns and the diagonals that attack the current row. Try candidate columns in increasing order.
Show hint 2Hint 2
For a lower bound, let each remaining row independently choose its cheapest usable square in a currently unused column, ignoring diagonal conflicts and collisions between future choices. Cache this bound by the unused-column mask.
Follow-up questions
What an interviewer might ask once you have a working solution.
- How would you return the number of minimum-cost placements as well as the canonical placement? Which pruning comparison would need to change?
- How would you adapt the search if some queens were already fixed on the board?
Practice this with an AI interviewer
Explain your approach out loud, write Python or JavaScript, run it against hidden tests (including large inputs), and get a scored debrief.
Start this problem