Oh this was so delightful! Very brute-force solution, it very much plods along slowly, but it’s quite nice.

The part 2 solution requires computing the part 1 solution, so I’m just putting a single solution here.

Here’s the program at dusa.rocks

Here’s the program at val.town

This program is exactly using Dusa’s choice operations the way I’d hoped to be able to use them. We use arbitrary choice to choose the direction of reflection in both parts, and use arbitrary choice to pick which of the possible lines we reflect over.

**reflection part1 is { horizontal, vertical }.
reflection part2 is { horizontal, vertical }.

reflectHorizontalLine Part is { Y? } :-
    reflection Part is horizontal,
    char Part _ Y is _,
    char Part _ (s Y) is _.

reflectVerticalLine Part is { X? } :-
    reflection Part is vertical,
    char Part X _ is _,
    char Part (s X) _ is _.**

The smudge is similarly guessed by arbitrary choice, though I did need to use the hack of a finishedPart1 predicate to sequence computation so that I didn’t guess where the smudge was until I’d already made all the relevant choices for part 1.

**smudge is { pair X Y? } :- 
    input X Y is "#",
    finishedPart1.**