aratti,
Thanks for the schematic. Yours is a better approach than mine because it only requires two SPDT relays instead of two DPDT relays...cheaper! However I am a little concerned about whether "nothing happens" in your circuit for the state where both Relay 1 and 2 coils are turned on and both the Red and Black wires are connected to +9vdc. I am not certain what the latching solenoid does that I am looking at when both wires are high.
Have your ever tested or used your circuit with an actual latching solenoid? If so what was your experience and can you refer me to the Part No. for the one you used??