1 package sudoku; 2 public class shudu { 3 static int [][]n=new int[9][9]; 4 static int[] num={1,2,3,4,5,6,7,8,9}; 5 public static void main(String[] srgs){ 6 // TODO 自动生成的方法存根 7 for(int i=0;i<9;i++){ //生成数字 8 int time=0; //记录填充数字的次数 9 for(int j=0;j<9;j++){ //填充数字 10 n[i][j]=generateNum(time); //产生数字 11 if(n[i][j]==0){ //如果返回是的0，说明此时出现重复数字，不能进行数字填充，要进行回溯 12 if(j>0){ //回溯原则：如果不是该行的第一格，则往左退一格，否则退到上一行的最后一格 13 j-=2; // 不是该行的第一格，则往左退一格 14 continue; 15 } 16 else{ 17 i--; //是该行的第一格，退到上一行的最后一格 18 j=8; 19 continue; 20 } 21 } //数字填充成功 22 if(isCorret(i,j)){ 23 time=0; //对数字填充的次数进行初始化，为下一次填充进行做准备 24 } 25 else{ 26 time++; //继续填充，填充次数+1 27 j--; //继续填充该行剩下的格子 28 } 29 } 30 } //对数独填充完毕后，将数独进行输出 31 for(int i=0;i<9;i++){ 32 for(int j=0;j<9;j++){ 33 System.out.print(n[i][j]+" "); 34 } 35 System.out.println(); 36 } 37 } 38 private static int generateNum(int time) { //产生1-9的随机数字，随机数字生成规则：利用Random函数生成随机数字，生成的随机数字是存放在数组8-time下标的位置 39 // TODO 自动生成的方法存根 40 if(time==0){ //第一次尝试，对随机数字源组进行初始化操作 41 for(int i=0;i<9;i++){ 42 num[i]=i+1;// 生成随机数字，该数字是数组的下标，取数组num中该下标对应的数字为随机数字 43 } 44 } 45 if(time==9){ //第十次尝试，说明该位置没有符合条件的数字，则返回0，由主程序进行回溯操作 46 return 0; 47 } 48 //随着time的增加，前面试过的数字将不会再取到,因为第一次的数字是在生成随机数字中随机选择的，第二次则是在剩下的随机数字中进行选择，以此类推…… 49 int ranNum=(int)(Math.random()*(9-time)); //把数字放置在数组倒数第time个位置 50 int temp=num[8-time]; 51 num[8-time]=num[ranNum]; 52 num[ranNum]=temp; 53 return num[8-time]; 54 } 55 public static boolean isCorret(int row,int col){ //在填充过程中，对填充的数字进行判断是否合法，对该行、该列、该宫是否出现重复数字 56 return(checkRow(row)&checkLine(col)&checkGong(row,col)); 57 } 58 private static boolean checkGong(int row, int col) { //在填充过程中，对该宫填充的数字进行判断是否合法，是否有重复数字出现 59 // TODO 自动生成的方法存根 60 int j=row/3*3; //获取该格的坐标 61 int k=col/3*3; 62 for(int i=0;i<8;i++){ //在该宫内进行循环比较 63 if(n[j+i/3][k+i%3]==0){ 64 continue; 65 } 66 for(int m=i+1;m<9;m++){ 67 if(n[j+i/3][k+i%3]==n[j+m/3][k+m%3]){ 68 return false; //返回false代表不合法 69 } 70 } 71 } 72 return true; //返回true代表合法 73 } 74 private static boolean checkLine(int col) { //在填充过程中，对该列填充的数字进行判断是否合法，是否有重复数字出现 75 // TODO 自动生成的方法存根 76 for(int j=0;j<8;j++){ 77 if(n[j][col]==0){ 78 continue; 79 } 80 for(int k=j+1;k<9;k++){ 81 if(n[j][col]==n[k][col]){ 82 return false; //返回false代表不合法 83 } 84 } 85 } 86 return true; //返回true代表合法 87 } 88 private static boolean checkRow(int row) { //在填充过程中，对该行填充的数字进行判断是否合法，是否有重复数字出现 89 // TODO 自动生成的方法存根 90 for(int j=0;j<8;j++){ 91 if(n[row][j]==0){ 92 continue; 93 } 94 for(int k=j+1;k<9;k++){ 95 if(n[row][j]==n[row][k]){ 96 return false; //返回false代表不合法 97 } 98 } 99 } 100 return true; //返回true代表合法 101 } 102 }
以上是全部代码，附上几个生成的数独：
2 9 8 1 5 6 7 3 4
6 7 1 8 4 3 5 2 9
3 4 5 2 7 9 8 6 1
8 1 9 6 3 7 4 5 2
4 2 6 5 8 1 9 7 3
7 5 3 9 2 4 1 8 6
1 3 2 7 9 5 6 4 8
5 6 4 3 1 8 2 9 7
9 8 7 4 6 2 3 1 5
------------------
5 2 7 9 3 4 1 6 8
1 9 6 8 2 5 4 3 7
3 4 8 7 1 6 5 2 9
9 7 3 4 5 2 8 1 6
6 8 2 1 7 9 3 5 4
4 5 1 3 6 8 7 9 2
2 3 4 6 8 1 9 7 5
7 6 9 5 4 3 2 8 1
8 1 5 2 9 7 6 4 3
------------------
7 3 9 8 2 5 4 1 6
6 5 4 7 9 1 3 2 8
2 8 1 3 4 6 5 9 7
1 9 6 2 8 4 7 3 5
8 7 5 6 3 9 1 4 2
4 2 3 5 1 7 6 8 9
3 1 7 9 5 8 2 6 4
9 6 2 4 7 3 8 5 1
5 4 8 1 6 2 9 7 3
分析：该程序正确，能正确输出数独，能达到题目要求，可输出百万级别的数独；该程序代码量较少，能在0.3856秒内输出结果，性能较好。
心得：本次作业中，花了一天和2个晚上才做完，一开始在网上进行资料查询，对什么是数独进行了解，然后也查了一下别人是怎么实现的，总体来说，本题有3种方法（自认为，或许还有很多，只是我不知道而已），第一种就是从第一宫的第一格开始填数，从左到右从上往下进行填数，每填一个数就对该数所在行、列、宫进行检查该数是否合法，如果不合法，就进行回溯，重新填写，一直循环，循环到填满9个宫；第二种就是在每个宫中进行随机填写一个相同的随机数，然后对填的数所在行、列、宫进行检查该数是否合法，如果不合法，就进行回溯，重新填写，一直循环，循环到填满9个宫为止；第三种就是先对数独的两条对角线进行填充，然后按照第一种方法进行填充，一直到填满为止。以上3种方法，各有各的优点，我所选的方法是第一种，我猜大部分人应该是第一种，因为这个是比较容易想到的，在进行回溯的过程中，是按照以下规则进行回溯，回溯原则：如果不是该行的第一格，则往左退一格，否则退到上一行的最后一格。
在做本次作业中，对自己的编程能力是一种锻炼，我以前编程能力较为欠缺，通过这次作业，对我的编程能力有一定的提高，特别是在思考题目过程中，自己思维能力的提升是最明显的，对问题的考虑也比以前更加细致，对题目中所能出现的问题也考虑的更加全面，在本次题目中遇到的问题便是怎么进行回溯，回溯的规则是怎样的，经过自己的努力，终于把这个问题想清楚了，然后通过编程将其实现。在做数独题目过程中，本算法较为快速的原因在于产生1-9的随机数字，本题中随机数字生成规则：利用Random函数生成随机数字，生成的随机数字是存放在数组8-time下标的位置，这样可以保证前面填充的数字不会再拿出来进行填充，就可以省下对不符合要求数字的尝试时间，大大提高程序的运行时间，不这样做，虽然也能做出来，但是运行速度可能会打折扣。
本次做题的收获便是想到什么不动手去实现是没用的，想出来觉得很简单，可实际并不一定，只有你通过自己行动把它实现了才知道容不容易，勤思考，多行动，付出实践的思考才是有用的思考。
课外任务作业：从链接的调查表中发现，我觉得：语言、需求分析、项目管理、团队协作、理论素养这5部分对我个人来说比较重要，语言学了不下于10种，却没有一个精通的，简言之“多而不精”；需求分析方面，对软件所需要考虑的各方各面考虑的还不是很清楚，导致做出来的APP有很多bug，或者一些功能不尽人意；项目管理方面，带过好几个项目，最终都勉强完成，但是没有达到自己想要的结果；团队协作方面自认为还可以；理论素养还得继续加强。希望这门课程结束后，自己能有所提高这几方面。