[chinpokomon]

From that list, the first one mentioned is the worst of the bunch. "8) A password cannot be too similar to a previous password.”

How can you possibly know this without storing the password in plain text or without storing something in the database that reveals critical information about the pattern?

[umsm]

You can ask for the old password and the new password twice. Solves your concern without storing anything critical.

[DonHopkins]

Also: "Must not have been used within your last 20 passwords."

So you just have to provide your last 20 passwords.