Quick answer with some assumptions.
Assuming a 100 Ohm solenoid, one would draw 120ma current on 12v DC. (12/100 = 0.12)
36 solenoids would use 4.32 Amperes. ( 0.12*36 = 4.32)
A 12V 7AH Sealed Lead Acid Battery (This size is moderately portable and easily available) would last a over an hour at this load.
7AH = 1 Ampere for 7 hours = 7 Amperes for 1 Hour = 3.5 Ampere for 0.5 Hours. (This is a simplified calculation for Ampere Hours. Practically, the capacity goes down with increased load current. A battery that gives 1A for 7 hours will be able to source 7A for less than an Hour)
For 4.32 Amperes, 7AH would run for 7/4.32 = 1.62 Hours
This doesn't take into account the switching losses or the duty cycle of the solenoids. If you turn on only a few solenoids at a time and have them turned on only for short duration, you can expect a lot more run time.
If you want more run time, try a car battery which at around 35AH would give you more than 8 hours run time.