Latching Solenoid Arduino

The 2-wire version is going to need 6-18V applied in both positive and negative directions. You need an H-bridge. Otherwise known as a brushed DC motor controller. There's a wide range of controllers with the 4A capacity you need. I would not bother with the capacitor if your battery can deliver that current.

For best efficiency on battery, I would choose a MOSFET based driver, not the older style LM293 motor drivers.

Which Arduino? Which battery?