2D grid Hamiltonian path puzzle solver

The puzzle goes like this: in a rectangular 2D grid there are empty spaces (.), exactly one starting point (S, s) and obstacles (denoted below by X's). The objective of the puzzle is to find a path starting at the starting point and going through each empty space exactly once (a Hamiltonian path). You can't, of course cross the obstacles. You can move horizontally and vertically. A typical puzzle would look like this:

......
.SX...
...X..
.....X
......
XX....
......

And its solution:

11 12 13 14 17 18
10 1  X  15 16 19
9  2  3  X  21 20
8  5  4  23 22 X 
7  6  25 24 29 30
X  X  26 27 28 31
37 36 35 34 33 32

I wrote a solver in Python 3 (I later learned that this algorithm is actually a simple DFS). It solves the puzzle above in ~0.9 s, which is very good, but I was wondering if I can perhaps optimize it somehow.

```
import time

EMPTY_SPACE_SYMBOLS = ['.']
STARTING_POINT_SYMBOLS = ['S', 's']
OBSTACLE_SYMBOL = 'X'
PUZZLE_PATH = "grid.txt"
DIRS = [(-1, 0), (1, 0), (0, 1), (0, -1)]

start_time = time.time()

grid = open(PUZZLE_PATH).read().splitlines()
H = len(grid)
W = len(grid[0])
assert all(len(row) == W for row in grid), "Grid not rectangular"

def print_solution(coords):
result_grid = [[OBSTACLE_SYMBOL for _ in range(W)] for _ in range(H)]
for i, (r, c) in enumerate(coords, start=1):
result_grid[r][c] = i
str_grid = [[str(item).ljust(3) for item in row] for row in result_grid]
print('\n'.join(' '.join(row) for row in str_grid))

def extend(path, legal_coords):
res = []
lx, ly = path[-1]
for dx, dy in DIRS:
new_coord = (lx + dx, ly + dy)
if new_coord in legal_coords and new_coord not in path:
res.append(path + [new_coord])
return res

start_pos = None
legal = set()
for r, row in enumerate(grid):
for c, item in enumerate(row):
if item in STARTING_POINT_SYMBOLS:
assert start_pos is None, "Multiple starting points"
start_pos = (r, c)

1. Review

-
Code is easier to test (and measure the performance) if it's organized into functions or classes. In this case you have persistent data (W, H, grid, legal, start_pos) that's shared between the various parts of the code, so a class would be the best way to go here.

-
It would be simpler to write:

EMPTY_SPACE_SYMBOLS = '.'
STARTING_POINT_SYMBOLS = 'Ss'

since Python can iterate over the characters in a string just as easily as over the items in a list.

-
Assertions should be reserved for detecting programming errors, and not used for reporting problems with the input. That's because assertions can be disabled via the -O option to the Python interpreter, or the PYTHONOPTIMIZE environment variable. For the errors in this code, you should raise exceptions.

-
It's more general to have a method format_solution that returns a string, rather than a function print_solution that prints it. That way the caller has the option of deciding what to do with it.

-
Instead of:

[OBSTACLE_SYMBOL for _ in range(self.w)]

write:

[OBSTACLE_SYMBOL] * self.w

-
Instead of building str_grid from result_grid and then formatting the former, just format result_grid directly:

'\n'.join(' '.join(str(item).ljust(3) for item in row)
          for row in result_grid)

-
The number "3" only works for small enough puzzles. To make the formatting work in the general case, it should be one more than the maximum number of digits in any number in the path, that is:

len(str(len(path) + 1)) + 1

-
extend is only called from one place in the code, so it would make sense to inline it at that point.

-
Coordinates are r and c in some places in the code, and x and y in other places. It would be better to be consistent.

1. Revised code

import time

EMPTY_SPACE_SYMBOLS = '.'
STARTING_POINT_SYMBOLS = 'Ss'
OBSTACLE_SYMBOL = 'X'
DIRS = [(-1, 0), (1, 0), (0, 1), (0, -1)]

class HamiltonSolver:
    """Solver for a Hamilton Path problem."""

    def __init__(self, grid):
        """Initialize the HamiltonSolver instance from a grid, which must be a
        list of strings, one for each row of the grid.

        """
        self.grid = grid
        self.h = h = len(grid)
        self.w = w = len(grid[0])
        if any(len(row) != w for row in grid):
            raise ValueError("Grid is not rectangular")
        self.start = None
        self.legal = set()
        for r, row in enumerate(grid):
            for c, item in enumerate(row):
                if item in STARTING_POINT_SYMBOLS:
                    if self.start is not None:
                        raise ValueError("Multiple starting points")
                    self.start = (r, c)
                elif item in EMPTY_SPACE_SYMBOLS:
                    self.legal.add((r, c))
        if self.start is None:
            raise ValueError("No starting point")

    def format_solution(self, path):
        """Format a path as a string."""
        grid = [[OBSTACLE_SYMBOL] * self.w for _ in range(self.h)]
        for i, (r, c) in enumerate(path, start=1):
            grid[r][c] = i
        w = len(str(len(path) + 1)) + 1
        return '\n'.join(''.join(str(item).ljust(w) for item in row)
                         for row in grid)

    def solve(self):
        """Generate solutions as lists of coordinates."""
        target_path_len = len(self.legal) + 1
        paths = [[self.start]]
        while paths:
            path = paths.pop()
            if len(path) == target_path_len:
                yield path
            r, c = path[-1]
            for dr, dc in DIRS:
                new_coord = r + dr, c + dc
                if new_coord in self.legal and new_coord not in path:
                    paths.append(path + [new_coord])

PUZZLE_GRID = '''
......
.SX...
...X..
.....X
......
XX....
......
'''.split()

def main():
    start_time = time.time()
    n_solutions = 0
    puzzle = HamiltonSolver(PUZZLE_GRID)
    for solution in puzzle.solve():
        if n_solutions == 0:
            print(puzzle.format_solution(solution))
            print("First solution found in {} s"
                  .format(time.time() - start_time))
        n_solutions += 1
    print("{} solution{} found in {} s"
          .format(n_solutions, '' if n_solutions == 1 else 's',
                  time.time() - start_time))

if __name__ == '__main__':
    main()

1. Speeding it up

-
Each time extend is called, the list of paths under consideration is extended by up to four new paths, each of which is a copy of the current path plus one new grid coordinate. As the search progresses, this results in many paths being created and stored (up to 20 paths in the example from the post).

But in a depth-first search it should be only be necessary to remember a single path at a time, together with the current position in the iteration over the four directions. (This is the "stack of iterators" pattern.)

-
The code checks to see if the n

StackExchange Code Review Q#142507, answer score: 6