We had a system at one of my old companies that with each password change, you couldn't have any of the same characters that were in your last password (12 character max so it was never impossible to solve), you couldn't have the same character in the same place as any of your last 10 passwords, or the same character type (letter or number) in the same space as the last password. Also no special characters.

The end result was everyone ended up using a1a1a1a1 for the first password, then 2b2b2b2b, c3c3c3c3, 4d4d4d4d, etc. The draconian password requirements resulted in everyone using the same passwords.