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

Author

Nicholas Tran, Jul 14 2020

Keywords

• nonn
• hard
• more

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.

Examples

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

Links

• V. Ilmer, Ship City.
• Nicholas Tran, Solution in ASP.