做招聘网站怎么设计框架,电影网站怎么做友情链接,网站系统参数设置,广东莞建建设工程有限公司前段时间出差在外闲得无事看到一个数独问题。有三题#xff0c;脑子不好使#xff0c;只做出前两题。想想不如用程序来实现。我先把题放出来大家有兴趣研究一下。8 5 7 1 1 9 2 6 2 5 6 9 2 4 5 8 8 1 2 …前段时间出差在外闲得无事看到一个数独问题。有三题脑子不好使只做出前两题。想想不如用程序来实现。我先把题放出来大家有兴趣研究一下。 8 5 7 1 1 9 2 6 2 5 6 9 2 4 5 8 8 1 2 4 9 4 6 5 7 5 8 9 1 5 2 1 9 6 3 3 5 7 6 6 1 4 7 7 2 6 4 5 3 8 6 9 7 8 3 5 8 3 9 8 7 6 1 7 1 9 3 6 4 5 2 8 8 1 7 2 2 7 6 6 7 6 5 3 5 4 8 规则在9*9的格子中用1到9填满格子每一行都要用到1~9位置不限每一列都要用到1~9位置不限每3*3格子都要用到1~9位置不限我的算法思想比较简单穷举法递归。1、初始化 新建两个数组A[9,9],B[9,9],他们的初始值都一样。 public static int[,,] A new int[9,9,9];?xml:namespace prefix o ns urn:schemas-microsoft-com:office:office / public static int[,] B new int[9,9]; for(int i0;i9;i) for(int j0;j9;j) A[i,j] 0; A[0,1]6; A[0,4]1; A[0,5]7; ……………… A[8,3]5; A[8,4]4; A[8,7]8; A[8,8]6; for(int m0;m9;m) for(int n0;n9;n) B[m,n] 0; B[0,1]6; B[0,4]1; B[0,5]7; ……………… B[8,3]5; B[8,4]4; B[8,7]8; B[8,8]6; 递归过程 public void JudgeNumber(int x,int y) { if(x9y9) //判断数组下标范围 { if(A[x,y] 0||A[x,y] ! B[x,y]) //如果数组的值为零或者取得的值不等于B的值 { for(int i1;i10;i) { A[x,y] i; //循环付值 if(Pass(x,y)) //判断条件 { if(Victory()) //成功 { printShuzu(); return ; } if(y8) //判断下一个数 JudgeNumber(x,y1); else JudgeNumber(x1,0); } } A[x,y] 0; //失败之后把值设为零以便继续判断 } else //判断下一个数 { if(y8) JudgeNumber(x,y1); else JudgeNumber(x1,0); } } } public ?xml:namespace prefix st1 ns urn:schemas-microsoft-com:office:smarttags /boolPass(int i,int j) { //判断横竖有无重复 for(int b0;b9;b) { if(b!i) if(A[i,j] A[b,j]) return false; if(b!j) if(A[i,j] A[i,b]) return false; } //判断*3有无重复 int q0 (i/3)*3; int k0 (j/3)*3; int q1 (i/31)*3; int k1 (j/31)*3; for(int qq0;qq1;q) for(int kk0;kk1;k) if(q!ik!j) if(A[i,j] A[q,k]) return false; return true; } /// summary /// 在Pass情况下如果整个数组无0表示成功求解 /// /summary /// returns/returns public bool Victory() { bool axfalse; for(int i0;i9;i) for(int j0;j9;j) { if( A[i,j] ! 0) ax true; else return false; } return ax; } 本算法的问题1.穷举取值过多。不必从1~9全部取2.成功后在递归里面不能跳出。对问题1的改进:1.新建3维数组A[9,9,9]2初始判断,获取该位置可取值的范围 for(int i0;i9;i) for(int j0;j9;j) { int[] B new int[9]; for(int d0;d9;d) B[d] d1; if(A[i,j,0]0) { for(int a0;a9;a) { A[i,j,0] B[a]; for(int b0;b9;b) { if(b!i) if(A[i,j,0] A[b,j,0]) B[a]0; if(b!j) if(A[i,j,0] A[i,b,0]) B[a]0; } int q0 (i/3)*3; int k0 (j/3)*3; int q1 (i/31)*3; int k1 (j/31)*3; for(int qq0;qq1;q) for(int kk0;kk1;k) if(q!ik!j) if(A[i,j,0] A[q,k,0]) B[a]0; A[i,j,0] 0; } } } 3.更改判断部分. public void JudgeNumber(int x,int y) { if(x9y9) { if(A[x,y,0] 0||A[x,y,0] ! B[x,y]) { for(int i1;i9;i)//更改部分 { if(A[x,y,i]!0)//更改部分 { A[x,y,0] A[x,y,i];//更改部分 if(Pass(x,y)) { if(Victory()) { printShuzu(); //return ; } if(y8) JudgeNumber(x,y1); else JudgeNumber(x1,0); } } } A[x,y,0] 0; } else { if(y8) JudgeNumber(x,y1); else JudgeNumber(x1,0); } } } 转载于:https://www.cnblogs.com/wssmax/archive/2006/08/25/486229.html
