关于一个最简单的数独解题实现与疑惑一

一、缘起

　　之前买了一本《算法的乐趣》，这么多日子里根本没看过。我可能是一个书籍的收藏者而不是读者，因为在办公室里的书架上琳琅满目的摆放了几十本书了，可所读者寥寥无几！言归正传，偶然看了这本书中关于数独的章节，觉得有意思，但书中代码不全，所以自己动手试试，看看能不能按照原作者的思路把这个问题解决了。

 二、编码

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