GitHub - konstin/sudoku-in-python-packaging: 在 Python 打包中的数独求解

主要观点:通过 Python 包来解决数独问题,数独在 Python 包的版本求解中是 NP 完全问题,可将数独格中的每个单元格视为一个包,用 pyproject.toml 表示并求解,还介绍了将数独转换为需求、用包管理器求解以及渲染解决方案的方法,并给出了基准测试结果。
关键信息:

  • 数独格中单元格对应包sudoku_{x}_{y},版本值即单元格值。
  • 可将数独写为 csv 转换为需求,用csv_to_requirements.py脚本,如python csv_to_requirements.py sudoku.csv requirements.in
  • 用包管理器求解,如uv pip compile --find-links packages/ --no-annotate --no-header requirements.in > requirements.txtpip-compile --find-links packages/ --no-annotate --no-header requirements.in -o requirements.txt
  • render_solution.py脚本渲染解决方案,如python render_solution.py requirements.txt
  • 基准测试中uv pip compile平均耗时约 29.7ms,不同数独测试的 walltime 变化不大,性能瓶颈在于获取和解析元数据以及构建源分布。
    重要细节:
  • 给出了具体的数独示例及其转换后的需求和解决方案。
  • 说明了在实际中 Python 的依赖解析通常无需回溯,多数情况下性能较好。
阅读 32
0 条评论