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 \times 400$$ and magic rectangles up to $$100 \times 300$$ demonstrate practical scalability and efficiency.