Loading...
Loading...
Loading...
The chess club at Priya's college has an old n × n board, and some of its squares are cracked. Priya wants to place n queens so that no two queens attack each other: no two may share a row, a column or a diagonal. A queen cannot stand on a cracked square, but a cracked square does not block an attack.
Count the number of ways to place the n queens.
. for a good square and # for a cracked one.. or #Example 1
Input
4 .... .... .... ....
Output
2
A plain 4 × 4 board has exactly 2 ways.
Example 2
Input
4 .#.. .... .... ....
Output
1
One of the 2 ways puts a queen on the cracked square, so only 1 is left.
Try the problem first. Open one hint at a time.
Each row must hold exactly one queen. Place queens row by row, choosing a column for each row.
Before placing a queen at (r, c), check its column and both diagonals. Squares on one diagonal share r + c; on the other they share r - c.
Keep three boolean arrays: columns, r + c diagonals and r - c + n - 1 diagonals. Each check is then O(1).
Mark the three entries, go to the next row, then unmark them. Count 1 each time you place a queen in the last row.
Write your Java code, run it on the examples and submit it to hidden tests.
Solve in the editor