Java Solution using memoization. The first step is to find all possible Ls that cover the grid, and create a map from grid locations to all valid Ls that cover that location (for the sake of brevity I won’t go over this part, but there’s 8 possible Ls where the ‘long bar’ starts for a single location). The most efficient way to represent the coverage of a grid this small is a bit mask (aka. an array of 3 or less longs), so it also good to idea to precompute the masks for the valid Ls and store them in a map, and also find the mask of the initial grid and fully covered grid. The last map goes from a bitmask to the number of ways you can cover that mask.

The recursive logic is pretty straightforward. Find the first open location on the current grid, and for every L you can place on this location, sum the ways you can cover the rest of the uncovered grid and that’s the number of ways you can cover the current grid. Again, this is all done with bit masks, so you’ll have to implement functions for combining masks, removing coverage from a mask, finding the first open entry and finding the coverage count of a grid (these are all very fast functions though) and a class for a bitmask. Also note that, if you combine a grid’s mask with an L’s mask, and the coverage count went up by less than 4, that means this L overlapped with some already covered part of the grid, and therefore is an invalid placement. You also have to be careful with the last long of the bit mask, as the grid is likely not a multiple of 64 (aka. not all 64 bits of the last long are in use).

Here is the main recursive function (the first call has the “to find” mask as the fully covered grid and the “currently covered” grid as the initially covered grid: ‘ public static long findWaysToCover(BitMask toFindMask, BitMask coveredMask, Map> waysToCover, Map> LsThatCover, Map lToMask, int numLeftToCover, int initialCount) {

    // Avoid recalculations / memoization 
    Map<BitMask,Long> waysToCoverCurr = waysToCover.get(numLeftToCover);
    if (waysToCoverCurr.containsKey(toFindMask)) {
        return waysToCoverCurr.get(toFindMask);
    }
    // Find the first open entry
    int newPosToCover = findFirstOpenEntry(coveredMask);
    Set<Integer> coveringNew = new HashSet<>(LsThatCover.get(newPosToCover));

    // Check every possible way to add an L that covers this open grid location
    long result = 0;
    int currCovered = numToCover - numLeftToCover;
    for (int lIdx : coveringNew) {
        BitMask lMask = lToMask.get(lIdx);
        BitMask nextCovered = combineMasks(coveredMask, lMask);
        // If this L overlaps with the previous coverage, invalid L
        if (findCoverageCount(nextCovered, initialCount) < currCovered + 4) {
            continue;
        }
        // Add this L to the current coverage, find ways to cover the reverse
        BitMask nextToFind = removeCoverage(toFindMask, lMask);
        int newLeftToCover = numLeftToCover - 4;

        long nextWays = findWaysToCover(nextToFind, nextCovered,
        waysToCover, LsThatCover, lToMask, newLeftToCover, initialCount);
        result = (result + nextWays) % mod;
    }
    waysToCoverCurr.put(toFindMask,result);
    return result;
}

‘