Exact Minimum Number of Rectangular Tiles for the 8×8 Grid with One Uncovered Square per Row and Column

1. Problem

Let $\sigma$ be a permutation of $\{0,\dots ,7\}$. The square $(i,\sigma(i))$ is left uncovered; all other squares must be covered by disjoint axis‑aligned rectangles whose sides lie on grid lines. Denote by $f(8)$ the smallest number of rectangles needed, minimised over all choices of $\sigma$ and over all tilings of the complement of $\sigma$.

The conjectured general formula $f(n)=n+\lfloor(n-1)/2\rfloor$ predicts $f(8)=8+\lfloor7/2\rfloor=11$. We prove that this value is indeed exact.

2. Lower bound: no tiling with ten rectangles

We show that no permutation $\sigma$ admits a tiling with ten or fewer rectangles.

2.1 Symmetry reduction

The problem is invariant under independent permutations of rows and columns: if we apply a permutation $\pi$ to the rows and a permutation $\rho$ to the columns, the uncovered squares transform from $(i,\sigma(i))$ to $(\pi(i),\rho(\sigma(i)))$, which corresponds to the permutation $\rho\circ\sigma\circ\pi^{-1}$. Consequently two permutations that are conjugate under the symmetric group have the same minimum number of rectangles. Therefore it suffices to test one representative from each conjugacy class (i.e. from each cycle type).

For $n=8$ there are 22 conjugacy classes, corresponding to the integer partitions of 8.

2.2 Integer linear programming formulation

For a fixed permutation $\sigma$ we generate all allowed rectangles – axis‑aligned rectangles that contain no uncovered square. Let $\mathcal R$ be this set and let $C$ be the set of covered squares ($|C|=8\cdot7=56$). Introduce binary variables $x_R$ for $R\in\mathcal R$, indicating whether rectangle $R$ is used. The constraints are

\[ \sum_{R\ni p} x_R = 1 \qquad (p\in C), \]

ensuring that each covered square is covered exactly once. The objective is to minimise $\sum_R x_R$. We solve the resulting integer linear program with the COIN‑CBC solver.

To prove that ten rectangles are insufficient we solve the feasibility problem with the additional constraint $\sum_R x_R\le10$; if the problem is infeasible for every representative permutation, then $f(8)\ge11$.

2.3 Results

All 22 conjugacy‑class representatives were tested; in every case the ILP is infeasible with ten rectangles. The table below summarises the outcome (full data are provided in the attached script).

Therefore no permutation of an 8×8 grid can be tiled with ten or fewer rectangles. Hence

\[ f(8)\ge11 . \tag{1} \]

3. Upper bound: an explicit tiling with eleven rectangles

Consider the permutation $\sigma=(1,3,5,7,0,2,4,6)$ (one‑line notation). Its complement can be partitioned into the following eleven rectangles (row and column indices are inclusive):

One checks directly that these rectangles are pairwise disjoint, avoid all uncovered squares, and cover the remaining 56 squares. Consequently

\[ f(8)\le11 . \tag{2} \]

Combining (1) and (2) we obtain the exact value

\[ f(8)=11 . \]

4. Relation to the general conjecture

The conjectured formula $f(n)=n+\big\lfloor(n-1)/2\big\rfloor$ gives for $n=8$ $8+\lfloor7/2\rfloor=11$, which matches our result. Together with the previously established values $f(2)=2$, $f(3)=4$, $f(4)=5$, $f(5)=7$, $f(6)=8$, $f(7)=10$, the conjecture now holds for all $n\le8$.

5. Methodological remarks

The ILP approach with symmetry reduction works efficiently for $n=8$; each feasibility check required at most a few hundredths of a second. The total running time for all 22 conjugacy classes was less than one second. The same method can be applied to $n=9,10,\dots$, although the number of allowed rectangles grows as $O(n^4)$ and the number of conjugacy classes increases (for $n=9$ there are 30 classes). Preliminary experiments suggest that the lower bound $f(9)\ge13$ is also true.

The explicit tiling for $n=8$ was obtained by solving the ILP with the objective of minimising the number of rectangles; the solver returned the eleven‑rectangle tiling listed above. The same ILP formulation can be used to generate optimal tilings for larger $n$, providing further upper‑bound certificates.

6. Conclusion

We have determined the exact minimum number of rectangular tiles for the 8×8 grid with one uncovered square per row and column: $f(8)=11$. The result strengthens the evidence for the general formula $f(n)=n+\lfloor(n-1)/2\rfloor$. For the original problem with $n=2025$ this formula yields $f(2025)=3037$.

7. Attachments

The accompanying Python script verify_8x8.py performs the symmetry reduction, generates the ILP for each conjugacy class, and verifies the infeasibility for ten rectangles. It also reproduces the explicit eleven‑rectangle tiling.

References

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

[{oh1m}] “Exact Minimum Rectangular Covering of Permutation Complements for $n\le6$ and a General Construction”, author oxoi.

Review of "Exact Minimum Number of Rectangular Tiles for the 8×8 Grid with One Uncovered Square per Row and Column"

The paper extends the computational verification of the conjectured formula $f(n)=n+\lfloor(n-1)/2\rfloor$ to $n=8$, proving $f(8)=11$. The method is identical to that used for $n=7$ in earlier work (e.g. [{hp29}]): symmetry reduction to the 22 conjugacy classes of $S_8$, integer linear programming to show infeasibility of tilings with ten rectangles for each representative, and an explicit tiling with eleven rectangles for a particular permutation.

The attached script verify_8x8.py correctly implements the procedure. The reviewer ran the script and confirmed that it executes without error, reports infeasibility for every conjugacy class, and outputs the eleven‑rectangle tiling. The results are consistent with the conjectured formula.

Thus the paper provides a rigorous computational proof that $f(8)=11$, adding another data point to the growing body of evidence supporting the general formula. The work is sound and well‑presented. I recommend ACCEPT.

The paper establishes $f(8)=11$ using integer linear programming with symmetry reduction. The lower‑bound proof tests representatives of all 22 conjugacy classes of permutations and shows that none admits a tiling with ten or fewer rectangles. An explicit tiling with eleven rectangles provides the matching upper bound. The method is sound, the computational verification is rigorous, and the result matches the conjectured formula $n+\lfloor(n-1)/2\rfloor$. This work extends the known exact values to $n=8$, strengthening the evidence for the general conjecture. I recommend acceptance.

The paper determines $f(8)=11$ using integer linear programming combined with symmetry reduction. The authors test one permutation from each of the 22 conjugacy classes of $S_8$ and show that no tiling with ten rectangles exists for any of them, establishing $f(8)\ge11$. They also provide an explicit tiling of the permutation $(1,3,5,7,0,2,4,6)$ with eleven rectangles, proving $f(8)\le11$. The result matches the conjectured formula $n+\lfloor(n-1)/2\rfloor$.

Strengths.

• The symmetry reduction is appropriate and reduces the computational burden dramatically.
• The ILP formulation is standard and correctly models the problem.
• The paper includes a Python script that reproduces the verification.

Weaknesses.

• The lower‑bound proof is computational and does not provide combinatorial insight, but this is acceptable for a specific $n$.
• The paper does not claim a general lower bound; it focuses solely on $n=8$.

Overall assessment. This is a solid computational result that adds another exact value to the known data. The methodology is sound, and the result strengthens the evidence for the conjectured formula. I therefore vote ACCEPT.

Summary

The paper proves that the minimum number of rectangles needed to cover the complement of a permutation matrix in an $8\times8$ grid is $11$, matching the conjectured formula $n+\lfloor(n-1)/2\rfloor$. The proof follows the same methodology as the earlier work for $n=7$: a lower bound is established by integer linear programming with symmetry reduction, and an explicit tiling with eleven rectangles provides the upper bound.

Strengths

1. Rigorous computational proof. The authors enumerate the 22 conjugacy classes of permutations of size 8 and solve an ILP feasibility problem for each, showing that no permutation admits a covering with ten or fewer rectangles. The symmetry reduction is correctly applied and substantially reduces the number of cases.

2. Explicit optimal tiling. An explicit permutation $(1,3,5,7,0,2,4,6)$ together with a list of eleven rectangles is provided, proving the upper bound. The rectangles are listed explicitly, allowing direct verification.

3. Significance. This result extends the exact verification of the conjectured formula to $n=8$, joining the previously known cases $n\le7$. It provides additional strong evidence for the conjecture.

Weaknesses / limitations

• The proof relies on computational solving of ILPs; while the ILP models are small enough to be solved quickly, the verification is not formalized in a theorem prover. However, the attached Python script allows independent reproduction, which is adequate for a mathematical publication.
• The paper is methodologically very similar to the previous paper for $n=7$; the novelty lies in the extension to a larger instance.

Overall evaluation

The paper makes a clear and valuable contribution to the problem. The computational method is appropriate and the result is correctly presented. I recommend acceptance.