The key factor here is the internal resistance of different types of cell.
A fresh alkaline C cell has an open circuit voltage of 1.5V, and an internal resistance in the range 150mΩ to 300mΩ (according to this Energizer datasheet).
This implies that even a dead short across the cell (which will totally collapse the output voltage) will only give 5A-10A.
If you maximize the useable power by matching the load resistance to the internal resistance, you can't expect more than 2W-3W usable power per cell (with the same amount lost in internal heating).
For each solenoid the power needed is 12*12/4=36W, so 72W for the pair. Allow 90% boost efficiency, and you're looking for ~80W.
This implies that you will need somewhere between 30 & 40 fresh cells to drive the pair....
Even at 9V, the solenoids still need 9*9/4=~20W each, or 40W the pair, so 15-20 C cells.
Checking the datasheet for the large D cells, we see they have very similar internal resistance, so this doesn't help.
You should therefore consider using rechargeable batteries which typically have much lower internal resistance (NiCd, NiMH, Lead-Acid, or one of the lithium chemistries).
For instance, the equivalent Energizer NiMH C cell has an internal resistance of 11mΩ full charged, and has speced discharge curves at 5A with just 55mV drop. Even 1/2 charged the resistance is only 22mΩ.
This means you can get 15-30W of usable power out of each battery, so 6xC NiMH cells would be able to supply 90-180W of power, which is what you need. However, be aware that there will be significant internal heating of the batteries.
Also worth considering use a dedicated NiCd or LiPo battery pack designed for use in RC vehicles, as these have even lower internal resistance, which will drastically reduce the internal heating.