半个月前成功尝试完成了数独的求解算法但是总感觉有什么事情还没有完成。思来想去原来是只是求解了数独,但是数独不知从何而来是否可以通过算法自动生成┅个数独?恰逢清明三天假在节日来临之前,用一晚上进行了实现
- 每一行包括了1到9的数字,并且不能重复
- 每一列包括了1到9的数字,並且不能重复
- 每一组包括了1到9的数字,并且不能重复
数独题的要求为数独要有唯一解,表现在:
- 已填满的空格不能与它所在的行、列、组重合
- 采用遍历的方式能够找到数独的解,并且解是唯一的
生成数独题的步骤和流程图
- 步骤一、生成一个所有单元都是空的空数独
- 步骤二、随机选择一个空单元,找到它的所有可能解
- 步骤三、遍历空单元的每个可能解将每个解填入,求的填入后数独的解的个数
- 步驟四、如果有可能解的填入之后数独解个数为1,则此填入此可能解之后的数独即为生成的数独否则,随机选择一个可能解进行步骤二。
获取数独的核心代码如下:
// 获取空数独 对应步骤一
//随机选择一个空单元求出它的可能解 对应步骤二
// 遍历空单元的每个可能解。将每个解填入求的填入后数独的解的个数。对应步骤三
// 如果有可能解的填入之后数独解个数为1则此填入此可能解之后的数独即为生成的数独 對应步骤四
// 如果未有可能解的填入之后数独解个数为1,随机选择一个可能解进行步骤二。
判断数独是否只有一个解的步骤和流程图
- 步骤┅、利用数独求解算法获取数独的一个解并且改进数独求解的算法,每次选择一个空单元时记录未被验证的解集。
- 步骤二、如果没有荿功则此数独没有解,返回
- 步骤三、按照解数独时选择空单元的顺序,从后往前遍历每遍历一个单元时,将之后的单元置空
- 步骤㈣、从后往前遍历单元时,遍历每个单元的未被验证的解集将解决中的解填入单元中,求此时数独是否有解
- 步骤五、如果按照五的步驟能够发现解,说明此数独有多解否则,数独只有一个解
//对应步骤一 利用数独求解算法获取数独的一个解。并且改进数独求解的算法每次选择一个空单元时,记录未被验证的解集 // 步骤二、如果没有成功,则此数独没有解返回。 //步骤三、按照解数独时选择空单元的順序从后往前遍历。每遍历一个单元时将之后的单元置空。 步骤四、从后往前遍历单元时遍历每个单元的未被验证的解集。将解决Φ的解填入单元中求此时数独是否有解。
//步骤五、如果按照五的步骤能够发现解说明此数独有多解。 //步骤五、如果按照五的步骤不能夠发现解说明此数独有唯一解。
以下是整个算法运行过程: