Project Euler Forum

The question shows a 2x2=4 square grid. Am I right to assume that the solution to the 2x2 is based on 3x3=9 sides. If so then can you confirm that the solution to the 20x20 question is based on 21x21 sides.

Please don't start a new topic for a problem if there already exists one.

andy7788 wrote:The question shows a 2x2=4 square grid. Am I right to assume that the solution to the 2x2 is based on 3x3=9 sides. If so then can you confirm that the solution to the 20x20 question is based on 21x21 sides.

No, that assumption is not needed. There is no need to look at a 21X21 grid to get the number of paths in a 20X20 grid.

andy7788 wrote:The question shows a 2x2=4 square grid. Am I right to assume that the solution to the 2x2 is based on 3x3=9 sides. If so then can you confirm that the solution to the 20x20 question is based on 21x21 sides.

It depends what you mean by "sides". If you mean the edges of the squares, then there aren't 9 in the 2x2 grid. There are 12. It is true that the 2x2 grid has 3 vertical lines and 3 horizontal lines, but multiplying those doesn't give the number of anything that I'd call "sides".

The only thing I can see 9 of in the 2x2 grid are the vertices, where those vertical and horizontal lines meet. The 20x20 grid will have 21 vertical lines, 21 horizontal lines, and 21x21 = 441 vertices. And 20x20 = 400 squares, of course.

I have a feeling that this problem could be solved easily without checking all the routes, so I've been trying to come up with a formula for a n*n grid, with no success up to now.