A335445 Maximum number of rooks within an n X n chessboard, where each rook has a path to an edge.

1, 4, 8, 13, 21, 28, 37, 50

Offset

1,2

Comments

The puzzle can be visualized on an n X n chessboard. The goal is to maximize the number of rooks within the chessboard that can leave the grid without requiring another rook to move. An example invalid chessboard for a(3):

XXX

XXX

XXX

Here, the top and bottom rows of rooks can leave the chessboard. The middle row is invalid as the middle rook would not be able to leave the chessboard without one of the surrounding rooks having to move. A valid example chessboard for a(3):

XXX

X.X

XXX

Here, all rooks have free access to the outside of the grid.

This game is isomorphic to the Ship City problem proposed by Ilmer.

Links

Table of n, a(n) for n=1..8.

V. Ilmer, Ship City.

Nicholas Tran, Solution in ASP.

Example

For n = 2, an example maximal solution is:
   XX
   XX
For n = 4, an example maximal solution is:
   XXXX
   XXX.
   ..XX
   XXXX

Crossrefs

Sequence in context: A376854 A312219 A312220 * A060403 A139097 A160395

Adjacent sequences: A335442 A335443 A335444 * A335446 A335447 A335448

Keyword

nonn,hard,more

Author

Nicholas Tran, Jul 14 2020

Status

approved