Abstract
The Latin Square Completion (LSC) problem is a fundamental NP-complete combinatorial problem with critical applications in optical networking, error-correcting codes, and experimental design. This paper introduces FastLSC, a high-performance local search algorithm that integrates logical reduction rules, a history-aware conflict selection heuristic, and a novel perturbation mechanism. Experimental results demonstrate that FastLSC significantly outperforms existing state-of-the-art solvers in both success rate and computational efficiency.
1. Introduction
A Latin square of order $n$ is an $n \times n$ grid where every symbol from $1$ to $n$ appears exactly once in every row and column. The Latin Square Completion (LSC) problem starts with a partially filled grid and asks if it can be completed into a legal Latin square. Because LSC is NP-complete, finding solutions for large instances is exponentially difficult. While exact algorithms struggle with scalability, existing heuristic local search methods often waste time on redundant calculations or get trapped in local optima.
2. The FastLSC Algorithm
FastLSC addresses these challenges through three primary innovations designed to prune the search space and enhance exploration.
2.1 Reduction Reasoning
Before the search phase begins, FastLSC applies logical reduction rules to fix the values of certain empty cells. Similar to Sudoku techniques, these rules identify cells with only one possible valid symbol or symbols that can only fit in one specific cell within a row or column. This preprocessing drastically reduces the search space the algorithm must explore.
2.2 Conflict Selection and History-Aware Perturbation
During the search, FastLSC uses a primary scoring function to find moves that reduce total conflicts. To break ties and prevent stagnation, it introduces a secondary scoring function ($cscore$) based on the history of conflicts, prioritizing cells that have been in conflict for a long time.
When the algorithm reaches a local optimum, it performs a restart using a solution pool of the best results found so far. Instead of starting from scratch, FastLSC uses the "age" of assignments to intelligently perturb a saved solution, creating a high-quality starting point for the next round of searching.
3. Experimental Evaluation
FastLSC was evaluated against MMCOL (the previous state-of-the-art) using two major benchmarks: a Random Benchmark (1,800 instances) and the COLOR03 Benchmark (19 difficult instances).
3.1 Key Results
FastLSC demonstrated a clear advantage in both success rate and speed:
- Success Rate: On the hardest random instances (70% pre-filled), FastLSC achieved a success rate of 82% to 99%, while MMCOL often dropped to 0% to 28% under the same time constraints.
- Speedup: On the COLOR03 benchmark, FastLSC was consistently 2 to 3 times faster than MMCOL.
As shown in the runtime comparison, FastLSC consistently outperforms MMCOL, with many instances showing speed improvements of 10X or more. The algorithm's ability to utilize memory through historical conflict tracking allows for much smarter tie-breaking and more effective search space exploration.
4. Conclusion
FastLSC represents a significant advancement in solving the Latin Square Completion problem. By combining logical preprocessing with history-aware heuristics and intelligent perturbation, the algorithm achieves superior performance on both random and structured benchmarks. Future research will explore applying these history-based mechanisms to other NP-hard combinatorial problems.
Summary updated