We present a new automatic test pattern generation algorithm for sequential circuits by traversing the partitioned state spaces. The new features include: (1) non-disjoint state groups are obtained such that two different state groups may have common flip-flops, (2) partial state transition graphs (STGs) are constructed at run time for each state group, (3) spectral information for state variables are extracted and the spectral information of the state variables helps to identify the behavior of the flip-flops in the frequency domain. This information will help us to intelligently partition the state space. We focus only on the STGs for the flip-flops that are grouped together instead of building the STG for the entire circuit, and the ATPG tries to traverse all states and transitions within each partial STG. By exercising states visited and arcs traversed, the vectors generated often lead to the detection of hard faults. Since we limit a maximum size any state group can be, construction of partitioned STGs is feasible even for very large sequential circuits. Only logic simulation is needed in our ATPG; as a result, the execution time is greatly reduced while achieving high fault coverages compared with other test generators. For some large sequential circuits, highest fault coverages have been achieved.