Rubik's clock can be solved using linear algebra.
The only reservation I have about this example is that the Rubik's clock puzzle is unfortunately nowhere near as fun as Rubik's cube. Not only is it obscure, but it's basically impossible to look at both sides of the clock at once. Also, the specimens I've seen are not very well constructed and it's hard to turn the wheels.
Despite all that, I personally enjoyed solving Rubik's clock a lot, and a significant part of the fun was discovering that it was a linear algebra problem. (This was back when the puzzle first came out; I was still an undergraduate, and linear algebra was still relatively new to me.)
