×

# Rooks on a chessboard!

Hello guys!!

I have a programming problem for which I need help.

You are given an $$N\times N$$ chess board (where $$N\leq 10000$$ ) which has no pieces on it. On the board there are obstacles (meaning that no piece can be put on the obstacle and no piece can go over the obstacle at any time). Your job is to provide the maximum number of Rooks you can put on the chessboard so that no $$2$$ Rooks atack each other.

Explanation: If there is an obstacle between 2 rooks they dont atack each other! For example:

..O R X R O... is a valid combination for 2 of the rooks if O are open spots on the board, R are rooks and X is the obstacle.

PS: Please provide an explanation of the algorithm you are using as well as a proof if you can so I can understand better!! Much appreciated

Note by Alladin Sjebrnakov
2 years, 4 months ago

Sort by:

I thought of a condition where you are guaranteed that placing a rook on a certain square is optimal. Given a board with obstacles and some number of rooks already placed, we say that it is optimal to place a new rook in a certain position if the maximum number of rooks that can be fit on the board does not decrease after placing that new rook (we count already placed rooks in this maximum number). We can then maximize the number of rooks by making a sequence of optimal placements.

Terminology: a [row] is a full unobstructed piece of a row. That is, two positions are on the same [row] if they are on the same row and they are unobstructed by an obstacle. We have a similar definition for [column].

Lemma: after placing a number of rooks, an open position (x,y) is optimal if: There do not exist a,b so that

1. (a,y) and (x,b) are open spaces (we can still place rooks on them)
2. (x,y) sees both (a,y) and (x,b) (same [row] and [column])
3. It is not the case that (a,b) sees both (a,y) and (x,b)

Proof: Suppose we are given a position with some number of rooks placed. Suppose (x,y) is not optimal but holds the condition. Since placing (x,y) only closes the positions on its [row] and [column], an optimal solution (which does not include (x,y)) must include two rook placements, one on (x,y)'s [row] and one on its [column]. If it didn't, we could add (x,y) to the so called optimal solution and remove at most one rook, yielding another optimal solution, this time containing (x,y).

Let the two positions in this optimal solution be (a,y) and (x,b). Then these must be currently open, so parts 1 and 2 are satisfied. Thus part 3 is not satisfied, since we assumed (x,y) holds the condition. Since (a,y) is open, there has not been a rook placement on its [column]. Since (x,b) is open, there has not been a rook placement on its [row]. Since there has not been a rook placement on its [row] or [column], (a,b) is open. But then placing (x,y) and (a,b) closes the same squares as placing (a,y) and (x,b), so they are interchangeable in the optimal solution, which contradicts (x,y) not being optimal. QED.

Some thoughts:

As a corollary, any open square on a [row] or [column] with no other open square is optimal.

This may provide a complete algorithm. I conjecture that there does not exist a board (with some filled rooks) without any position holding this condition.

By itself, this is an extremely slow algorithm. · 2 years, 3 months ago

I'm not sure that the following will produce an optimal solution and this is definitely not the best algorithm:

1. Create a list containing coordinates of all empty squares.
2. Calculate how many squares the new rook would threaten for each element in the list.
3. Place the new rook in the square that threatens the least number of squares.
4. Delete all the squares that the new rook is threatening from the list and also the square where you placed the new rook.
5. If the list is empty, terminate; else, goto 2

Or, do this if you are sure that placing a rook in any feasible place won't compromise the maximum number of rooks that are going to be placed:

1. Create a list containing coordinates of all empty squares.
2. Pick the first element of the list and place a rook in the indicated coordinate.
3. Delete all the coordinates that rook is now threatening from the list and also the square where you placed the new rook.
4. If the list is empty, terminate; else goto 2
· 2 years, 4 months ago

Counterexample: o's are obstacles, _'s are squares with no obstacles, r's are rooks Given the position

oooo _ _

oooo _ _

ooo _ _ _

oo _ _oo

_ _ _ ooo

_ _ _ ooo

Your algorithm would fill out the middle space immediately, since it threatens only two squares. You would get something like

oooo _ _

oooo r _

ooo _ _ r

oo _ r oo

_ _ r ooo

_ r _ ooo

But you could do better with

oooo _ r

oooo r _

ooo r _ _

oo r _oo

_ r _ ooo

r _ _ ooo · 2 years, 3 months ago

Being I non specialist in computer science, the subject just show up well after my college years, I only dare to give you some thoughts and suggestions in the hope to cast some light upon which you can elaborate.

1) I will consider the board as matrix ordinary matrix (N x N) to make ourselves more comfortable we can use a regular chessboard 8x8 so we can experiment at our will.

2) We can identify an obstacle by a 0 and a rook by 1. Then I believe we should differentiate in two cases

A) There is none obstacle in a least in one of the main diagonal our matrix.

B) There is a least one obstacle on both diagonals.

We will deal with the first case for now.

Obviously we can place in our diagonal free of 0, a rook in any squares of the diagonal, and we cannot place no more than N, otherwise the additional rook will be checked by one of the rooks in main diagonal.

A single obstacle will not provide enough "shadow" to prevent the check by a rook on the diagonal, two obstacles are needed to provide a safe place.

We shall consider the case of two obstacles at same side of diagonal. If they were at opposite sides you cannot place any additional rook

Now there are two cases a) None of the obstacle shares equal row or column let say A(7,4) and A(5,2) that will allow us to place a rook in square A(7,2) we will call this square “SAFE”

b) The two obstacle share row or column in such case we cannot put any other rook.

So we must search for SAFE squares by comparison of the locations of every pairs of obstacles following the above strategy.

Once we got the set of SAFE squares we called S. However N+S is the best scenario for maximum amount of rooks and we must check for those those originally SAFE square that became UNSAFE when we place a rook for instance in the A(7,2).

Case B) In such case we must reduce our square matrix (NxN) by (N-k x N-k) being k the least number of obstacle in any of the diagonals · 2 years, 4 months ago

If an obstacle is 0, and a rook is 1, what would you represent the empty squares with? -1? · 2 years, 4 months ago

I will try to study your algorithm, is going to be a very busy week for me.

Upfront in the first algorithm I believe the step 3 is a hard nut to crack. So I would choose the second, if it works.

Anyway I will come back in case I got better or usefull way for tackling the problem.

Is up to you to name the empty spaces , -1 look reasonable.

The minus sign will provide a quick way to identify them.

I sometimes use a prime number so is any multiplication happen I can keep a trace. Good luck · 2 years, 4 months ago

I will definitely go over this problem . While I am doing so , let me invite some Brilliant Coders into this discussion .

I see that Agnishom and Aditya have already been mentioned . · 2 years, 4 months ago

will surely look forward to it.... just need time.. as JEE on heads currently... (sigh) · 2 years, 4 months ago

@Alladin Sjebrnakov Hmm, It's 1:20 am at my place.. so I'll leave here what comes to mind as of now. Will try to do this later sometime.

The rooks can attack each other only if they face each other in a straight line with no obstacles between them.

First we will do the easier case, the case when the rooks are not in the same straight line in the first place. In this case, observe that the rooks must and will occupy diagonal corners of a rectangle formed by the squares of the chessboard. All we have to do is to find number of rectangles(squares inclusive) formed by the squares of the chessboard and multiply it by 2(since there are two pairs of opposite corners) then subtract the cases when we have a blocked square in one of the corners where we supposed that a rook could be placed. I think an algorithm to do this can be devised... but we have one big problem due to a relatively small thing: two obstacles being on the same line. This will cause huge troubles.. I can feel it.. Please do post your Ideas also.

@Agnishom Chattopadhyay @Aditya Raut · 2 years, 4 months ago