欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

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

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

一、缘起

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

 二、编码

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