基于C++实现数独【100012553】

# BITCS单人项目：数独 本项目仍在开发中。 Github存储库地址：<https://github.com/howmanyKsdoIneed/BITSE-sudoku> 本项目的PSP2.1表格如下： |项目|预估耗时(min)|实际耗时(min)| |:---|:-:|:-:| |计划|120|| |· 估计所需时间|120|| |开发|1140|| |· 需求分析/新技术学习|240|| |· 生成设计文档|120|| |· 设计复审|60|| |· 代码规范|60|| |· 具体设计|240|| |· 编码|240|| |· 代码复审|60|| |· 测试|120|| |报告|210|| |· 测试报告|120|| |· 计算工作量|30|| |· 事后总结，提出过程改进计划|60|| |总计|1470|| ## 1 题意简述 本项目的需求主要有两部分：生成数独终局和解一个数独问题。 生成终局部分，输入要生成的终局数量N(1\<=N\<=1E6)，在短时间内高效生成N个合法且不重复的数独终局，保存到文件中。这些终局左上角的数字必须全部是3。程序应有识别参数是否合法及处理其他异常情况的能力。 解数独部分，从输入的文件名中读取数独题目，用0代表空位。对输入文件中的每一个问题，给出数独的一个可行解并存入文件。每个题目空位均在30-60个之间，每个九宫格都至少有2个空位。输入数据保证正确，题目数量在1和1E6之间。 ## 2 解题思路描述 ### 终局的构造 首先考虑数独终局生成部分。考虑要在短时间内生成大量数独终局，如直接采用回溯法求解，每一行（或列，九宫格）都组成一个排列树，计算次数约有9!^9，即1E50左右，恐怕一个解都无法按时生成。故须采取某种简化算法，或按某种方法构造。 考虑一个已经填满一行（不妨认为是第一行），其他位置均为空位的数独。将第一行循环左移3个和6个位置后分别填入第2、3行，所得的结果的前三行（即已经填满的行）中，各行必然符合数独要求；不难得知这三个九宫格也满足数独要求。 将前三行每行循环左移1或2位后填入4-6、7-9行中。与前面相似，每一行必然满足数独要求。5、6行可看作第4行循环左移3、6位的结果，故可知每个九宫格也满足数独要求，7-9行同理。 同样，不难发现这样生成的数独矩阵每一列的各个元素刚好一一对应第一行的各个元素，故每一列也都满足数独要求。 综上，只要确定了第一行，便可依此法构造一个数独终局。在本题背景下，合法的第一行共有8!=40,320种。 考虑一个合法的数独终局。如果任意交换两行，显然不会破坏行、列上的数独条件，但可能破坏九宫格内的数独条件。交换属于同样三个九宫格的行（如4，5，6行都对应第二排九宫格），就不会破坏数度条件了。因此在本题的条件下（第一位须为3），给定一个合法的数独终局，均可构造出2!\*3!\*3!=72种变体。上述两种方法结合，可以构造出2,903,040种不同的数独终局。 实际上还可以将4-6和7-9行整体交换，这样可构造出的数独终局数量还能再加倍。 上述构造算法远远不能构造出所有可能的数独终局，但已经满足了题目提出的要求。 ### 终局的编码 可以用0-2,903,039之间（含）的正整数一一对应地编码按上述方法构造出的数独终局。数独终局是由第一行的变化和各行的排列两部分构造而成的。前者有8!=40,320种变化，后者有72种变化。因此可将标号视作72a+b的形式，其中a,b都是正整数，a<40,320;b<72。a编码了第一行如何变化，b编码了剩余行如何排列。 首先考虑a。第一行的排列又可看作第二个的确定和其他位置的确定，故a/7!可以当作第二个数(第1位上的数)的编码。同样地，(a mod 7!)/6!可以当作第三个数的编码，依此类推。 因此，第i位(i=1,2，...,7)的编码为(a mod (9-i)!)/(8-i)!。第8位的编码为0。每当确定了编码后，就与自己右方第编码个数互换（e.g. 处于第2位的，若编码为5，则与第7位的数交换）。左侧的位置先交换，右侧的位置后交换，即按编码构造了终局的第一行。 用类似的方式考虑b。b可以视为b1\*36+b2\*6+b3三部分，其中b1取0或1，b2和b3取0,1或2。0行因左上角的数字要求不能移动。若b1=1，表示应互换1,2两行，否则不互换；b2%3表示第3行和第3+i行互换；b2的奇偶性表示4,5行是否再互换。6-8行同理。 这样，就用一个整数唯一地表示了构造出的数独终局。 ### 求解 求解数独没有生成终局那样的构造方法，只能在回溯法的基础上，尽量优化。首先可以尝试使用排列树进行优化，也可以像人处理数独问题那样，优先分析可选数字比较少的空位来剪枝，并同时考虑某个数字当前可能出现在不同九宫格的哪个位置上，从而尽可能在不加深搜索深度的情况下，尽可能填满更多的空位，或排除更多的无效解。 ## 3 设计简述 程序分为主控模块和数独棋盘类两部分。主控类负责接受并检查程序参数并协调其他模块工作。数独类保存一个数独状态，并拥有以下功能： 1. 索引。禁止外部直接访问数独棋盘的内部数据结构，通过这种方式预留外接访问棋盘上具体位置数字的方法。 2. 有效性检查。检查当前数独的状态是否合法。可根据输入参数来指明空位视为合法还是非法。 3. 终局生成模块。给出标号n(0<=n<=2,903,039)，按照上述构造算法，构造第n个数独终局。这样可以使重复执行程序获得输出不同成为可能。 4. 解数独模块。输入要求解的数独和开始搜索的位置(首先尝试填数字的空位)，递归地在这个数独问题（的数据）上做改动，试图求解这个数独问题。若得解，返回true，此时输入数据被改动成为求解出的终局；若没有得解，返回false，保持原题目不变。 5. 数独输入模块。从输入流中读一个数独题目或者终局，检查其合法性。 6. 数独输出模块。向输出流中写一个数独终局，但不必检查合法性。 以下就几个较复杂的模块做详细介绍。 ### 主控模块 首先读入参数，并检查参数合法性。参数应为两个，第一个参数允许是-c或-s。 若为-c，则第二个参数须可以转为小于等于100,000的正整数；若为-s，则第二个参数应是一个可以打开的文件的路径。 之后分两种情况讨论： - -c,即输出指定个数独终局。可任意选出给定数量个0-2,903,039的整数，生成这些标号对应的数独终局并保存至文件，也可从0开始逐一生成。 - -s,即解数独。打开指定的文件，每次读入一个数独题目并交由解数独模块求解，直到文件读完为止。对每一个数独题目，若能够解出，则输出至文件；否则打印错误信息。 ### 终局生成模块 输入给定的标号（和左上角数字），本模块的目的是给出标号对应的数独终局。 首先用0初始化一个数独盘面，之后生成第一行：在第一行填入1-9后，将1和要求的左上角数字互换。计算出第一行每一位的编码。从第二位开始，设第i位的编码是k，则互换第i位和第i+k位。 生成第一行后，用前述平移第一行的方法逐个生成之后的行，随后按b的编码对之后的行进行互换，参见终局的编码部分。随后，返回生成的数独终局。 ### 解数独模块 用较简单的回溯法求解。算法如下所示： 1. 找开始搜索的空位。若输入的位置非法或不是空位，则遍历所有位置，找出第一个空位作为开始搜索的空位。若找不到，说明数独已经填完了，返回true；否则，继续执行。 2. 搜索空位所在行、列、九宫格中已有的数字，找出当前填入尚合法的所有数字。若找不到，直接返回false； 3. 对可填入的每一个数字，尝试填入后，递归调用本方法。若返回true，则表明已找到解，直接返回true；若返回false，则继续尝试下一个数字。暂不考虑子调用首先搜索的位置。 4. 若2中每一个子调用都返回false，则表明未找到合法解。将这个位置重置为0，并返回false。