count the domino tilings of a rectangle; see https://math.stackexchange.com/questions/4613898

Question4613898.java

public class Question4613898 {
    final static int w = 6;
    final static int h = 6;
    
    static int x,y;
    
    static boolean [] [] used = new boolean [w] [h];
    static int count;
    static int deadEnds;
    
    public static void main(String [] args) {
        recurse ();
        System.out.println(count);
        System.out.println(deadEnds);
    }

    static void recurse () {
        int oldX = x;
        int oldY = y;
        
        try {
            while (used [x] [y])
                if (++x == w) {
                    x = 0;
                    if (++y == h) {
                        count++;
                        return;
                    }
                }

            used [x] [y] = true;
            if (!(attempt (x,y + 1) | attempt (x + 1,y)))
                deadEnds++;
            used [x] [y] = false;
        } finally {
            x = oldX;
            y = oldY;
        }
    }
    
    static boolean attempt (int nx,int ny) {
        boolean free = nx < w && ny < h && !used [nx] [ny];
        if (free) {
            used [nx] [ny] = true;
            recurse ();
            used [nx] [ny] = false;
        }
        return free;
    }
}