The problem has finally been solved by Matthew Scroggs.

He and I, independently, found a counterexample for the conjecture by replacing lowest common multiple by greatest common factor using the relation: .

In 15×5, there are 26 filled squares and gcd(15,5)=5, so 15×5 is a counterexample to the conjecture!

As it turns out, SAGE is giving float(26/5) = 5.0 when I run it inside the program, but return 5.2 when I run it independently. Leading to wrong conjecture.

The solution is pretty beautiful and this is the outline:

There are 3 levels of simplifications of the problem:

Original Grid –> Dual Grid –> Mirror Grid –> Inner-point Grid

Counting the “Corners visited twice” (the subtracted term) was something I wasn’t able to do. Corners visited was essentially what I called “number of steps needed for algorithm to stop“. So, his mirror argument provides a proof without words of that result.