# 数独大作业

### 完成人及分工

| 完成人 | 学号 | 分工 |
| ------ | ---------- | ---- |
| 邱乐平 | 2019080107 | 数据结构<br>`solve`函数|
| 弋紫轩 | 2019011307 | 作业报告<br>`solve`函数 |
| 郑瑞晨 | 2019080116 | 输入输出<br>`generate`函数 <br> |

### 程序功能介绍

本程序能够通过用户输入控制程序运行出题或解题功能

##### 输入与输出

1. 输入`1`程序会输出一个9*9、有唯一解、至少一半以上是空格的数独题目
2. 输入`2`以及一个合法的9*9数独题目程序会：
1. 对无解题目，输出 `No solution`
2. 对存在唯一解的题目，第一行输出 `OK` 随后九行输出唯一解
3. 对存在多解的题目，第一行输出 `Multiple_solutions` 随后输出9行，表示第一个可行解，空一行后再输出9行，表示第二个可行解

##### 合法9*9数独阵样式：

每行九个数，用空格隔开，其中没有数的位置用 `-` 代替

- - 3 8 6 - 9 5 -
- 2 7 - - 9 - - 3
5 - - - - 3 - - -
- - - 1 - - - - 2
8 - - 7 - - 5 1 -
- 5 2 - 3 4 6 - -
- 6 1 2 - - 4 8 5
9 - - - 4 - - - 6
- 7 4 - - 5 1 3 -

### 代码设计思路

#### 实现背景

- 用0-8代替数独阵的1-9

#### 主要变量和数据结构

| 变量和数据结构 | 用途 | 备注|
| ---------------------- | ---------------- | -------- |
| `WILL_DIG` | 设定出题时目标挖空个数 | 提高可能会造成更长的运行时间 |
| `taken[3][9][9]` | 判断行、列、宫是否可以再填入某数 | - 用数组下标中的0-8代表行/列/宫是否出现过该数<br>- 若出现记为1，否则记为0 |
| `sudoku[3][9][9]` | 记录三个数独阵 | - 用`-1`表示该位置为空 |
| `can_fill[9][9]` | 记录该位置最初是否为空 | - 用`1`表示该位置非空，`0`表示该位置为空 |
| `solution_num` | 记录解的个数 | - 解题时可以在`sudoku`数组中控制在第几层存放数独阵 <br>- 出题时可以用来判断挖空方案是否是唯一解 |
| `digging` | 记录上轮已挖空个数 | - 在出题时对比digged和digging，若没有产出新的空，放弃本次挖空并重新挖空 |
| `digged` | 记录一轮挖空过程中，已挖空的个数 | |
|`generated_sudoku` | 输出时的中间字符串，用于附带输出内容 | |

#### 函数

| 函数名称 | 函数参数（未标注的数据类型均为`int`） | 函数功能 | 出题 / 解题 ？ |
| -------- | -------- | -------- | -------- |
| `locate_block` | `row`, `col`：位置坐标 | 返回该坐标所在九宫格号码 | 解题 |
| `find_next_value` | `row`, `col`：位置坐标<br>`start`：填入数字初始值 | 从`start`开始查找下一个可填写的数字 | 解题 |
| `update_taken` | `row`, `col`：位置坐标<br>`direction`：`1`代表填入，`-1`代表删去 <br>`deleted`：`-1`代表填入，恢复所挖的空则为删去数值 | 更新`taken`填写状态。记录每行、列、宫的下标出现情况。 | 出题、解题 |
| `is_valid` | 无 | 若`taken`中存在大于`1`的元素，则无解，返回`false` | 解题 |
| `init_sudoku` | 无 | 初始化数独数组，并读入数据 | 解题 |
| `init_sudoku_for_generator` | 无 | 读入出题时提供的数据后初始化数独数组 | 出题 |
| `show` | `index`：`sudoku`数组的层数 | 输出`sudoku`数组第`index`层代表的数独阵。 | 解题 |
| `show_generator` | `index`：`sudoku`数组的层数 | 输出`sudoku`数组第`index`层代表的数独阵。不同于`show()`函数，允许输出空位。 | 出题 |
| `add_solution` | 无 | 存储已找到的解，以便`solve`继续回溯 | 解题 |
| `solve` | `row`, `col`：位置坐标 | 解题主函数。利用回溯算法解题。 | 解题 |
| `print_solution` | 无| 解题过程结束后，按照题目要求输出解题情况和解 | 解题 |
| `change_str` |`int* row`| 出题时将随机打乱的一行数字变成字符串 | 出题 |
| `generate` |无| 出题主函数之一。对生成的完整数独阵进行挖空。 | 出题 |
| `generator` |无| 出题主函数之一。一直挖空，直到挖空个数达到目标（`WILL_DIG`）。 | 出题 |

### 设计思路

#### 解题算法设计思路：回溯

1. 从输入的9*9数独阵左上角开始，将空的位置填入数。
2. 行、列、宫的规则若被满足则寻找下一个可填位置并填数，若不满足则更换数重新填写或回溯。
3. 若数独阵全部填完，则对解进行记录，并继续回溯填写。
4. 重复第三步：
1. 若无解，则输出无解。
2. 若只有一解，则输出一解。
3. 若已有两解，则不再向下寻找，并输出两解。

#### 出题算法设计思路：挖空

1. 为了保证出题的随机性，将9*9数独阵的第一行随机排列。
2. 使用解题时的函数，找到该行下的一种合法解。
3. 将这一组解作为基础，从数独阵的右下角开始挖空。
4. 每次挖空后使用解题时的函数判断是否解唯一，若唯一继续挖空，若不唯一跳过并向左移动，继续挖空。成功挖空后记录挖空个数。
5. 挖空个数若达到要求，便输出该挖空后的数独阵，若没有达到要求则重复1-4。

### 心得体会
经过这次数独大作业，我们充分了解到了团队合作的重要性，小组成员之间可以分享自己的一些学习资料，在互相讨论之中可以关于这个问题的解法有更清楚的了解。关于解数独和出数独这个问题本身，更多是关于算法和具体写代码上的一些学习，但是在具体实现之外，在整个大作业的完成过程中，我们经历了众多debug的过程。在“打补丁”、“重构代码”的过程中，在经历一次次成功实现与失败后，我们最终成功实现了要求。具体写代码的过程是这次大作业的核心，但是过程中的收获也是老师想要我们在团队合作中得到的。

另外为了解决写代码期间因长时间无法找到bug的位置的僵局，我们发现可以随机播放一些音乐音乐。我们发现每当播放到[Carmen - Toreador Song](https://bd.kuwo.cn/play_detail/40365963?from=baidu)的时候程序都能够被debug出来，顺利运行。我们还发现，播放音乐可以同时解决研讨间隔壁同学音量过大的问题，通过大音量播放音乐能够让他人意识到自己大声说话的错误行为，并及时纠正。可谓是一石二鸟。总结：音乐与编程是密不可分的，音乐是编程的必要条件。