While many great puzzle games have a fixed number of levels, I’d like to find more with procedurally-generated levels to maximize replay value. Aside from Minesweeper games, so far I’ve found the following ones:
- Hexcells Infinite
- InfiniPicross 2.0
- KNIGHTS
- Lines Infinite
- Linklight
- LOOP
I would almost consider games like Loop Hero to be puzzles, maybe stuff like 2064 as well, or other match 3 type games like Gems of War (not that that may be the best one you’re looking for, but I think that genre loosely fits your criteria)
Are you open to community shared level editors? You might wanna give “babba is you” a try. Loads of level packs are available, also on the console versions.