[Community Puzzle] Harmless Rooks

Puzzles
#1

Hello,

I was trying to solve “Harmless Rooks”:

I was wondering if someone is getting better scores than required?
Size 5 -> ok
Size 8 -> ok
Size 16 -> ok
Size 30 -> I got 176 on 165
Size 50 -> 504/484
Size 99 -> 2000/1911
Size99 -> 2109/2018
Size99 -> 2166/2076
Size1 -> ok

I`ve triple checked my logic and it looks ok.

#2

Hi, completely independently of your logic, have you triple checked your results (it’s easier to check a solution than to solve a case and should reveal the problem)? For instance, can you post here, or by PM to me if you prefer, your actual solution (rooks positions) for the Size 30 testcase?

1 Like
#3

damn, you’re fast :wink:
I have just printed out my result to look for errors and I have found some…
fate of a rookie :stuck_out_tongue:
I was my mistake, which i am hoping to repair :wink: thank you for quick reply anyway :wink:

#4

I can not solve this puzzle
The algorithm I implemented does not fully work.
2 tests with the size of 99 cells failed, the remaining tests pass successfully
Somewhere my logic is broken :confused:

#5

Maybe I can help if you explain your current logic in PM (to avoid spoil).

#6

Same here, I keep missing the result from a few rooks with the 99 tests… Arf

#7

hello all,
My solution works but it is too sloooow. I do not see how to optimize this problem.
I do not want the solution but can you send me some wikipedia links about this type of optimization.
Thanks

#8

hello, i got test until size 50 working, but none for the 99…

My algo sort the free chess cases that have the more little impact on the board and not attacking another rock, it gives me:
size 99: 1905 / 1911
size 99: 2013 / 2018
size 99: 2075 / 2076
Can you give a clue ?
thx

#9

@never-again I answered in PM to avoid spoiling too much here.

1 Like
#10

Hello everyone.

I tried this puzzle with a strategy that I knew was possibly not optimal, and it indeed seems that it doesn’t work, but I don’t really understand why (I can’t find an easy configuration where it doesn’t work). My strategy is as follows:

  • I begin by computing for each square the number of squares a rook placed here would attack
  • While there remains some unattacked squares, I place a rook on the square attacking the minimum number of not-already-attacked squares.

On the first example, the iterations give the following results (R means a rook is there, A means it is attacked by at least one rook, so we can’t place another one there and E means it is an empty square where we could possibly place another rook):

  • Step 1: Add a rook at position (0,3)
    [[‘X’ ‘X’ ‘A’ ‘R’ ‘X’]
    [‘E’ ‘E’ ‘E’ ‘A’ ‘X’]
    [‘X’ ‘X’ ‘E’ ‘X’ ‘E’]
    [‘X’ ‘E’ ‘E’ ‘E’ ‘E’]
    [‘E’ ‘E’ ‘E’ ‘E’ ‘E’]]

  • Step 2: Add a rook at position (1,0)
    [[‘X’ ‘X’ ‘A’ ‘R’ ‘X’]
    [‘R’ ‘A’ ‘A’ ‘A’ ‘X’]
    [‘X’ ‘X’ ‘E’ ‘X’ ‘E’]
    [‘X’ ‘E’ ‘E’ ‘E’ ‘E’]
    [‘E’ ‘E’ ‘E’ ‘E’ ‘E’]]

  • Step 3: Add a rook at position (2,2)
    [[‘X’ ‘X’ ‘A’ ‘R’ ‘X’]
    [‘R’ ‘A’ ‘A’ ‘A’ ‘X’]
    [‘X’ ‘X’ ‘R’ ‘X’ ‘E’]
    [‘X’ ‘E’ ‘A’ ‘E’ ‘E’]
    [‘E’ ‘E’ ‘A’ ‘E’ ‘E’]]

  • Step 4: add a rook at position (2,4)
    [[‘X’ ‘X’ ‘A’ ‘R’ ‘X’]
    [‘R’ ‘A’ ‘A’ ‘A’ ‘X’]
    [‘X’ ‘X’ ‘R’ ‘X’ ‘R’]
    [‘X’ ‘E’ ‘A’ ‘E’ ‘A’]
    [‘E’ ‘E’ ‘A’ ‘E’ ‘A’]]

  • Step 5: Add a rook at position (3,1)
    [[‘X’ ‘X’ ‘A’ ‘R’ ‘X’]
    [‘R’ ‘A’ ‘A’ ‘A’ ‘X’]
    [‘X’ ‘X’ ‘R’ ‘X’ ‘R’]
    [‘X’ ‘R’ ‘A’ ‘A’ ‘A’]
    [‘E’ ‘A’ ‘A’ ‘E’ ‘A’]]

  • Step 6: Add a rook at position (4,1)
    [[‘X’ ‘X’ ‘A’ ‘R’ ‘X’]
    [‘R’ ‘A’ ‘A’ ‘A’ ‘X’]
    [‘X’ ‘X’ ‘R’ ‘X’ ‘R’]
    [‘X’ ‘R’ ‘A’ ‘A’ ‘A’]
    [‘R’ ‘A’ ‘A’ ‘A’ ‘A’]]

So I find 6 rooks as expected.

BUT
for the size 16, I find 46 rooks instead of 47 and for the first and third size 99, I find respectively 1907 and 2074 instead of 1911 and 2076. All the other example work (including the second size 99).

Does anyone see an example where this method doesn’t work and why?

#11

I have already helped several people in PM with this puzzle. They all seem to have the same problem and I almost always give the same answer. So I think it might be time to publish a part of it here to help anyone having trouble.

Disclaimer: It is recommended that you only unfold the following if you have tried the problem and have troubles with a greedy strategy (picking squares to place a rook one at a time).

Spoiler

Let’s talk about graph theory for one second. Consider the graph G whose vertices are the free cells and whose edges connect cells that are threatening each other (so cells on the same line/column without obstacles in between). Seeing things that way, what we are looking for is called a Maximum (Size) Independent Set (MSIS, beware not to confuse with Maximal Independent Sets that are only maximum for the inclusion): A set of vertices (i.e. cells) of maximum size such that no two vertices in the set are neighbors (i.e. no two cells are threatening each other). That is most likely what one is trying to compute using a greedy/heuristics approach: One picks vertices in an order induced by a certain score attributed to them.

Unfortunately:

  1. This approach can work well on small graphs, yet is has no good reason to work in general as it is local: the score given to each cell most certainly only depends on its neighborhood at a certain radius in the graph G (i.e. the score of a cell depends on its neighbors, possibly the neighbors of its neighbors, possibly a bit more, but it stops at a finite distance in the graph). This does not reflect the actual global topology of the graph, while MSIS actually are global objects.
  2. All such greedy/heuristics approaches known to the MSIS problem are approximations (sometimes good ones) but not optimal.
  3. And actually, there even is no efficient approach known to the MSIS problem (it is NP-hard)!

Long story short: Seeing this rooks problem in terms of MSIS is a trap, it actually complicates things!

3 Likes
#12

@Andeagi My previous post explains a few things worth knowing about the kind of strategy you used here. If you send me your code in PM, I can try to find a simple counter-example (but there might not be a very simple one though: as explained, the larger the grid, the more your strategy is likely to fail).

#13

Thanks for your very quick answer. I knew there was no reason for my approach to be optimal, but I didn’t expect it to give results so close to the actual best configuration if it wasn’t, so I just wanted to make sure the issue was coming from the algorithm itself and not the way I implemented it.

I’ll go take a look at your other post to try and solve this problem for real now! :smiley:

#14

@Andeagi what is funny is that i had the same approach, but it seems that our results differ … :smiley: i m still pending this one …

#15

I have also struggled with little differences in results in deductive approach.
Large tests are too big to find what was the issue.
What helped me was small, custom test like this, where human brain can see the logic:

X..X
....
....
X..X

and that

XX..XX
X....X
......
X....X
XX..XX
2 Likes
#16

I wonder how can I get a insight of the solution. Is there any relevant field or algorithm I can learn before trying to solve this puzzle?

#17

Have you looked at the spoiler (in a collapsible block) in one of my messages above?

#18

Hi @Niako,
Like some others on this forum, I’m stucked with this puzzle.
The answers i get are ok for “small” boards but are wrong for 99x99 boards, where I always miss a few rooks.
My original algorithm chose squares for rooks one by one : for a position, i identify a square that have the lowest number of squares “attacked” to place the rook here…
As some rooks are missing, I’ve tried to improve the algorithm : when multiple squares are possibles (multiple possibilities for the lowest), i select in priority the square far from the center, but I still have wrong results.

I’ve read the other messages here on the forum about MSIS (a trap you said ?) or picking the square one by one (also wrong algo if I understood well)… so i’m stuck.

Can you help me to go further ?
Thanks for proposing this puzzle anyway, it’s a very nice one :slight_smile:

1 Like
#19

@Alexand_NO I answered in PM to avoid spoiling too much here.

1 Like
#20

After more than 1 month on this puzzle, i finally solved it :grinning:
It was a good opportunity to learn and apply some graph theory algorithms i didn’t know at first :slight_smile:
Thanks a lot @Niako for this puzzle and for your help !

2 Likes