Getting all possible down- and right edge paths in a n x n grid

Question

Problem 15:
Starting in the top left corner of a 2×2 grid, there are 6 routes (without backtracking) to the bottom right corner.
How many routes are there through a 20×20 grid?

So my attempt at Problem 15 is kinda bruteforcy because I try to get permutations of all of the possible valid paths by going from right to left and changing the predecessor of the first change of direction. For example, when I have a 2x2 grid (look at the Problem 15 link graphics) the first path I'll take is right - right - down - down and the last one I'll take is down - down - right - right, which is also my termination criteria. I add the possible valid paths into a list and also use that list to determine whether the valid path has been already added or not. And to permutate a path I'll do what I've mentioned earlier: I go from right to left in my array (Which in the graphic would be the bottom right corner where the arrowhead points at) and change the first element of which the next element is different from itself. So right - right - down - down would become right - right - right - down, which is obviously invalid since you have to have the same amount of rights and downs to be able to reach the end corner. So what I thought is to make another loop going from left to right and change as many elements as needed to get a valid path. So in this example right - right - right - down becomes down - right - right - down.

Also, what I forgot is that I'm not counting the points, I'm counting the edges from top left corner to bottom right corner.

So I have already written some code, but it doesn't work at all.

package projecteuler;

import java.util.ArrayList;

public class Projecteuler {
    public static final int GRIDSIZE = 2;

    public static void main(String[] args) {
        ArrayList<boolean[]> paths = new ArrayList<>();

        paths.add(new boolean[GRIDSIZE * 2]);
        for(int i = 0; i < GRIDSIZE; i++) {
            paths.get(0)[i] = true;
            paths.get(0)[GRIDSIZE * 2 - 1 - i] = false;
        }

        boolean[] buf = paths.get(0).clone();
        printArr(buf);
        boolean tmp;
        while(!checkTerminate(paths)) {
            while(paths.contains(buf)) {
                tmp = buf[buf.length - 1];
                for(int i = buf.length - 1; buf[i - 1] != tmp && 0 < i; i--) {
                    buf[i] = !buf[i];
                    for(int j = 0; checkValid(buf) && j < i; j++)
                        buf[j] = !buf[j];
                }
            }
            paths.add(buf.clone());
            printArr(buf);
        }
        System.out.println(paths.size());
    }

    public static boolean checkTerminate(ArrayList<boolean[]> paths) {
        boolean[] endPath = new boolean[GRIDSIZE * 2];
        for(int i = 0; i < GRIDSIZE; i++) {
            endPath[i] = false;
            endPath[GRIDSIZE * 2 - 1 - i] = true;
        }
        return paths.contains(endPath);
    }

    public static boolean checkValid(boolean[] arr) {
        int countR = 0,
            countL = 0;
        for(int i = 0; i < arr.length; i++) 
            if(arr[i])
                countR++;
            else
                countL++;

        return countR == countL;
    }

    public static void printArr(boolean[] arr) {
        for(int i = 0; i < arr.length; i++)
            System.out.print(arr[i] ? "right " : "down ");
        System.out.println();
    }
}

It somehow doesn't change anything anywhere.

right right down down 
right right down down 
right right down down 
right right down down ...

and so on is all it's outputting. It seems that the code simply doesn't permutate my path, but also doesn't get stuck in any of the for loops. My best guess would be that my function criteria are placed in the wrong sequence

I also thought of a solution with backtracking like we did for a labyrinth two years ago in school, but I want to see if this approach is anywhere viable or not before redoing everything.

EDIT:
I'll try to implement the images of the 2 x 2 grid example asap, but the ProjectEuler website is under maintainance at the moment.

Answer 1

The solution is given by the number of combinations of "down" and "right" movements we can have. Since there is no backtracking, there are N downwards and N rightwards movements in total (in any route, for an NxN grid). There are 2N movements in total.

We can obtain this using the binomial coefficient, ⁿC_r (pronounced "n choose r"), which is the number of ways of choosing r objects from n objects (each of which can be two things). In our case an "object" is either a downward or rightward movement. This is given by

Thus the number we want is:

For N = 2 this gives 6. For N = 20 this gives 137846528820.