An adaptive gait control problem for a quadruped is formalized and an adaptive gait algorithm for eliminating dead-lock positions is proposed. The proposed method is based on the concept of a neural optimization network. The desired footholds are taken as the output variables of the neural circuit, and differential equations which tend to minimize the energy of the network are derived. An efficient method to make the quadruped statically stable is addressed. Several conditions for satisfying the geometric limits of reachable volumes are introduced. The maximum stride which can be transversed in the current configuration is calculated. The algorithm is applicable to both even and rough terrain without gait transitions.>