A Fast Local Search Algorithm for the Latin Square Completion Problem


  • Shiwei Pan Northeast Normal University
  • Yiyuan Wang Northeast Normal University
  • Minghao Yin Northeast Normal University




Search And Optimization (SO)


The Latin square completion (LSC) problem is an important NP-complete problem with numerous applications. Given its theoretical and practical importance, several algorithms are designed for solving the LSC problem. In this work, to further improve the performance, a fast local search algorithm is developed based on three main ideas. Firstly, a reduction reasoning technique is used to reduce the scale of search space. Secondly, we propose a novel conflict value selection heuristic, which considers the history conflicting information of vertices as a selection criterion when more than one vertex have equal values on the primary scoring function. Thirdly, during the search phase, we record previous history search information and then make use of these information to restart the candidate solution. Experimental results show that our proposed algorithm significantly outperforms the state-of-the-art heuristic algorithms on almost all instances in terms of success rate and run time.




How to Cite

Pan, S., Wang, Y., & Yin, M. (2022). A Fast Local Search Algorithm for the Latin Square Completion Problem. Proceedings of the AAAI Conference on Artificial Intelligence, 36(9), 10327-10335. https://doi.org/10.1609/aaai.v36i9.21274



AAAI Technical Track on Search and Optimization