C#教程之关于一个最简单的数独解题实现与疑惑一(2)

当前位置:

首页 > Python基础教程 >

C#教程之关于一个最简单的数独解题实现与疑惑一(2)

} 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，也是我通过一次次的摸索，根据最后能得到答案的结果来实现的。这里，因为是递归，所以局面太多，简单的调试根本进行不下去。。。。。。不知道最终的问题何在，后面还需要慢慢的摸索，更希望有哪位能给指点一下迷津，提前谢谢了。

栏目列表