Mathematicians == Magicians !
Few days back, I came across this problem in one of the mailing list. The problem is about counting the no of squares which are internally intersected by a line in a square grid of unit size.I just wanted to solve this problem somehow and did a bit of research for it. I experimented out with various solutions like using some vector algebra methods, modifying bresenham line drawing algorithm etc. But none were good enough to solve the problem. Then I found that this problem was one of the Olympiad problem in the 80s .. !!!
Solution:
If (x1,y1) and (x2,y2) are two end points of the line,
m=(x2-x1) n=(y2-y1)
The no of squares which are intersected internally by a line is
gcd(m,n)*((m+n)/gcd(m,n)-1)
Thats all !!!
Mathematicians are true Magicians :)