数独-分析、设计、求解思路

需求分析

需求

运行一个命令行程序，程序能：
?1. 生成不重复的数独终局至文件。
?2. 读取文件内的数独问题，求解并将结果输出到文件。

数据建模

将数独分成9个宫进行求解，ER表示如下，因为数独左上角第一块确定，所以将其看作数独的属性。

功能建模

数据源：用户

数据终点：文件

主要数据流：生成指令、求解指令、数独（待求解），以及终局

主要支持文件：待求解数独文件

主要处理过程：生成终局、求解数独

0层图

??对系统进行求精，划分系统的子系统。

行为建模

解题思路

??在最开始拿到题目的时候，想起上学期算法课程学过的回溯算法，决定用会回溯算法进行实现，所以翻看了算法设计的课本和ppt，对回溯算法重新进行了学习。在生成n个不同局面和求解给定数独的思路大致一致，但有在细节处的处理有些不同。首先是生成n个不同的局面，按行进行循环，有一个二维数组保存每个位置的可能数字，从可能数字中随机选一个放在该位置，若该位置找不到可能的位置，则回到上一个，修改上一个位置的解。不断进行回溯，直到所有的位置都合法。若是对给定局面进行求解，则将空白位置用数组记录下来，只对空白位置进行回溯即可。

??但在该回溯算法中，搜索时盲目的，效率较低，最差的实现对每个空方格试探所有可能的数字，有大量的时间浪费。并且如果需要生成多个终局时，每一个终局都是通过回溯实现，且生成不同的终局由Random()进行数字选择实现，但实际上Random生成伪随机数，在一定时间会生成相同随机数，无法保证在生成终局数目足够大时，不会产生两个相同的终局。

??因为算法效率有很大的改进空间，以及无法保证在n足够大时，所有终局都相异，所以在对代码重构的过程中，引入了排列组合的算法，对原有进行优化。将数独分成9个3X3的小方块，每个小方块是一个宫。

??参考维基百科提供的一个生成终局思路，由第一宫生成其余八个宫。对第一宫中的块进行排列组合即可，因为生成终局时，要求左上角的第一个数为：（学号后两位相加）%9+1，(1+3)%9+1=5，所以左上角为5，且不允许改变。即在第一宫内只有八个块可以移动，有8!=40320种情况，并且在每一宫内（除了第一宫）进行列列变换有3!×3!×3!×3!=1296，第二宫和第三宫可以交换，第四宫和第七宫可以交换有2!×2!=4，总共可以生成209,018,880个终局(大于1,000,000)，此方案可行。

??对于各种全排列，使用递归的方式实现。

设计实现过程

???编译器：Intellij IDEA 2019.2
???语言：java
???运行环境：JDK 1.8

活动图

顺序图

??下面是生成终局的顺序图

??下面是求解数独的顺序图

类图

???共有三个类，Main用于判断输入是否合法、将终局写入文件、判断输入命令是否合法，Generate类用于生成终局，Solve类用于求解数独。

具体代码说明

Generate中主要函数：

???generateSudoku 外部调用的接口，传入一个n(n<=1,000,000)，即可以生成n个终局。

??createSeed 将第一宫作为种子，进行交换操作，得到不同的种子。

??createMap 通过种子的变换，得到该种子生成的第一个终局。

??changeIndex 对于第一个终局进行行列变换，生成不同的终局。

??writeToOutput 将生成的int[ ] [ ]的终局，按照输出格式要求，存放在一个char[]中 。

changeIndex流程图如下

??具体实现代码如下所示，在goalNum=1时，不用进行变换，在>1开始，先交换index[16]和index[17]，即先在第三大列内进行列变换，可以有6中不同的终局，接着在第二大列内进行交换，依次类推，到行进行交换，可以快速产生大量不相同的终局。

/**
 * @Title: changeIndex
 * @Description: 对宫内的行列进行全排列
 * @param  a
 * @param  start
 * @param  end
 * @return void
 * @throws
 */
public void changeIndex( int start, int end) {
   int i;
   //分段进行全排列
   if (start == end) {
      if (end == 5) {
         changeIndex( 6, 8);
      }else if(end==8){
         changeIndex( 12, 14);
      }else if(end==14){
         changeIndex( 15, 17);
      }
      else {
         writeToOutput();
      }
   }
   else {
      for (i = start; i <= end; i++) {
         swap(index, start, i);
         changeIndex( start + 1, end);
         if (nowNum == goalNum) break;
         swap(index, start, i);

      }
   }
}

Solve中主要函数

??findSolution外部调用的接口，传入一个txt的绝对路径，即可对该txt中的数独进行求解。

??dealFile将txt中的所有数独，存在一个int[]中，并得到要求解的数独数目。

??initCriterion将Criterion(表示行列宫没有用过的数)初始化，并将数独中出现过的数在Criterion进行标记。

??chooseCriterion递归对数独进行求解。

chooseCriterion流程图

??chooseCriteron和dealWithCriterion是求解数独的主要两个函数。chooseCriterion中state表示当前是否能找到可行解，找到返回true，没找返回false。先循环1-9九个数，找到一个所在行、列、宫都没有使用过的数放入，然后调用dealWithCriterion函数，若后面的位置没有待求解位置，则返回true，此时state为true，结束求解。若后面仍有待求解位置(a,b)，则dealWithCriterion函数返回chooseCriterion(a, b)进行求解，若可以找到可行解，则前面所求解保留，若找不到，则修改前面找到的可行解。本质是利用回溯算法进行求解。

??起初两个函数写在一起，但在代码质量检查时，该函数复杂度太高，所以拆分成两个函数

/**
 * @Title: chooseCriterion
 * @Description: 回溯选择合适的数
 * @param row
 * @param col
 * @return boolean
 * @throws
 */
private boolean chooseCriterion(int row, int col) {
   int value;
   boolean state = false;
   for (int k = 0; k < 9; k++) {
      if(!state) {
         value = k + 1;
         if (!fill(row, col, value)) {
            continue;
         }
         map[row][col] = value;
         usedNum(row, col, value);
         state = dealWithCriterion(row, col);
         if (!state) {
            releaseNum(row, col, value);
            map[row][col] = 0;
         }
      }
   }
   return state;
}

/**
 * @Title: dealWithCriterion
 * @Description: 查找是否有空位要求解
 * @param  row
 * @param  col
 * @return boolean
 * @throws
 */
public boolean  dealWithCriterion( int row, int col) {
    //没有空位
    boolean state = false;
    for (; row < 9; row++) {
        for (; col < 9; col++) {
            if (map[row][col] == 0) {
                state = true;
                break;
            }
        }
        if (state)
            break;
        col = 0;
    }
    //没有空位
    if (!state) {
        return true;
    }
    return chooseCriterion(row, col);
}

Main中主要函数

?stringToFile传入一个char[]，将其写入可执行文件同级文件夹中的layout.txt(没有会创建)。

?isNumeric，whetherSolve，whetherGenerate都是判断输入是否合法。