Quantum computing is one of the most promising emerging technologies of the future. Reversible circuits are an important class of Quantum circuits. In this paper, we investigate the problem of optimally synthesizing four-qubit reversible circuits. We present an enhanced bi-directional synthesis approach. Due to the super-exponential increase on the memory requirement, all the existing methods can only perform four steps for the CNP (Control-Not gate, NOT gate, and Peres gate) library. Our novel method can achieve 12 steps. As a result, we augment the number of circuits that can be optimally synthesized by over 5*10⁶ times. Moreover, our approach is faster than the existing approaches by orders of magnitude. The promising experimental results demonstrate the effectiveness of our approach.