Bidirectional solid state switch for solenoid
David, while you may be able to find the appropriate switches and make your current approach work, I think there is a neater solution to your problem.  



Each row and column in the matrix can be high, or low, or floating.  This gives you random access to each solenoid, so you can run current through one solenoid in either direction, while no current is running through other solenoids.

I drew the half-bridges with MOSFETs, but they can be implemented in other ways too.

update:



The circuit in the dot board with the diodes seems a bit odd to me.  It would still require nTransistors = 2*nRows + 2*nCols, but now the dot board has 2x connections per row instead of 1.  I wonder what the rationale of the dot board designers was.  I also wonder if I’m missing something.

Then again, we’re situated roughly in the same neck of the woods.  Perhaps, I can physically look at your dot board.