第二次作业————个人项目实战

项目地址

https://github.com/raven031502225/one

项目需求

利用程序随机构造出N个已解答的数独棋盘

输入

数独棋盘题目个数N（0<N<=1000000）

输出

随机生成N个 不重复 的 已解答完毕的 数独棋盘，并输出到sudoku.txt中且左上角的第一个数为：（学号后两位相加）% 9 + 1

遇到的困难及解决方法

困难描述：

仅产生随机数判断是否能够填入如不能则换个随机数，如还是不行，则从头来，这种算法耗时太长

做过的尝试：

填的位置为随机，填的位置为同一个宫内的随机，最后使用逐行填入并回溯而不是全部重来

是否解决

已解决

收获

单纯是想出来的方法大多是很粗糙的，而更好的方法往往是在各种优化之后得到的

解题思路

原来闲的时候做过数独这种东西，当时是用来消磨时间的，觉得很熟悉，但是仔细思考之后才发现熟悉的仅仅是解数独的方法而不是设计的方法，所以最开始觉得只要是随机数，并且符合三种判断条件的就肯定能够填进去，所以最开始版本的代码甚至不能跑出一个完整的数独，最开始觉得是bug，输出了每一步的走法后才发现数独的生成并不是这么简单的东西，其实是非常容易出现冲突的，然后就想到原来做过的马踏棋盘的题，于是就使用了回溯法来生成数独。

关键代码or设计说明

部分代码

以下为判断此格是否能够填入此数的代码部分

if (tright[y][x][anyway - 1] == 0) {						//判断本格是否出现过此数并无法生成无冲突的数独
		if (square[(x / 3) + 3 * (y / 3)][anyway - 1] == 0) {	//判断本格所处的九宫格内是否存在此数
			if (upright[y][anyway - 1] == 0) {					//判断本格所处的行内是否存在此数
				if (transverse[x][anyway - 1] == 0) {			//判断本格所处的列内是否存在此数
					all[y][x] = anyway;							//将本数记录入数独内
					upright[y][anyway - 1] = 1;					//记录：本行已存在此数
					transverse[x][anyway - 1] = 1;				//记录：本列已存在此数
					square[(x / 3) + 3 * (y / 3)][anyway - 1] = 1;	//记录：本宫已存在此数
					y = y + x / 8;								
					x = (x + 1) % 9;							//移至下一个需要写入的位置
				}
				else tright[y][x][anyway - 1] = 1;				//本格不能填入此数
			}
			else tright[y][x][anyway - 1] = 1;					//同上
		}
		else tright[y][x][anyway - 1] = 1;						//同上上
	}
           

设计说明

第一个数是固定的，初始化则初始化时直接将其初始化，接下来逐行试图填入数字，每次生成一个随机数，将其固定到0-5的范围内，然后再判断是否符合三个限制条件并是否已经在这个格子里出现过并且无法生成正确的数独终盘，如果均符合限制则填下此数并进行下一格的填充，如果此格九个数均不可填充，则回溯一格，若全部填充完毕之后，则将最后一个数标记为不可用并重新推导则可以得到不重复的数独终盘。

测试运行

通过命令行运行程序：

运行程序所输出文件的部分截图：

程序的改进

程序改进所消耗的时间零零散散加起来大概有8-9个小时，最开始时是随机出一个数如果本位9个都不能使用则全盘推倒重来，这样就导致程序运行时间非常的长，跑1000平均需要花费20s左右，这时想到了回溯，但是这时候的回溯并不是挨位来回溯，而是如果本位9个都不能使用则回溯一行，这样有了一定的性能提高，1000基本上需要15s，但是这时候和同学们讨论题的时候他们提到了曾经打过的马踏棋盘的题目，这时候才想起来逐位回溯......于是改为逐位回溯，这样1000仅需要1-2s就可以跑出来了，而且还不需要担心前面两种方法所可能出现的重复问题。

性能分析图：

执行力、泛泛而谈的理解

泛泛而谈

指肤浅的讲出看法。浮于表面，没有深入研究。

——引用自百度百科

泛泛而谈其实就是没有经过太多的思考而就说空话的结果，就像是我们打代码，拿到题目时刚开始时脑子里划过的想法就大都是泛泛而谈，就是没有经过深思，通常是最暴力的解法，非常粗糙，没有经过任何的推理过程，没有经过任何的优化而想出的解法，甚至大多时候都是错误的解法，所以要经过深思才能下手去开始编码，而不是想到什么就些什么，就是说不能泛泛而谈

执行力

执行力是指有效利用资源、保质保量达成目标的能力，指的是贯彻战略意图，完成预定目标的操作能力。是把企业战略、规划、目标转化成为效益、成果的关键。

执行力包含完成任务的意愿，完成任务的能力，完成任务e的程度。对个人而言执行力就是办事能力；对团队而言执行力就是战斗力；对企业而言执行力就是经营能力。

简单来说就是行动力。

对于我们来说，执行力的一种表现就是任务要在deadline之前完成，而且越早体现的执行力就越强，就像老师在评分中所提到的问题

• 个人认为大部分问题最终是归为 “执行力” 问题

  - 你是否打算解决这个问题？

  - 你是打算 现在 开始解决这个问题，还是等等再说吧？

  - 你是否定下一个可衡量的目标，比如每天2小时泡图书馆，具体2小时要如何分配？是想想就算了，还是真的去做了？2小时太多？如果你有充分的理由，调整！没问题！

  - 一件事情是否需要专门筹划一天或者几天来做，时间不到就无所谓？

  - 如果“专用”的时间被外界打断，你要怎么办？

  - 如果时间预估错误，deadline完不成怎么办？

  - 所以能否有一点空闲时间我们就把事情往前推进哪怕只有一点点？

——引用自【评分】软件工程实践2017第一次作业-准备

这些问题我在这里当然能够有回答：

• 当然打算解决执行力的问题
• 从现在开始解决这个问题
• 定下了可衡量的目标，虽然不是每天两小时泡图书馆，而是每天至少会看3小时的书，每天会分配好看哪种书的时间（订了闹钟（因为这个学期晚上都没有选修课而导致时间分配异常简单粗暴
• 原先预计耗时较长的事情就常常会特意空出一天或者几天的时间，而且会逼着自己必须要完成
• 如果“专用”的时间被外界打断，这时候会心很慌，如果不补上的话总觉得心不安，必须要补上，通常会占用原来计划的休息时间（例如熬夜
• 在老师规定deadline的时候其实自己就会给自己规定一个自己的deadline，在这个deadline之前必须要把任务完成到只差提交的地步，就像这次作业，写到这的时候是9月10日0:37，而我给自己的deadline就是9月10日睡觉之前，而且其实这部分是重写的，最开始对题目的理解有误，搞的准备睡觉了又从床上爬下来重写=。=要不然心慌。
• 在有任务的时候就常常有一种压迫感，在休息的时候也是休息不好的，所以只要有空闲时间当然就会吧事情往前推进，而为了长期有这种压迫感，我已经给自己订了一些计划并且订了闹钟来提醒自己。

PSP:

||||||

|:--|:--|:--|:--|

|PSP2.1|Personal Software Process Stages|预估耗时（分钟）|实际耗时（分钟）|

|Planning|计划|10|7|

|?Estimate|· 估计这个任务需要多少时间|10|7|

|Development|开发|370|430|

|?Analysis|· 需求分析 (包括学习新技术)|30|30|

|?Design Spec|· 生成设计文档|20|10|

|?Design Review|· 设计复审 (和同事审核设计文档)|10|10|

|?Coding Standard|· 代码规范 (为目前的开发制定合适的规范)|20|20|

|?Design|· 具体设计|40|30|

|?Coding|· 具体编码|120|200|

|?Code Review|· 代码复审|10|10|

|?Test|· 测试（自我测试，修改代码，提交修改）|120|120|

|Reporting|报告|80|90|

|?Test Report|· 测试报告|30|80|

|?Size Measurement|· 计算工作量|20|10|

|?Postmortem & Process Improvement Plan|· 事后总结, 并提出过程改进计划|30|20|

|合计||460|527|

另：虽然没选上实践课但请老师不要放弃我QAQ

学习进度条

第N周	新增代码（行）	累计代码（行）	本周学习耗时(小时)	累计学习耗时（小时）	重要成长
200		12		从同学们那里得到了很多的解题思路并学会了系统的优化代码的方法