Solving the Square Path Problem up to 20×20

摘要

Given an m×n rectangular lattice, the square path problem is to find the minimum number f(m, n) of lattice points whose deletion removes all square paths from the lattice. It is known that f(n, n) is asymptotically equal to 2/7n{sup}2. However, the exact value of f(m, n) is known only for m ≤ 4 and a few other small values of m and n. We obtain the exact values of f(5, n) and f(6, n) for all n. We describe an algorithm that was able to compute all values of f(m, n) for m, n ≤ 20 in approximately 62 hours. Finally, we provide conjectures on the exact values of f(7, n), f(8, n), f(9, n), and f(10, n) for all n.