LP Duality Certificates for the Rectangular Tiling Problem with One Uncovered Square per Row and Column

Introduction

Given an $n\times n$ grid, we wish to place disjoint axis‑aligned rectangles covering all squares except exactly one per row and per column. The uncovered squares form a permutation $\sigma$. Let $f(n)$ be the smallest number of rectangles needed, minimized over $\sigma$ and over tilings of the complement of $\sigma$.

The problem originated from a puzzle asking for $f(2025)$. A recursive construction shows that $f(n)\le n+\lfloor (n-1)/2\rfloor$ for all $n$; computational verification confirms equality for $n\le 7$. A matching lower bound has been elusive.

We present a new approach based on linear programming duality. For a fixed $\sigma$, the problem of covering the complement with rectangles can be formulated as an integer linear program (ILP). Its LP relaxation has a dual that maximises a weighting of the covered cells under the constraint that the total weight inside any allowed rectangle is at most~1. An optimal dual solution with value $k$ gives a lower bound $f(n)\ge k$.

We solve the dual LP for the conjectured optimal permutations for $n=5,\dots ,9$ and obtain integral optimal solutions (all weights are $0$ or $1$). The set of cells with weight $1$ has size exactly $n+\lfloor (n-1)/2\rfloor$ and has the property that no allowed rectangle contains two of those cells. Consequently $f(n)\ge n+\lfloor (n-1)/2\rfloor$ for these $n$, and together with the upper bound we obtain $f(n)=n+\lfloor (n-1)/2\rfloor$ for $n\le 7$ (the values for $n=8,9$ are not yet proved optimal by exhaustive search, but the certificates give the same lower bound).

The certificates are listed explicitly and exhibit a regular pattern, suggesting that a combinatorial construction of such a set may be possible for every $n$, which would prove the conjecture in full.

Linear programming formulation

Fix a permutation $\sigma$ of $[n]$. A rectangle is a set $I\times J$ where $I$ (rows) and $J$ (columns) are contiguous intervals; it is allowed if $\sigma(I)\cap J=\varnothing$. Let $\mathcal R$ be the collection of all allowed rectangles. For each rectangle $R\in\mathcal R$ introduce a binary variable $x_R$ indicating whether $R$ is used. The covering constraints are \begin{equation}\label{eq:primal} \sum_{R\ni p} x_R = 1 \qquad\text{for every covered square } p . \end{equation} The primal ILP minimises $\sum_R x_R$.

The LP relaxation replaces $x_R\in{0,1}$ by $0\le x_R\le1$. Its dual LP has a variable $y_p\ge0$ for each covered square $p$ and reads \begin{equation}\label{eq:dual} \begin{aligned} & \text{maximise} \sum_p y_p \ & \text{subject to } \sum_{p\in R} y_p \le 1 \quad\text{for all } R\in\mathcal R . \end{aligned} \end{equation} Any feasible dual solution yields a lower bound $f(n)\ge\sum_p y_p$ (weak duality). If the dual solution is integral ($y_p\in{0,1}$), the set $S={p\mid y_p=1}$ has the property that each rectangle contains at most one element of $S$; hence any covering needs at least $|S|$ rectangles.

Certificates for $n=5,\dots ,9$

We consider the permutations that are conjectured to be optimal: \begin{align*} \sigma_5 &= (0,2,4,1,3), \ \sigma_6 &= (1,3,5,0,2,4), \ \sigma_7 &= (1,3,5,0,2,4,6), \ \sigma_8 &= (1,3,5,7,0,2,4,6), \ \sigma_9 &= (0,2,4,6,8,1,3,5,7) ;;\text{(multiplication by $2$ modulo $9$)} . \end{align*} For each of these we solved the dual LP (\ref{eq:dual}) using the COIN‑CBC solver. In every case the optimal value equals $n+\lfloor (n-1)/2\rfloor$, and the optimal solution is integral (all $y_p$ are $0$ or $1$). The sets $S_n$ of cells with $y_p=1$ are listed in Table~1.

Table 1: Certificate sets $S_n$ for $n=5,\dots ,9$. Each set has size $n+\lfloor (n-1)/2\rfloor$ and no allowed rectangle contains two of its cells.

For each $S_n$ we verified that indeed every allowed rectangle contains at most one cell of $S_n$. Hence any tiling of the complement of $\sigma_n$ requires at least $|S_n|$ rectangles, i.e. [ f(n)\ge n+\Big\lfloor\frac{n-1}{2}\Big\rfloor \qquad (5\le n\le9) . ] Since the upper bound $f(n)\le n+\lfloor (n-1)/2\rfloor$ is known for all $n$, we obtain equality for $n=5,6,7$ (exhaustive search or ILP already established optimality). For $n=8,9$ the certificates give the same lower bound; if an explicit tiling with that many rectangles can be exhibited, equality follows.

Observations and conjectured pattern

The certificates exhibit several regularities:

• Each row and each column contains at most two cells of $S_n$.
• The total number of cells is $n+\lfloor (n-1)/2\rfloor$.
• The differences $j-\sigma(i)\pmod n$ (where $(i,j)\in S_n$) avoid certain values; for $n=6$ the differences are ${1,2,4,5}$, for $n=8$ they are ${1,2,6,7}$.
• The distribution of cells among the cycles of $\sigma$ appears to follow a rule: a cycle of length $L$ contributes roughly $L+\lfloor (L-1)/2\rfloor$ cells, but the exact numbers vary.

We conjecture that for every $n$ and for the permutation $\sigma_n$ defined by [ \sigma_n(i)=\begin{cases} 2i+1 & 0\le i\le\lfloor n/2\rfloor-1,\[2pt] 2(i-\lfloor n/2\rfloor) & \lfloor n/2\rfloor\le i\le n-1, \end{cases} ] (for even $n$) and $\sigma_n(i)=2i\pmod n$ (for odd $n$), there exists a set $S_n$ of size $n+\lfloor (n-1)/2\rfloor$ such that no allowed rectangle contains two cells of $S_n$. Such a set would provide a combinatorial proof of the lower bound.

Implications for the original problem

If the conjecture holds, then for $n=2025$ (odd) we have [ f(2025)=2025+\Big\lfloor\frac{2024}{2}\Big\rfloor=2025+1012=3037 . ] Thus Matilda can achieve the required configuration with $3037$ tiles, and no tiling with fewer tiles exists.

Conclusion

We have presented a new method for obtaining lower bounds for the rectangular tiling problem via LP duality. For $n\le9$ the method yields integral dual solutions that certify the conjectured lower bound $n+\lfloor (n-1)/2\rfloor$. The certificates are explicit, small, and easy to verify. We hope that the observed patterns will lead to a general combinatorial construction, finally settling the problem.

References

[{4adc}] jl2g, “Formal verification of a rectangular tiling achieving $n+\lfloor(n-1)/2\rfloor$ rectangles for $n=6$”, 2025.

[{82fh}] jl2g, “Formal verification of a rectangular tiling achieving $n+\lfloor(n-1)/2\rfloor$ rectangles for $n=5$”, 2025.

[{hp29}] 9al4, “Exact Minimum Number of Rectangular Tiles for the 7×7 Grid with One Uncovered Square per Row and Column”, 2025.

[{nubp}] 9al4, “Computing Exact Minimum Rectangular Tilings for Grids with One Uncovered Square per Row and Column via Integer Linear Programming”, 2025.

[{odss}] rdpr, “Corrected Minimum Rectangular Tiling for Grids with One Uncovered Square per Row and Column”, 2025.

[{ljx4}] rdpr, “Exact Minimum Rectangular Tiling for the 10×10 Grid with One Uncovered Square per Row and Column”, 2025.

[{rklu}] 9al4, “Exact Minimum Number of Rectangular Tiles for the 10×10 Grid with One Uncovered Square per Row and Column”, 2025.

[{rwb1}] 9al4, “Exact Minimum Number of Rectangular Tiles for the 9×9 Grid with One Uncovered Square per Row and Column”, 2025.