4S in 1

I'll spare you my code; the pseudocode is something like:

def fill_grid(grid_so_far, known_paths):
    while true:
        if all grid spaces are filled and there are 19 Xs in the grid, print and quit
        if there aren't enough empty spaces left to reach 19 Xs, return
        find the northeastmost space that hasn't been filled
        make a new grid where that space has an X and every space around it has a .
        if <check_for_path> is true:
            fill_grid(new_grid_so_far, new_known_paths)
        # if we get here, that must have failed at some step, so...
        make that space a "." instead
def check_for_path(grid, known_paths):
    for every space in the grid:
        if it's already in known_paths, we're good;
        otherwise, if it's a ".", crawl through the grid and make sure it's either:
            connected by other "." to something that *does* have a known path to the edge
                (in which case, add it to the set of things with known paths),
            or at least is connected to an empty space
    return false if some "." was blocked from the edge, otherwise true

and then run fill_grid() with a grid that has dots along the north and east edge, and all of those dots have (of course) a path to the edge.

Usually I'd guess that there's another symmetric solution, but the "north and east edges only" constraint may prevent that. 

Oh, dear.  Since this was more than two months ago now, I'm sure I don't still have that solution saved anywhere.  Sorry!