Costas arrays are a special type of permutation matrices with ideal autocorrelation and low cross-correlation properties, making them valuable for radar, wireless communication, and integrated sensing and communication applications. This paper presents a novel unified framework for analyzing and discovering new Costas arrays. We introduce Universal Costas Matrices (UCMs) and Universal Costas Frequency Matrices (UCFMs) and investigate their structural characteristics. A framework integrating UCMs and UCFMs is proposed to pave the way for future artificial intelligence-assisted Costas array discovery. Leveraging the structural properties of UCMs and UCFMs, a reconstruction-based search method is developed to generate UCMs from UCFMs. Numerical results demonstrate that the proposed approach significantly accelerates the search process and enhances structural insight into Costas array generation.