How many routes are there through a 20×20 grid?

Project Euler Problem 15: Starting in the top left corner of a 22 grid, there are 6 routes (without backtracking) to the bottom right corner.

How many routes are there through a 2020 grid?

If you choose to solve this problem using recusion programatically, you will end up writing a program similar to the one below.

import java.util.ArrayList;
import java.util.List;
public class FindPath {
long noOfPath;
long sizeOfBox=10;
List<String> paths = new ArrayList<String>();
long i,j;
long recursionDepth;
void edgeCrawler(long i, long j, String s){
System.out.println("Recursion level: " + recursionDepth++);
// stop when i>n && j>n
if(i==sizeOfBox){
// increment j until j>n
while(j <= sizeOfBox){
s += (i + "" + j + "-" + i + "" + j++ + ".");
}
i++;
paths.add(s);
return;
}
// stop when i>n && j>n
else if(j==sizeOfBox){
// increment i until i>n
while(i <= sizeOfBox){
s = (i + "" + j + "-" + i++ + "" + j + ".");
}
j++;
paths.add(s);
return;
}
// go right and/or left
if(i<sizeOfBox){
s += (i + "" + j + "-" + (i+1) + "" + j + ", ");
edgeCrawler(i+1, j, s);
}
if(j<sizeOfBox){
s += (i + "" + j + "-" + i + "" + (j+1) + ", ");
edgeCrawler(i, j+1, s);
}
}
public static void main(String [] args){
FindPath find = new FindPath();
find.edgeCrawler(0, 0, "");
System.out.println("No. of paths: " + find.paths.size());
}
}

This program works well for small values of n (i.e. around 10). Above that this program will hog up so much memory that you will get OutOfMemory exception.

Leave a Reply

Your email address will not be published. Required fields are marked *