This is not quite right:

def _unchoose(self, i):
    """Unmake choice i; restore constraints and choices."""
    self.solution.pop()

It promises to undo an arbitrary choice i but actually pops the latest one from self.solution. As you only use if for undoing the latest choice, I suggest to drop the parameter:

def _unchoose(self):
    """Unmake latest choice; restore constraints and choices."""
    i = self.solution.pop()

Actually the choose-unchoose pattern feels a bit awkward to me. I'd prefer functional programming instead. Another idea that would make me feel more comfortable would be to create a context manager:

@contextlib.contextmanager
def _tentative_choice(self, i):
    self._choose(i)
    try:
        yield
    finally:
        self._unchoose(i)

use:

    for i in choices:
        with self._tentative_choice(i):
            for solution in self._solve():
                yield solution

Another small concern is that you use a local variable choices in methods of a class that has an instance variable self.choices. This may lead to confusion; I'd use a different name.

This is not quite right:

def _unchoose(self, i):
    """Unmake choice i; restore constraints and choices."""
    self.solution.pop()

It promises to undo an arbitrary choice i but actually pops the latest one from self.solution. As you only use if for undoing the latest choice, I suggest to drop the parameter:

def _unchoose(self):
    """Unmake latest choice; restore constraints and choices."""
    i = self.solution.pop()

Actually the choose-unchoose pattern feels a bit awkward to me. I'd prefer functional programming instead. Another idea that would make me feel more comfortable would be to create a context manager:

@contextlib.contextmanager
def _tentative_choice(self, i):
    self._choose(i)
    yield
    self._unchoose(i)

use:

    for i in choices:
        with self._tentative_choice(i):
            for solution in self._solve():
                yield solution

Another small concern is that you use a local variable choices in methods of a class that has an instance variable self.choices. This may lead to confusion; I'd use a different name.