关于一个最简单的数独解题实现与疑惑一
一、缘起
之前买了一本《算法的乐趣》,这么多日子里根本没看过。我可能是一个书籍的收藏者而不是读者,因为在办公室里的书架上琳琅满目的摆放了几十本书了,可所读者寥寥无几!言归正传,偶然看了这本书中关于数独的章节,觉得有意思,但书中代码不全,所以自己动手试试,看看能不能按照原作者的思路把这个问题解决了。
二、编码
1、首先说我自己是一个非常业余的编程爱好者,既不是本专业,也不从事相关工作,所以代码中肯定有很多乱七八糟的写法,如果有人看到后想揍人,那么。。。。。。
/// <summary> /// 关于单元格的类 /// </summary> [serializable] public class sudokucell { public int num; // 该单元格的值 public bool isfixed; // 该单元格是否是确定的数值 public list<int> candidatures ; // 候选数列表 public sudokucell() { candidatures = new list<int> { 1, 2, 3, 4, 5, 6, 7, 8, 9 }; // 候选数列表 } }
这里的思想是这样的,对于数独游戏而言(这里只考虑9*9),有81个格子。每个格子,可以认为是一个单元格。这里用sudokucell这个类来表示,同时,用一个候选数列表来表示该单元格还可以填入的数字。
2、再定义一个关于整个盘面的类,表示数独游戏自身,因为内容较多,我分开来写
/// <summary> /// 关于整个盘面的类 /// </summary> [serializable] public class sudokugame { ...... }
2.1、sudokugame类中,定义几个数据成员
// 定义单元格数组,表示81个单元格 public sudokucell[,] cells = new sudokucell[9,9]; // 记录已经确认的单元格的数量,就是那些数字已经确认无误的单元格的数量 public int fixedcount;
2.2、构造函数
/// <summary> /// 构造函数,自己给了一个局面 /// </summary> public sudokugame() { int[] data = new int[] { 7,6,1,0,3,0,0,2,0, 0,5,0,0,0,8,1,0,7, 0,0,0,0,0,7,0,3,4, 0,0,9,0,0,6,0,7,8, 0,0,3,2,7,9,5,0,0, 5,7,0,3,0,0,9,0,2, 1,9,0,7,6,0,0,0,0, 8,0,2,4,0,0,0,6,0, 6,4,0,0,1,0,2,5,0 };
for (int i = 0; i < 81; i++) { int num = data[i]; // 单个的值 cells[i / 9, i % 9] = new sudokucell(); cells[i / 9, i % 9].num = num; // 这里,把给定的盘面复制到cells中 if (num != 0) { cells[i / 9, i % 9].isfixed = true; fixedcount++; } } }
2.3、最终盘面输出
1 /// <summary> 2 /// 输出得到的结果 3 /// </summary> 4 public void writeresult() 5 { 6 console.writeline("当前的fixedcount为:{0},局面为:",fixedcount); 7 // 这里因为已知是9*9的数组 8 9 for (int i = 0; i < 9; i++) 10 { 11 for (int j = 0; j < 9; j++) 12 { 13 string s = cells[i, j].num.tostring(); 14 console.write(s + " "); 15 } 16 // 输出换行 17 console.writeline(); 18 } 19 }
2.4 、传入一个需要判定的位置,看该位置是否已经有确定的值,有的话就跳到下一个位置
/// <summary> /// 跳过已被确定好了数字的位置 /// </summary> /// <param name="sp">需要判断的位置,0-80 </param> /// <returns>比传入的位置+1的位置</returns> public int skipfixedcell(int sp) { // 判断传入的位置是否在数组范围内 if (sp<0 || sp >=81) { return 81; // 因为从0开始,sp=80的时候是最后一个位置,这个位置的数据是需要处理的,处理之后,sp就变为81了 } // 这里,要把这个sp修改为行列值 int row = sp / 9; int col = sp % 9; if (cells[row,col].isfixed == true) { // 如果当前位置已被确定,继续判定下一个位置 skipfixedcell(++sp); } return sp; }
2.5 、设置某个单元格的值
/// <summary> /// 将某个值,设置到某个指定的位置,并进行检验 /// </summary> /// <param name="row">需要设置的行号</param> /// <param name="col">需要设置的列号</param> /// <param name="num">需要设置的值</param> /// <returns></returns> public bool setcandidaturetofixed(int row,int col,int num) { //1、设置值 cells[row, col].num = num; // 确定已确认的数字 cells[row, col].isfixed = true; //2、排除相关20个格中候选数中的num值 if (!exclusivecorrelativecandidatures(row, col, num)) { return false; } //3、查看相关20格在删除num之后的状态,并且如果触发了唯一值,则继续进行递归 if (!processsinglescandidature(row, col)) { return false; } //4、到这里,说明前面填入的num没有问题,可以确定这个单元格的数字了 fixedcount++; return true; }
2.6、删除相关20格的函数
1 /// <summary> 2 /// 在某个单元格的相关20格中删除该单元格已经确定的数字 3 /// </summary> 4 /// <param name="row">该单元格所在的行</param> 5 /// <param name="col">该单元格所在的列</param> 6 /// <param name="num">该单元格的填充值</param> 7 /// <returns>要删除的数字如果不存在,则证明错误,返回false</returns> 8 public bool exclusivecorrelativecandidatures(int row,int col,int num) 9 { 10 // 遍历行 11 for (int currentcol = 0; currentcol < 9; currentcol++) 12 { 13 // 传入的数字的当前数的位置自然要跳过的,自己和自己比是没有意义的 14 if (currentcol == col) 15 { 16 continue; 17 } 18 // 如果当前单元格未确定数字 19 if (!cells[row, currentcol].isfixed ) 20 { 21 //如果候选数中存在这个要删除的数字 22 if (cells[row, currentcol].candidatures.contains(num)) 23 { 24 // 如果要删除的数字是这个候选数列表的最后一个数字了 25 // 那么删除的话,导致候选数列表为空,则表示数据填入错误了 26 if (cells[row, currentcol].candidatures.count == 1) 27 { 28 return false; 29 } 30 // 从候选数列表中删除这个指定的数字 31 cells[row, currentcol].candidatures.remove(num); 32 } 33 } 34 else 35 { 36 // 对于已经确定了数字的单元格,则要比较是否与新填入的数字一致 37 if (cells[row, currentcol].num == num) 38 { 39 return false; 40 } 41 } 42 } 43 // 遍历列 44 for (int currentrow = 0; currentrow < 9; currentrow++) 45 { 46 if (currentrow == row) 47 { 48 continue; 49 } 50 // 如果当前单元格未确定数字 51 if (!cells[currentrow, col].isfixed) 52 { 53 //如果候选数中存在这个要删除的数字 54 if (cells[currentrow, col].candidatures.contains(num)) 55 { 56 // 如果要删除的数字是这个候选数列表的最后一个数字了 57 // 那么删除的话,导致候选数列表为空,则表示数据填入错误了 58 if (cells[currentrow, col].candidatures.count == 1) 59 { 60 return false; 61 } 62 // 从候选数列表中删除这个指定的数字 63 cells[currentrow, col].candidatures.remove(num); 64 } 65 } 66 else 67 { 68 // 对于已经确定了数字的单元格,则要比较是否与新填入的数字一致 69 if (cells[currentrow, col].num == num) 70 { 71 return false; 72 } 73 } 74 } 75 // 遍历所在的九宫格 76 // 这里,可以把81格看成9个9*9的九宫格,那么根据row、col的值,让其除以3,则可以得到 77 // 0,0 0,1 0,2 78 // 1,0 1,1 1,2 79 // 2,0 2,1 2,2 80 // 得到这样的位置信息 81 // 再进一步,这里用一个3维数组来表示怎么样?这里估计可能是一个笨方法 82 // 我的想法是可以避免去判断某个位置的九宫 83 int[,][] arr = new int[3,3][]; 84 arr[0, 0] = new int[] { 0, 1, 2, 9, 10, 11, 18, 19, 20 }; 85 arr[0, 1] = new int[] { 3, 4, 5, 12, 13, 14, 21, 22, 23 }; 86 arr[0, 2] = new int[] { 6, 7, 8, 15, 16, 17, 24, 25, 26 }; 87 arr[1, 0] = new int[] { 27, 28, 29, 36, 37, 38, 45, 46, 47 }; 88 arr[1, 1] = new int[] { 30, 31, 32, 39, 40, 41, 48, 49, 50 }; 89 arr[1, 2] = new int[] { 33, 34, 35, 42, 43, 44, 51, 52, 53 }; 90 arr[2, 0] = new int[] { 54, 55, 56, 63, 64, 65, 72, 73, 74 }; 91 arr[2, 1] = new int[] { 57, 58, 59, 66, 67, 68, 75, 76, 77 }; 92 arr[2, 2] = new int[] { 60, 61, 62, 69, 70, 71, 78, 79, 80 }; 93 94 // 获取给定的点所在的位置,可以从上述的二维数组中定位 95 int r = row / 3; 96 int c = col / 3; 97 98 // 根据二维数据的定位,获取了在3维数组中的值 99 for (int i = 0; i < 9; i++) 100 { 101 int indexofall = arr[r, c][i]; 102 // 把诸如14,21这样的值再转化为row、col形式 103 int rr = indexofall / 9; 104 int cc = indexofall % 9; 105 106 // 判断是否是当前位置 107 if (rr == row && cc == col) 108 { 109 continue; 110 } 111 112 if (!cells[rr, cc].isfixed) 113 { 114 //如果候选数中存在这个要删除的数字 115 if (cells[rr, cc].candidatures.contains(num)) 116 { 117 // 如果要删除的数字是这个候选数列表的最后一个数字了 118 // 那么删除的话,导致候选数列表为空,则表示数据填入错误了 119 if (cells[rr, cc].candidatures.count == 1) 120 { 121 return false; 122 } 123 // 从候选数列表中删除这个指定的数字 124 cells[rr, cc].candidatures.remove(num); 125 } 126 } 127 else 128 { 129 // 对于已经确定了数字的单元格,则要比较是否与新填入的数字一致 130 if (cells[rr, cc].num == num) 131 { 132 return false; 133 } 134 } 135 } 136 return true; 137 }
2.7、查看相关20格函数,看是否有唯一解出现
1 /// <summary> 2 /// 查看相关20格的状态,是否存在唯一候选数,存在,则继续调用setcandidaturetofixed 3 /// </summary> 4 /// <param name="row">该单元格所在的行</param> 5 /// <param name="col">该单元格所在的列</param> 6 /// <returns>是否存在错误</returns> 7 public bool processsinglescandidature(int row, int col) 8 { 9 // exclusivecorrelativecandidatures,该函数保证了候选数至少会存在一个 10 // 遍历行 11 for (int currentcol = 0; currentcol < 9; currentcol++) 12 { 13 // 需要判断是否是当前的位置 14 if (currentcol == col) 15 { 16 continue; 17 } 18 // 如果当前单元格的数字没有确定,而且只有一个候选数 19 if (!cells[row, currentcol].isfixed && cells[row, currentcol].candidatures.count == 1) 20 { 21 // 那么就应该把这个数字确定,并且以它为原则,继续确认其他数字 22 int num = cells[row, currentcol].candidatures[0]; 23 24 // 递归调用,继续搜寻 25 //fixedcount++; 26 //if (!processsinglescandidature(row, currentcol)) 27 //{ 28 // return false; 29 //} 30 31 32 if (!setcandidaturetofixed(row, currentcol, num)) 33 { 34 return false; 35 } 36 } 37 } 38 // 遍历列 39 for (int currentrow = 0; currentrow < 9; currentrow++) 40 { 41 // 需要判断是否是当前的位置 42 if (currentrow == row) 43 { 44 continue; 45 } 46 // 如果当前单元格的数字没有确定,而且只有一个候选数 47 if (!cells[currentrow, col].isfixed && cells[currentrow, col].candidatures.count == 1) 48 { 49 // 那么就应该把这个数字确定,并且以它为原则,继续确认其他数字 50 int num = cells[currentrow, col].candidatures[0]; 51 // 递归调用,继续搜寻 52 //fixedcount++; 53 //if (!processsinglescandidature(currentrow, col)) 54 //{ 55 // return false; 56 //} 57 58 if (!setcandidaturetofixed(currentrow, col, num)) 59 { 60 return false; 61 } 62 } 63 } 64 // 遍历所在的九宫格 65 // 这里,可以把81格看成9个9*9的九宫格,那么根据row、col的值,让其除以3,则可以得到 66 // 0,0 0,1 0,2 67 // 1,0 1,1 1,2 68 // 2,0 2,1 2,2 69 // 得到这样的位置信息 70 // 再进一步,这里用一个3维数组来表示怎么样? 71 // 我的想法是可以避免去判断某个位置的九宫 72 int[,][] arr = new int[3, 3][]; 73 arr[0, 0] = new int[] { 0, 1, 2, 9, 10, 11, 18, 19, 20 }; 74 arr[0, 1] = new int[] { 3, 4, 5, 12, 13, 14, 21, 22, 23 }; 75 arr[0, 2] = new int[] { 6, 7, 8, 15, 16, 17, 24, 25, 26 }; 76 arr[1, 0] = new int[] { 27, 28, 29, 36, 37, 38, 45, 46, 47 }; 77 arr[1, 1] = new int[] { 30, 31, 32, 39, 40, 41, 48, 49, 50 }; 78 arr[1, 2] = new int[] { 33, 34, 35, 42, 43, 44, 51, 52, 53 }; 79 arr[2, 0] = new int[] { 54, 55, 56, 63, 64, 65, 72, 73, 74 }; 80 arr[2, 1] = new int[] { 57, 58, 59, 66, 67, 68, 75, 76, 77 }; 81 arr[2, 2] = new int[] { 60, 61, 62, 69, 70, 71, 78, 79, 80 }; 82 83 // 获取给定的点所在的位置,可以从上述的二维数组中定位 84 int r = row / 3; 85 int c = col / 3; 86 87 // 根据二维数据的定位,获取了在3维数组中的值 88 for (int i = 0; i < 9; i++) 89 { 90 int indexofall = arr[r, c][i]; 91 // 把诸如14,21这样的值再转化为row、col形式 92 int rr = indexofall / 9; 93 int cc = indexofall % 9; 94 // 需要判断是否是当前的位置 95 if (rr == row && cc == col) 96 { 97 continue; 98 } 99 if (!cells[rr, cc].isfixed && cells[rr, cc].candidatures.count == 1) 100 { 101 // 那么就应该把这个数字确定,并且以它为原则,继续确认其他数字 102 int num = cells[rr, cc].candidatures[0]; 103 // 递归调用,继续搜寻 104 105 //fixedcount++; 106 //if (!processsinglescandidature(rr, cc)) 107 //{ 108 // return false; 109 //} 110 111 if (!setcandidaturetofixed(rr, cc, num)) 112 { 113 return false; 114 } 115 } 116 } 117 return true; 118 }
3、游戏类,问题在这里,随后再说
1 /// <summary> 2 /// 问题解决类 3 /// </summary> 4 public class solution 5 { 6 public static int gamecount = 0; 7 // 3、类似于穷举的算法 8 /// <summary> 9 /// 求解算法,这是一个递归算法 10 /// </summary> 11 /// <param name="game">当前的局面</param> 12 /// <param name="sp">查找的位置,从0开始,到80结束</param> 13 public void findsudokusolution(sudokugame game, int sp) 14 { 15 // 0、设置递归算法的结束条件 16 if (game.fixedcount >= 95) 17 { 18 game.writeresult(); 19 return; 20 } 21 // 1、判断要查找的位置是否已经被确定 22 // 之前所使用函数,是因为可能存在连续被确定的情况 23 // 所以,下面这个函数也是一个递归函数 24 sp = game.skipfixedcell(sp); 25 if (sp >= 81 || sp < 0) 26 { 27 // 如果已经超出了数组的范围,那么直接返回即可 28 return; 29 } 30 // 2、获取当前位置的cell 31 int row = sp / 9; 32 int col = sp % 9; 33 sudokucell currentcell = new sudokucell(); 34 currentcell = game.cells[row, col]; 35 36 // 3、定义一个新状态,用于保存当前的game的状态 37 sudokugame newgamestate = new sudokugame(); 38 39 // 40 for (int i = 0; i < currentcell.candidatures.count; i++) 41 { 42 newgamestate = deepcopygame(game); //把当前的状态保存一下 43 44 // console.writeline("创建了{0}个局面了",gamecount++); 45 46 int currentcandidature = currentcell.candidatures.elementat(i); 47 if (newgamestate.setcandidaturetofixed(row, col, currentcandidature)) 48 { 49 // 试数成功,没有冲突,进行下一个单元格 50 51 findsudokusolution(newgamestate, sp+1); 52 } 53 } 54 return; 55 } 56 }
4、深拷贝类
1 /// <summary> 2 /// 通过序列化实现game的深复制 3 /// </summary> 4 /// <param name="obj"></param> 5 /// <returns></returns> 6 public static sudokugame deepcopygame(sudokugame obj) 7 { 8 object retval; 9 using (memorystream ms = new memorystream()) 10 { 11 binaryformatter bf = new binaryformatter(); 12 //序列化 13 bf.serialize(ms,obj); 14 ms.seek(0,seekorigin.begin); 15 // 反序列化 16 retval = bf.deserialize(ms); 17 ms.close(); 18 } 19 return (sudokugame)retval; 20 }
5、调用方式
1 sudokugame game = new sudokugame(); 2 solution s = new solution(); 3 s.findsudokusolution(game,0);
6、疑惑与说明
上面,就把所有的代码都完成了,试了几个局面,也能得到正确的结果。但有个问题让我百思不得其解。
在3中,有 if (game.fixedcount >= 95) 此句作为递归的结束条件。可是,这里这个数字不应该是81吗????但是,如果写81,最终输出的盘面中,会有一部分数字没有得到答案,而这个95,也是我通过一次次的摸索,根据最后能得到答案的结果来实现的。这里,因为是递归,所以局面太多,简单的调试根本进行不下去。。。。。。不知道最终的问题何在,后面还需要慢慢的摸索,更希望有哪位能给指点一下迷津,提前谢谢了。
上一篇: Android传感器(sensor)简介
下一篇: 从王思聪抽奖上可以学到什么