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

#ComputerScience #Programming #Chess #Algorithm #Chessboard

Easy Math Editor

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.
Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

Markdown	Appears as
`italics` or `_italics_`	italics
`bold` or `__bold__`	bold
- bulleted - list	bulleted list
1. numbered 2. list	numbered list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1 paragraph 2	paragraph 1 paragraph 2
`[example link](https://brilliant.org)`	example link
`> This is a quote`	This is a quote
# I indented these lines # 4 spaces, and now they show # up as a code block. print "hello world"	# I indented these lines # 4 spaces, and now they show # up as a code block. print "hello world"

Math	Appears as
Remember to wrap math in `$` ... `$` or `\[` ... `\]` to ensure proper formatting.
`2 \times 3`	$2 \times 3$
`2^{34}`	$2^{34}$
`a_{i-1}`	$a_{i-1}$
`\frac{2}{3}`	$\frac{2}{3}$
`\sqrt{2}`	$\sqrt{2}$
`\sum_{i=1}^3`	$\sum_{i=1}^3$
`\sin \theta`	$\sin \theta$
`\boxed{123}`	$\boxed{123}$

Comments

@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

Raghav Vaidyanathan - 6 years, 2 months ago

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

@Brock Brown , @Kishlaya Jaiswal , @Vraj Mehta , @Pranjal Jain , @Harshvardhan Mehta , @Ronak Agarwal

I see that Agnishom and Aditya have already been mentioned .

A Former Brilliant Member - 6 years, 2 months ago

will surely look forward to it.... just need time.. as JEE on heads currently... (sigh)

Harshvardhan Mehta - 6 years, 2 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

Mariano PerezdelaCruz - 6 years, 2 months ago

If an obstacle is 0, and a rook is 1, what would you represent the empty squares with? -1?

Agnishom Chattopadhyay - 6 years, 2 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

Mariano PerezdelaCruz - 6 years, 2 months ago

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

Create a list containing coordinates of all empty squares.
Calculate how many squares the new rook would threaten for each element in the list.
Place the new rook in the square that threatens the least number of squares.
Delete all the squares that the new rook is threatening from the list and also the square where you placed the new rook.
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:

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

Agnishom Chattopadhyay - 6 years, 2 months ago

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

oooo _ _

ooo _ _ _

oo _ _oo

_ _ _ 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

Eilon Lavi - 6 years, 2 months ago

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

(a,y) and (x,b) are open spaces (we can still place rooks on them)
(x,y) sees both (a,y) and (x,b) (same [row] and [column])
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.

Eilon Lavi - 6 years, 2 months ago

Math	Appears as
Remember to wrap math in `\(` ... `\)` or `\[` ... `\]` to ensure proper formatting.
`2 \times 3`	$2 \times 3$
`2^{34}`	$2^{34}$
`a_{i-1}`	$a_{i-1}$
`\frac{2}{3}`	$\frac{2}{3}$
`\sqrt{2}`	$\sqrt{2}$
`\sum_{i=1}^3`	$\sum_{i=1}^3$
`\sin \theta`	$\sin \theta$
`\boxed{123}`	$\boxed{123}$