Non-attacking rook placements on crossword grids

Abstract

We introduce the notion of a non-attacking rook placement on a crossword grid. A crossword grid is a collection of white squares (which comprise across and down words) and black squares (which separate the words), and a complete non-attacking rook placement on such a grid is a subset of white squares which intersects every across and every down word exactly once. We prove an upper bound on the number of rook placements that a general grid can admit. We then study sparse grids in which no two black squares share an edge and show that rook placements on certain sparse grids correspond bijectively to alternating sign matrices with prescribed −1 entries. Specializing further to permutation grids, we prove that every permutation grid admits at least one rook placement, and characterize the permutations whose grids admit exactly one placement in terms of the Robinson--Schensted correspondence. Throughout, we pose a variety of conjectures and open questions.

Maximizing Crossword Grids with a Fixed Minimum Clue Length
Kelly Isham, Abigail Schnitzer
arXiv2 Nov 2026PreprintCC BY-NC-SA 4.0Full textCombinatorics & discrete mathematicsarXiv
Rook characters as symmetric functions
Rosa Orellana, Alexander N. Wilson, Mike Zabrocki
arXiv8 Sep 2026PreprintCC BY 4.0Full textAlgebra & number theory Combinatorics & discrete mathematicsarXiv
Hotplug Coded Caching: Uncoded versus Row-Wise Coded Placements
Daniela Tuninetti
arXiv2 Nov 2026PreprintCC BY 4.0Full textGeneral mathematicsarXiv
A flux form semi lagrangian scheme for the transport equation on reduced 2D grids
Clément Lasuen, Fabrice Voitus
HAL23 Oct 2026PreprintCC BY-NC-ND 4.0Full textGeneral mathematicsHAL
An efficient and rigorous criterion for the admissible time step of deforming grids in generalized Lagrangian and ALE methods
Yicun Zhen, Shouxian Zhu, Shipeng Mao
arXiv26 Sep 2026PreprintCC BY 4.0Full textNumerical analysis & scientific computingarXiv

Cite

BibTeX RIS

BibTeX

@misc{lewis2026nonattacking,
  title = {{Non-attacking rook placements on crossword grids}},
  author = {Joel Brewster Lewis and Robert Won},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.03081},
  eprint = {2609.03081},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.03081},
}

RIS

TY  - UNPB
TI  - Non-attacking rook placements on crossword grids
AU  - Joel Brewster Lewis
AU  - Robert Won
PY  - 2026
DA  - 2026/09/02
PB  - arXiv
DO  - 10.48550/arxiv.2609.03081
UR  - https://arxiv.org/abs/2609.03081
AB  - We introduce the notion of a non-attacking rook placement on a crossword grid. A crossword grid is a collection of white squares (which comprise across and down words) and black squares (which separate the words), and a complete non-attacking rook placement on such a grid is a subset of white squares which intersects every across and every down word exactly once. We prove an upper bound on the number of rook placements that a general grid can admit. We then study sparse grids in which no two black squares share an edge and show that rook placements on certain sparse grids correspond bijectively to alternating sign matrices with prescribed −1 entries. Specializing further to permutation grids, we prove that every permutation grid admits at least one rook placement, and characterize the permutations whose grids admit exactly one placement in terms of the Robinson--Schensted correspondence. Throughout, we pose a variety of conjectures and open questions.
ER  -

Abstract

Related

Cite