You could use two
SN754410NE H-Bridges. One driving columns and one driving rows giving you the ability to drive 16 solenoids in a 4x4 matrix. Plus, they have the diodes built in.
Actually, that wont work as you can't Hi-Z each output separately. You could however only use outputs 1 and 3 on the columns. This would mean that by using 2 chips on the rows (8 rows) and 2 chips on the columns (4 columns) you can control 32 solenoids. This would however require 16 outputs - 8 rows, 4 column polarities and 4 column enables but would only cost $20.
Edit, you can join all column polarities together therefore requiring only 13 outputs. Loose a column and you can control 24 solenoids with 12 outputs.
Mike.