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

当前位置:

首页 > Python基础教程 >

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

一、缘起

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

二、编码

　　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

栏目列表