@Override
    public Long solve() {

        final int max = 40;
        final long[][][] cache = new long[max][DIGITS][1 << DIGITS];
        
        long sum = 0;
        
        for (int f = 0; f < DIGITS; ++f) {
            cache[0][f][1 << f] = cache[0][f][0] = 1;
        }
        for (int n = 1; n < max; ++n) { // length
            for (int f = 0; f < DIGITS; ++f) { // first digit
                for (int d0 = 0; d0 < (1 << 10); ++d0) { // digits to be contained
                    if (bitCount(d0) <= n + 1) { // only those that may fit
                        
                        final int d1 = d0 & ~(1 << f);
                        
                        if (f > 0) cache[n][f][d0] += cache[n - 1][f - 1][d1];
                        if (f < 9) cache[n][f][d0] += cache[n - 1][f + 1][d1];
                    }        
                }
                if (f > 0) sum += cache[n][f][(1 << DIGITS) - 1];
            }
        }

        return sum;
    }