一、缘起
之前买了一本《算法的乐趣》，这么多日子里根本没看过。我可能是一个书籍的收藏者而不是读者，因为在办公室里的书架上琳琅满目的摆放了几十本书了，可所读者寥寥无几！言归正传，偶然看了这本书中关于数独的章节，觉得有意思，但书中代码不全，所以自己动手试试，看看能不能按照原作者的思路把这个问题解决了。
二、编码
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、构造函数
- [] data = ,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,, ( i = ; i < ; i++ num = data[i]; cells[i / , i % ] = / , i % ].num = num; (num != / , i % ].isFixed = ++
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 else128 {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、获取当前位置的cell31 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，也是我通过一次次的摸索，根据最后能得到答案的结果来实现的。这里，因为是递归，所以局面太多，简单的调试根本进行不下去。。。。。。不知道最终的问题何在，后面还需要慢慢的摸索，更希望有哪位能给指点一下迷津，提前谢谢了。
经验首页