Passwords shouldn't be stored in plain text for obvious security reasons: you have to store hashes, and you should also generate the hash carefully to avoid rainbow table attacks.

However, usually you have the requirement to store the last n passwords and to enforce minimal complexity and minimal change between the different passwords (to prevent the user from using a sequence like Password_1, Password_2, ..., Password_n). This would be trivial with plain text passwords, but how can you do that by storing only hashes?

In other words: how it is possible to implement a safe password history mechanism?