Queens on a Cracked Board

An old chess hall has huge square boards, and some squares are cracked and cannot hold a piece. Place n queens on an n × n board so that no two queens attack each other (no two share a row, a column or a diagonal) and no queen stands on a cracked square.

Write place_queens(n, cracks) that returns a list q of length n: q[r] is the column of the queen in row r. cracks is a set of (row, col) squares that must stay empty. Any valid placement is accepted.

The tests build their boards with cracked_board(n, seed), which cracks n // 8 random squares in every row; it is available in your code. Every test board has at least one valid placement.

Examples

Input:  n = 4, cracks = set()
Output: [1, 3, 0, 2]   (or [2, 0, 3, 1])

Input:  n = 8, cracks = cracked_board(8, 1)   (one cracked square per row)
Output: any of the 23 valid placements

Constraints

• n == 1 or 4 <= n <= 500
• Each test must finish in well under a second in your browser, so a search that places queens one row at a time and backs up on failure is far too slow for the big boards.
• Use random for any random choices and never the clock: the tests seed it.

Goals

• Repair a complete but flawed placement instead of building one square at a time
• Count conflicts with column and diagonal tallies in O(1)
• Use random tie-breaking so a repair search does not cycle