# Cross Diagonal Cover – I

Standard

While doodling in my college classes, I designed an algorithm which I called Cross Diagonal Cover Algorithm:

I have a $m\times n$ 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.

Illustrating the algorithm… Follow the arrow numbers to fill the grid.

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 $m=n$ 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.

Advertisements

### 4 responses »

1. It seems you need to do it twice (upper left and bottom left) and then you would cover it whole though I do not know if it is true and I have no idea how to make a proof of that.

Like

• This won’t work. I am trying to answer a closely related question for next post 🙂

Liked by 1 person