Supaplex, a game originally released back in 1991 now has multiple modern versions available on Steam and it seems the developers have now added Linux support years later.
Originally created as an extended clone of Boulder Dash, Supaplex is known for its difficulty. By modern standards, there's probably far more exciting puzzle games to look for but as a good bit of nostalgia it seems to do the job just right.
From what I can see, these games are not from the original developers so they're actually remakes. It's not entirely clear how they've been able to use the Supaplex name but it seems no one is around from the 90's to cause a fuss over it.
On Steam they have a few versions of it including Supaplex, Supaplex HARD and Supaplex SQUARES - all of which now have native Linux support and it seems the developers are working towards bringing Linux support to the other titles they have up in the series too.
You can find them all on Steam.