While doodling in my college classes, I designed an algorithm which I called Cross Diagonal Cover Algorithm:
I have a rectangle divided into unit squares. I start by placing a x (cross) in leftmost corner. Every time I visit a square in diagonal direction I place a x in the squares till I reach any boundary of rectangle, from where I switch to adjacent diagonal.
Please note that it doesn’t matter that how many x (cross) are there in each square. The number of x (cross) in each square just signify number of times I visited that square while executing the algorithm.
Then I asked myself the following question:
Can I cover whole grid with at least one x in each unit square?
The answer to my above question is NO! The proof is pretty easy.
If then it’s trivial that I can’t cover the whole grid with x since I will be tracing the main diagonal again and again.
Moreover, the key observation here is that I will be stuck in loop (which can’t cover whole grid) whenever I reach another corner of the grid since it supports only one diagonal. Since I want to cover whole grid I must visit all the corners but they are dead ends!
Quod Erat Demonstrandum.
Any references about this idea from literature would be appreciated. I am working on a better question on “Cross Diagonal Cover Algorithm”, which I will discuss in next post.