QPLACE - Editorial

editorial
, ,
1

PROBLEM LINK:

Contest

DIFFICULTY:

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.

TIME COMPLEXITY:

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