An enhanced multi-stage evolution strategy for large size magic square generation and extension to magic rectangles

This paper proposes a multi-stage evolutionary approach for generating large-scale magic squares. We introduce three main contributions: (1) a deterministic initialization reducing Stage-1 time to tens of milliseconds across all tested matrix sizes; (2) an improved search algorithm that reduces the computational complexity of each fitness evaluation to O(1) through differential updates and dynamic mutation strategies, achieving approximately 40% fewer generations and speedups exceeding 100-fold for large instances; and (3) an extension to arbitrary magic rectangles, broadening the applicability of the proposed framework to practical domains such as image encryption. Experiments on magic squares up to 400 × 400 and magic rectangles up to 100 × 300 demonstrate practical scalability and efficiency.