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.