Long before this Matt video, I've done just that. A generator of devilish no-image jigsaw puzzles :-) which I indeed wanted to do a little Show HN someday. I made a small python script call a SAT solver to create a MxN puzzle with only 1 solution but only a few jig shapes, so maaany 'almost solutions'. Then I laser cut a plastic board and made it real, and gave one copy to a friend. At least a nice use of SAT solvers that is more efficient than Matts brute force approach.

The most recent one I did had a grid of letters on the back, to make sure things align. I wonder if that would make it easier or harder to solve than if it were a single color

There's a jigsaw brand (impossipuzzle, I think) that does something like that to make them as difficult as possible. They're printed on both sides, and the rows/columns are cut from different sides.

I have aunts that took almost a year solving one that was an 5*7 foot picture of baked beans and chips. Most of the patterns are repetitive and non-distinct on purpose.