Contest

CAKEWALK

# PROBLEM:

Given a chessboard of size N*N. Place exactly N-2 queens on it such that, every cell is reachable by atleast one queen.

# EXPLANATION:

Solve for N=3, N=4 and N=5 to get the solution.

N=3, 4, 5

Given below are optimal solutions to each of the cases.

N = 3

``````...
.Q.
...
``````

N=4

``````....
.Q..
....
...Q
``````

N=5

``````.....
.Q...
.....
...Q.
....Q
``````

Can you observe some pattern in each of the solutions?

Solution

Place a queen in each of the diagonal cells (where r=c) EXCEPT the first (r=c=1) and third (r=c=3) diagonal cells.

The total number of queens placed will be N-2. To prove that each cell is reachable by atleast one queen, show that:

• Each cell (r,c) where r>3 or c>3, is reachable by one of the last N-3 queens.
• All others cells, that is, with r\le 3 and c\le 3, are reachable by the first queen.

O(N^2)

per test case.

# SOLUTIONS:

Editorialistâ€™s solution can be found here

Experimental: For evaluation purposes, please rate the editorial (1 being poor and 5 excellent)

• 1
• 2
• 3
• 4
• 5

0 voters