# A Rook's Territory in the Chessboard

Shade 32 cells, four on each row and column, of an 8 x 8 blank chessboard (all its cells originally white) so that a rook sitting on any shaded cell can reach any other shaded cell, moving just along other shaded cells.

If not possible, what is the size of the largest square board on which this can be done, i.e. shading four cells of each row and column creating a connected territory for a rook lying on any of its cells.

Problem based on a similar one communicated by Stan Wagon (http://stanwagon.com/pow/), who asks whether 3 cells of each row and column can be so shaded in a n x n (n > 4) board.

• The problem with 3 cells and $n>4$ is The American Mathematical Monthly problem 12137 (October 2019). May 19, 2020 at 22:08
• I had trouble understanding the problem because I imagine the rook jumping from the start to the destination cell. You should make clear that all the cells between the start and the end of each move must be shaded. The shaded region must be orthogonally connex. May 19, 2020 at 22:28
• @BernardoRecamánSantos math.lsu.edu/~mahlburg/teaching/handouts/2018S-3903/12008.pdf May 20, 2020 at 3:30
• Connex doesn't seem to be the right term, according to Wikipedia's definition. "Orthogonally connected" probably gets the point across well enough. May 20, 2020 at 13:12
• Sorry, I thought it was a typo like othogonally. 😉 May 20, 2020 at 13:24

I started with this:

 - - X X X X - -
- - X X X X - -
X X - - - - X X
X X - - - - X X
X X - - - - X X
X X - - - - X X
- - X X X X - -
- - X X X X - -

Pushed things this way and that, ended up with this:

 - - - X X X - X
X - X X - - - X
X X X - - - - X
X - X - - - X X
X X - - X - X -
- X - - X X X -
- X X X - X - -
- - - X X X X -

Similarly, on 9x9:

 - - - X X X - - X
- - X X X - - - X
X X X - - - - - X
X X - - - - - X X
X - - - - X X X -
X X - - - X - X -
- X X - - - X X -
- - X X X - X - -
- - - X X X X - -

And on 10x10:

 - - X X X X - - - -
- - - X X X X - - -
- - - - X - X X - X
X - - - - - - X X X
X X - - - - - - X X
X X - - - - - - X X
X X - - - - - X X -
- X X - - - X X - -
- - X X - X X - - -
- - X X X X - - - -

It took me a while to get there, but that one suggests an emerging pattern.

And here is an expandable solution for any $$2n\times 2n$$ grid.

• Great! Is this the largest square board on which this can be done? May 19, 2020 at 19:07
• @Bernardo 9x9 and 10x10 Is there a limit? May 19, 2020 at 22:12
• @Daniel Matias Don´t know! May 19, 2020 at 22:17
• @Bernardo $2n\times 2n$, unlimited. Probably something similar for $2n+1$, but I'm done for now. May 20, 2020 at 0:47

Here's an expandable solution for $$n\ge 5$$ (even or odd):

• Looks good for all $n\ge 5$ May 20, 2020 at 15:53
• Truly beautiful!! May 20, 2020 at 16:07
• n = 4 is trivial; fill the grid. n < 4 is trivially impossible. May 20, 2020 at 19:30