拉丁方补全求解器

一个基于局部搜索算法的拉丁方补全问题（Latin Square Completion, LSC）求解器，使用 C++20 实现。

项目简介

拉丁方是一个 n×n 的方阵，其中每行和每列都恰好包含 0 到 n-1 的每个数字各一次。拉丁方补全问题是指：给定一个部分填充的方阵，需要填充剩余的空白单元格，使其成为一个合法的拉丁方。

本项目实现了一个高效的局部搜索算法来求解拉丁方补全问题，能够在给定时间限制内寻找最优解。

主要特性

• 🚀 基于局部搜索的高效求解算法
• ⚡ 支持大规模问题实例（测试数据包含 n=50, 60, 70 的实例）
• ⏱️ 可配置的时间限制和随机种子
• 📊 实时输出搜索进度和冲突数
• 🎯 自动验证解的正确性

编译要求

• CMake 3.20 或更高版本
• 支持 C++20 标准的编译器（GCC 10+, Clang 10+, MSVC 2019+）

编译方法

# 创建构建目录
mkdir build
cd build

# 配置项目
cmake ..

# 编译
cmake --build .

# 或使用 make（Unix 系统）
make

编译完成后，可执行文件 LatinSquareCompletion 将生成在 build 目录中。

使用方法

基本用法

./LatinSquareCompletion <时间限制(秒)> <随机种子> <输入文件 >输出文件

参数说明

• 时间限制(秒): 算法运行的最大时间（秒），必须为正整数
• 随机种子: 随机数生成器的种子，用于结果的可重复性
• 输入文件: 通过标准输入重定向读取问题实例
• 输出文件: 通过标准输出重定向保存求解结果

使用示例

# 求解 n=50, f=750 的实例，时间限制 600 秒，随机种子 123456
./LatinSquareCompletion 600 123456 <../data/LSC.n50f750.00.txt >solution.txt

# 求解 n=60, f=1080 的实例，时间限制 300 秒，随机种子 42
./LatinSquareCompletion 300 42 <../data/LSC.n60f1080.00.txt >output.txt

输入格式

输入文件的第一行包含一个整数 n，表示拉丁方的大小。 接下来的若干行，每行包含三个整数 row col value，表示在位置 (row, col) 处预填充的值为 value。

示例（n=6 的实例）：

6
0 0 2
0 3 3
0 5 1
1 1 4
2 2 2
...

输出格式

输出为 n 行，每行包含 n 个用空格分隔的整数，表示补全后的拉丁方。

示例输出：

2 3 4 5 0 1
0 4 1 2 3 5
3 5 2 0 1 4
4 0 5 1 3 2
1 2 3 4 5 0
5 1 0 3 2 4

项目结构

.
├── CMakeLists.txt          # CMake 构建配置
├── README.md               # 项目说明文档
├── data/                   # 测试数据集
│   ├── n6f12.txt          # 小规模测试实例
│   ├── LSC.n50f*.txt      # n=50 的测试实例
│   ├── LSC.n60f*.txt      # n=60 的测试实例
│   └── LSC.n70f*.txt      # n=70 的测试实例
├── include/                # 头文件目录
├── src/                    # 源代码目录
│   ├── latin_square/      # 核心算法实现
│   └── main.cpp           # 主程序入口
├── build/                  # 构建目录（生成）
└── docs/                   # 文档目录

算法说明

本求解器采用局部搜索算法，主要包括以下组件：

1. 初始解生成: 为空白单元格生成初始填充
2. 冲突计算: 高效计算行列冲突数
3. 邻域搜索: 通过交换操作探索解空间
4. 禁忌策略: 避免陷入局部最优
5. 时间控制: 在指定时间内寻找最优解

测试数据

项目包含多组测试数据，命名格式为 LSC.n{N}f{F}.{ID}.txt：

• N: 拉丁方的大小（50, 60, 70）
• F: 预填充单元格的数量
• ID: 实例编号（00-99）

例如：LSC.n50f750.00.txt 表示一个 50×50 的拉丁方，包含 750 个预填充单元格。

性能提示

• 对于大规模实例，建议设置较长的时间限制（如 600 秒或更长）
• 不同的随机种子可能产生不同质量的解，可以尝试多个种子
• 程序会在标准错误输出中显示搜索进度和统计信息

开发说明

核心模块

• latin_square/instance.h: 问题实例的表示
• latin_square/latin_square.h: 拉丁方数据结构
• latin_square/local_search.h: 局部搜索算法实现
• latin_square/color_domain.h: 颜色域管理
• utils/RandomGenerator.h: 随机数生成器

编译选项

项目使用 C++20 标准，关键编译选项：

• CMAKE_CXX_STANDARD: 20
• CMAKE_CXX_STANDARD_REQUIRED: ON
• CMAKE_CXX_EXTENSIONS: OFF

许可证

本项目仅供学习和研究使用。

作者

Created by qiming

更新日志

• 2025-07: 初始版本发布
  • 实现基于局部搜索的拉丁方补全求解器
  • 支持大规模问题实例
  • 添加时间限制和随机种子控制

常见问题

Q: 程序运行时间超过了设置的时间限制怎么办？
A: 程序会在接近时间限制时自动停止搜索并输出当前最优解。

Q: 如何判断找到的解是否是可行解？
A: 程序会在标准错误输出中显示冲突数，冲突数为 0 表示找到了可行解。

Q: 为什么不同的随机种子会产生不同的结果？
A: 局部搜索算法具有随机性，不同的随机种子会导致不同的搜索路径，从而可能找到不同质量的解。

Q: 如何提高求解质量？
A: 可以尝试增加时间限制、使用多个随机种子运行多次并选择最优解。