利用程序随机构造N个已解答的数独棋盘
高级软件工程第二次作业：利用程序随机构造N个已解答的数独棋盘，代码如下：
package SudokuGame;
/**
* 解决这个问题使用的是回溯+剪枝的算法
* 基本思想：不断地将每个格子可填入的数字减少，如果当前格子没有数字可填入，就回溯到上一格
* 实现算法：首先初始化数独，将数独的第一行以随机数字填入，从第二行开始的每个格子都从1开始找可以填入的最小的数字，
在没有数字可填时，就开始回溯。 此算法在回溯的同时将不可能的结果排除，不会陷入死循环
*/ import java.io.File;
import java.io.FileWriter;
import java.io.IOException;
import java.util.Scanner; public class sudokuV2 { public static void main(String[] args) {
sudokuV2 sudoku = new sudokuV2();
int[][] square = new int[9][9]; //存放数独的二维数组 String pathName = "sudotiku.txt";
File file = new File(pathName);
if(file.exists()){
file.delete(); //此句话在每次执行程序时先删除已经存在的文件sudotiku.txt
}
//开始生成数独
sudoku.go(square); } /**
* 将square中生成的数独写到文件sudotiku.txt中
* @param square
*/
public void writerToFile(int [][] square) {
String pathName = "sudotiku.txt";
File file = new File(pathName); try {
if(!file.exists()) {//若文件不存在就创建一个新文件
file.createNewFile();
}
FileWriter fWriter = new FileWriter(file, true); //此处参数如果直接是整形，则会被当成ASCII码，最后输出时转换成ASCII码对应的字符
//所以此处将int型转换成String输出
for(int i = 0; i < 9; i++) {
for(int j = 0; j < 9; j++) {
fWriter.write(String.valueOf(square[i][j]) + "\t");
}
fWriter.write("\r\n");
}
fWriter.write("\r\n");
fWriter.close();
} catch (IOException e) {
e.printStackTrace();
}
} /**
* 接收用户输入的数字，若不符合要求则重新输入
* @return 返回用户输入的数字
*/
public int getNumber() {
int n; //用来接收用户想要生成的数独解的个数
do{
System.out.print("请输入要生成的数独的个数：(1~1000000之间)");
Scanner input = new Scanner(System.in);
n = input.nextInt();
if(n <= 0 || n >1000000) {
System.out.println("输入错误，请重新输入！");
}
}while(n <= 0 || n >1000000);
return n;
} /**
* 初始化九宫格，全部元素置0
* 并将数独的第一行填入随机数字
*/
public void init(int[][] square) {
/** 将大九宫格数字全部置0 */
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
square[i][j] = 0;
}
}
/** 将第一行填入随机数字 */
for(int i = 0,j =0; j < 9; j++) {
square[i][j] = findValueInFirst(square, i, j);
}
} /**
* 找到数独第一行可以填入的数字，并返回该数字
* @param square
* @param row
* @param col
* @return value 返回找到的合适的数字
*/
public int findValueInFirst(int[][] square, int row, int col) {
int value = 0; do{
value = (int)(Math.random() * 100) % 9 + 1 ;
if(rowCheck(square, row, col, value) == true) {
//如果value的值与第一行已有的值不重复，则返回value，将其存入square数组中
return value;
}
}while(true);
} /**
* 生成数独，从第二行开始，每个格子的可填入数字都从1开始试探，不符合则增加1
* @param square
*/
public void go(int[][] square) {
int n;
n = getNumber(); //用来接收用户想要生成的数独的个数
for(;n >= 1;n--) { //控制生成数独的个数
init(square);
/* 开始生成数独**/
int number ;
for (int i = 1; i < 9; i++) {
for (int j = 0; j < 9;) {
number = 0;
number = findValue(square, i, j);
if(number > 0) {
square[i][j] = number;
j++;
}else {
//没有找到可填入的值，开始回溯
if(j == 0) {//如果当前格子在第一列，则回溯到上一行的最后一格,此时需要将当前格子的数字置为0
square[i][j] = 0;
i--;
j = 8;
}else { //如果当前格子不在第一列，则回溯到同行的前一格
square[i][j] = 0;
j--;
}
}
}
}
writerToFile(square);
show(square);
System.out.println();
}
} /**
* 寻找可以填入格子的数字
* @param square
* @param row
* @param col
* @return
*/
public int findValue(int[][] square, int row, int col) { int temp = square[row][col];
if(temp == 0) {
//如果square当前的格子值为0，则说明在一个新的格子里，从1开始寻找可以填入的值
temp = 1;
}else {
//如果square当前的格子的不为0，则说明进入了回溯程序，将temp+1
temp++;
} boolean isChange = false; //记录temp是否有改变，用来判断循环是否继续 do {
/* tempValue用来记录进入循环时temp的值，以方便查看temp的值是否有变化 **/
int tempValue = temp;
if(rowCheck(square, row, col, temp) == false) {
//行内检查不唯一则temp在原来基础上+1
temp++;
isChange = true;
}
if(colCheck(square, row, col, temp) == false) {
//列内检查不唯一则temp在原来基础上+1
temp++;
isChange = true;
}
if(smallCheck(square, row, col, temp) == false) {
//小九宫格内检查不唯一则temp在上一步基础上+1
temp++;
isChange = true;
}
if(temp >= 10) {
//此时1~9均不能填入格子，需要进入回溯
return -1;
}
if(temp == tempValue) {
//全部检查完成后，若没有改变,则表示找到可以填入的值，返回temp
return temp;
}
}while(isChange == true); //isChange变成true，说明temp改变了，此时没有找到可以填入格子的值
return -1;
} /**
* 输出数独
* @param square
*/
public void show(int[][] square) {
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
System.out.print(square[i][j] + "\t");
}
System.out.println();
}
} /**
* 行检查：判断将要填入的数字是否与该行的元素有重复
* @param square 二维数组组成的大九宫格
* @param row 当前格子的行坐标
* @param col 当前格子的列坐标
* @param value 当前准备填入格子的数字
* @return 若value与该行已有的元素重复则返回false，不重复返回true
*/
public boolean rowCheck(int[][] square, int row, int col, int value) {
for(int j = 0; j < col ;j++ ) {//判断新填入的元素是否与该行的元素有重复
if(value == square[row][j]) {
return false;
}
}
return true;
} /**
* 列检查：判断将要填入的数字是否与该列的元素有重复
* @param square 二维数组组成的大九宫格
* @param row 当前格子的行坐标
* @param col 当前格子的列坐标
* @param value 当前准备填入格子的数字
* @return 若value与该列已有的元素重复则返回false，不重复返回true
*/
public boolean colCheck(int[][] square, int row,int col,int value) {
for(int i = 0; i < row ;i++ ) {//判断新填入的元素是否与该列的元素有重复
if( value == square[i][col] ) {
return false;
}
}
return true;
} /**
* 小九宫格检查：判断新填入的元素是否与其所在的小九宫格的元素有重复
* 想法：根据该格子所在的行和列判断所属的小九宫格的位置，然后分成九个小块分别判断
分别有九组 （0,0），（0,1），（0,2）
（1,0），（1,1），（1,2）
（2,0），（2,1），（2,2）
* @param square 二维数组组成的大九宫格
* @param row 当前格子的行坐标
* @param col 当前格子的列坐标
* @param value 当前准备填入格子的数字
* @return 若value与该小九宫格已有的元素重复则返回false，不重复返回true
*/
public boolean smallCheck(int[][] square, int row,int col,int value) { int x = row / 3; //（x，y）的组合表示小九宫格的位置
int y = col / 3; for(int i = 3 * x; i < 3 * x + 3 ;i++ ) {
for (int j = 3 * y; j < 3 * y + 3; j++) {
if(i == row && j == col) {
continue;
}
if(value == square[i][j]) {
return false;
}
}
}
return true;
}
}
以上为程序运行的全部代码。生成数独后将其写入文件“sudotiku.txt”中，也会在屏幕上显示。以下是运行结果：
请输入要生成的数独的个数：(1~1000000之间)3
9 3 5 7 1 8 2 4 6
1 2 4 3 5 6 7 8 9
6 7 8 2 4 9 1 3 5
2 1 3 4 6 5 8 9 7
4 5 6 8 9 7 3 1 2
7 8 9 1 2 3 5 6 4
3 4 1 6 7 2 9 5 8
5 6 2 9 8 1 4 7 3
8 9 7 5 3 4 6 2 1
4 5 1 9 7 8 2 3 6
2 3 6 1 4 5 7 8 9
7 8 9 2 3 6 1 4 5
1 2 3 4 5 7 6 9 8
5 4 7 6 8 9 3 1 2
6 9 8 3 1 2 4 5 7
3 6 2 5 9 1 8 7 4
8 1 5 7 2 4 9 6 3
9 7 4 8 6 3 5 2 1
4 8 1 5 2 7 6 9 3
2 3 5 1 6 9 4 7 8
6 7 9 3 4 8 1 2 5
1 2 3 4 5 6 7 8 9
5 4 7 8 9 1 2 3 6
8 9 6 2 7 3 5 1 4
3 1 2 6 8 4 9 5 7
7 5 4 9 3 2 8 6 1
9 6 8 7 1 5 3 4 2
程序运行的正确性以及性能分析：程序可以正确地运行出结果，计算1000个数独完全解大概用时926ms，理论上来说此程序可以得出9！个不同结果。另外，代码已经上传到coding，请老师指点。
学习过程及遇到的问题：
1、在做这次作业时，最开始我想到的方案是：用一个二维数组，每次填入格子中的值都是1~9中的随机数value，如果该数不符合数独要求，则value循环+1再填入，1~9都不能填入则回溯到上一格。此方法遇到了一个死循环，因为每次回溯到上一格后，该格子总是可以填入一个值，再开始下一格，因此导致死循环。
解决方法：在网上看到了目前这个算法，此算法每次都会排除不合适的数字（包括当前格不能填入的数字和填入此数字后导致后面的格子不能正确填入的数字），这样可以控制不陷入死循环。（PS：学习到别人的算法后，有试着再在每个格子填入随机数的基础上改进，但无可避免的落入死循环，这点不知道老师能否给出指点。）
2、本次作业从自己开始编程、遇到死循环再到寻找解决方案完成作业大概用了三到四天时间，通过本次作业锻炼了自己的编程能力，同时也看到了自己在算法设计上的不足，学习了别人的算法后才发现原来可以用这样的方式解决问题，还是受益匪浅。
关于课外任务：
问题：在你一生中身体最健康，精力最旺盛的时候，能在大学学习和研究，是一生中少有的机会。请说明一下，你已经具备的专业知识、技能、能力有哪些？离成为一个合格的 IT专业毕业生，在专业知识、技能、能力上还差距哪些？请看这个技能调查表， 从表中抽取 5 - 7 项你认为对你特别重要的技能， 记下你目前的水平， 和你想在课程结束后达到的水平 （必须至少列出 5 项）。链接： http://www.cnblogs.com/xinz/p/3852177.html
目前来说，我觉得我的专业知识与技能水平是比较差的，有些专业基础课之前没有学过，这些要利用课外的时间尽快补上。以下几项技能我觉得是比较重要的，希望课程结束之后可以在以下几个方面有较大的提升。
最新文章
- AOP学习心得&jdk动态代理与cglib比较
- CSS雪碧，即CSS Sprite 简单的例子
- Android属性动画完全解析(中)
- Hadoop2.6.0错误
- Apache server-status
- Struts2 语法--result type
- 【react-router】从Link组件和a标签的区别说起，react-router如何实现导航并优化DOM性能？
- 》》HTML5 移动页面自适应手机屏幕四类方法
- ACM 数塔
- Displaylink安卓驱动
- mysql 文件
- wtforms-表单生成及验证
- 爬坑Linux
- Luogu4139 上帝与集合的正确用法 拓展欧拉定理
- springboot + mybatis 的项目，实现简单的CRUD
- Android 将拼接好并加上边框的图片保存到内存卡中
- [LeetCode] 724. Find Pivot Index_Easy tag: Dynamic Programming
- Solr安装中文分词器IK
- 'wmic' 不是内部或外部命令，也不是可运行的程序 解决方法
- Windows下Python版本的切换
热门文章
- 【Linux】php7.2.8 + xdebug + composer + php代码覆盖率 + jenkins配置 （实操记录，亲测可用）
- mySql | Error: ER_DATA_TOO_LONG: Data too long for column 'base_info' at row 1
- css文本内容大于内本显示框设置其显示方式
- sed使用---转义字符
- Sass--传一个带值的参数
- html5 lineTo的使用例子
- 第03章 AOP前奏
- The Constructor with No Arguments
- 基于oracle 的PL/SQL编程 - 存储过程
- Java序列化及反序列化