软件工程实践2019第三次作业

Github项目地址：https://github.com/huarangmeng/031702142

PSP表格如下：

PSP2.1 Personal Software Process Stages 预估耗时（分钟） 实际耗时（分钟）
Planning 计划 20 20
Estimate 估计这个任务需要多少时间 20 20
Development 开发 340 300
Analysis 需求分析（包括学习新技术） 40 60
Design Spec 生成设计文档 20 10
Design Review 设计复审 10 10
Coding Standard 代码规范（为目前的开发制定合适的规范） 10 5
Design 具体设计 30 30
Coding 具体编码 160 120
Code Review 代码复审 30 45
Test 测试（自我测试，修改代码，提交修改） 50 60
Reporting 报告 30 30
Test Report 测试报告 10 10
Size Measurement 计算工作量 10 10
Postmortem & Process Improvement Plan 事后总结，并提出改进计划 10 10
合计 390 350

思路历程

  1. 之前没有玩过数独，只能查询数独的解法，看了一部分“唯一解”法，发现不太能理解，之后寻找到了回溯解法。
  2. 尝试先对九阶标准数独进行求解，完成主体思路
    • 对数独数组matrix[][] 从左至右，从上至下依次遍历，matrix[][]==0，代表可填写部分
    • 对可填写部分，进行填数检测 check(row,line,num) ,如果通过，则martrix[row][line]=num, 进入下一个位置 backTrace(row,line+1),最关键点，要将matrix[row][line]=0,恢复原状，如果下一次填数失败，要回溯重新试下一个数字
    • check(row,line,num)函数，需要检测当前行列宫均与Num不同，否则返回false
  3. 主体思路结束后，发现需要使用命令行输入输出文件，不会，嗯，就是不会。开始学，从JAVA输入输出文件开始还行，命令行参数获取有点懵逼，靠着@衡与墨 助教在微信群里的代码才运行了。
  4. 之后才对3-9阶进行区分，唯一需要改动的地方就是check()函数
    • 将3，5，7阶分为一类，即只需要检测行与列是否相同
    • 4，9阶分为一类，即行、列宫数均为sqrt（阶）
    • 6单独，8单独，需要检测宫的方法与其他不同

函数关联

代码改进

原本代码只针对存在解的数独进行求解，不存在报错机制。
改进增加这一部分，增加是否存在解判断 flag ，flag初始化为false，若有解 flag =true.
代码如下：

//Judging Solvability
        if(flag) {
            System.out.println("Success!!!!");
        } else{
           System.out.println("The test is insoluble!!!!!!");
           printf();
        }

代码读取文件部分：

File file = new File(inputFileName);

        int x[][] = new int[9][9];
        int row = 0;
        int line = 0;
        String str = "";
        if(! file.exists()){
            System.out.println("对不起，不包含指定路径的文件");
        }else{
            try{
                FileReader fr = new FileReader(file);

                char[] data = new char[23];
                int length = 0;

                while((length = fr.read(data)) >0){
                    str = new String(data,0,length);
                    for(int j = 0; j < str.length(); j++){
                        if(str.charAt(j) >47 && str.charAt(j)<58){
                            char c = str.charAt(j);
                            x[row][line++] = Character.getNumericValue(c);
                            if(line == phraseWordNum){
                                //Line feed
                                row++;
                                line = 0;
                            }
                        }
                        if(row == phraseWordNum){
                            //A disk is well stored
                            Lib lib = new Lib(x,phraseWordNum,outputFileName);
                            lib.Initialization();
                            row = 0;
                            line = 0;
                        }
                    }
                }
                //Close the read stream
                fr.close();
            }catch (Exception e){
                e.printStackTrace();
            }
        }

回溯解法主体：

 public void backTrace(int i, int j){
        //End of Arrival Output
        if(i == (rank-1) && j == rank){
            printf();
            flag = true;
            return;
        }

        //Arrive at the end of the column, wrap
        if(j == rank){
            i++;
            j = 0;
        }

        //If the lattice is empty, the judgement is entered.
        if(matrix[i][j] == 0){
            for(int k = 1; k <= rank; k++){
                //Check whether the requirements are met
                if(check(i,j,k)){
                    //Give the value K to the lattice
                    matrix[i][j] = k;
                    backTrace(i,j+1);
                    //Initialize the lattice
                    matrix[i][j] = 0;
                }
            }
        }else {
            backTrace(i,j+1);
        }
    }

检测所填数字合理性代码：

private boolean check(int row, int line, int k){
        //Query whether rows or columns have duplicate numbers
        for(int i = 0 ;i < rank; i++){
            if(matrix[row][i] == k || matrix[i][line] == k)
                return  false;
        }

        //Query if there are duplicate numbers in the Nine-palace grid
        if(rank == 4 || rank == 9){
            int gong = (int)sqrt(rank);
            int _row = row / gong;
            int _line = line / gong;
            for(int i = 0; i < gong; i++){
                for(int j = 0; j < gong ;j++){
                    if(matrix[_row*gong + i][_line*gong + j] == k)
                        return false;
                }
            }
        }else if(rank == 6){
            int _row = row / 2;
            int _line = line / 3;
            for(int i = 0; i < 2; i++){
                for(int j = 0; j < 3 ;j++){
                    if(matrix[_row*2 + i][_line*3 + j] == k)
                        return false;
                }
            }
        }else if(rank == 8){
            int _row = row / 4;
            int _line = line / 2;
            for(int i = 0; i < 4; i++){
                for(int j = 0; j < 2 ;j++){
                    if(matrix[_row*4 + i][_line*2 + j] == k)
                        return false;
                }
            }
        }

        return true;
    }

单元测试样例：

  1. 四阶数独

  2. 五阶数独

  3. 六阶数独

  4. 七阶数独

  5. 八阶数独

  6. 九阶数独

  7. 运行截图

性能分析

byte[], String ，类运行的最多，远大于其他，应该是参数输入，文件读取数字存为矩阵时使用过多
（JProfiler 不会用，参数看不太懂）

心路历程与收获

最开始心中完全对数独的陌生，寻找了很多关于数独解法的文章，看得头疼。
最大的收获应该是JAVA的文件输入输出，以及命令行运行JAVA项目吧，之前一直没有机会尝试过，这次终于接触了。
github上传代码，自己之前就试过一次，失败了，这次阴差阳错成功了？
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/huaranmeng/p/11574355.html