A Fast Local Search Algorithm for the Latin Square Completion Problem

Shiwei Pan, Yiyuan Wang, Minghao YinAAAI 2022 · DOI

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.

Illustration of the reduction reasoning process, simplifying the grid and its corresponding graph representation.

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.
Runtime comparison between FastLSC and MMCOL across various instances, demonstrating significant speedups.

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

BibTeX
@inproceedings{pan2022fast,
  author = {Shiwei Pan and Yiyuan Wang and Minghao Yin},
  title = {{A Fast Local Search Algorithm for the Latin Square Completion Problem}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2022},
  doi = {10.1609/aaai.v36i9.21274},
}
Figure