Matrix Puzzle Solver ✨

CS209A final project in SUSTech

A solver of sudoku and magic square

Requirements

面向对象编程

• 将矩阵谜题类型表示为具有独立内部数据表示的抽象数据类型(Abstract data type)(例如向量、单维数组、2d数组)
• 支持输入puzzle或者数独的不同参数值
• puzzle有约束条件，在"magic square"中对角线、行和列的总和都有限制，在数独中，矩阵中1-9的排列也有限制
• 支持一些可能的操作（例如交换值之后求解，或者获取字符串表示，比较两种解的优劣）
• 需要提供用来表示不同矩阵谜题的类层次结构的文档

实现GUI

• 让用户选择幻方或者数独模式
• 显示puzzle matrix
• 允许用户操作puzzle并寻解
• 存储已完成的或者中途解到文件中并可以加载
• 存储puzzle文件
• 可以用web UI

实现解题器

• 两个解题器：幻方(magic square)和数独(sudoku)
• 建议使用演化算法，不然肯定拿不到分
• 需要足够高效：
  • 解20x20要小于5min
  • 满分标准：解20x20的30次，平均时间少于1s; 解200x200的需要少于10s（都是在正常的笔记本电脑上）
  • 数独解题器要更快
• 解题器运行时GUI要能持续更新实时解
• 用户应当可以随时停止解题器，并且能够查看目前的最优解
• 用户应当可以继续开始之前停止的解题进程
• 用户应当可以固定幻方中的某些值

解题器要求

时间复杂度：$O(\lg n+1)$

N	运行时间（30次运行平均时间）
5	$0.9\pm0.05$
10	$2.1\pm0.01$
20	$3\pm0.01$
40	$4.01\pm0.5$