首页 关于

数独(Sudoku) 的求解

前几天坐在公交车上无聊，刷朋友圈看到有人晒了两道数独的题目，便好奇拿出笔做了起来，当时的题目很简单，做完之后成就感爆棚，感觉天下无不可解之数独，于是拿起手机下载数独App，直奔专家级。熟料这一题一做就是一个多小时，而且中间有一步还是靠蒙的，才勉强做出了这一题。后来又来了一题专家级，勉力强撑一个多小时以后放弃了。

这类困难的数独不能单靠简单的推导完成，需要层层排除，回来写了一个数独的求解程序。

160
1
using System;
2
using System.Text;
3
using System.Text.RegularExpressions;
4
​
5
namespace Sudoku
6
{
7
    class Sudoku
8
    {
9
        private readonly int[,] sudokuMatrix;
10
​
11
        public Sudoku(string input)
12
        {
13
            //初始化9x9数字
14
            sudokuMatrix = new int[9, 9];
15
            //检查是否输入是81为数字字符串
16
            if (!String.IsNullOrEmpty(input) && Regex.IsMatch(input,"[0-9]{81}"))
17
            {
18
                for (int i = 0; i < 9; i++)
19
                {
20
                    for (int j = 0; j < 9; j++)
21
                    {
22
                        sudokuMatrix[i, j] = Convert.ToInt32(input[i * 9 + j].ToString());
23
                    }
24
                }
25
            }
26
            else
27
            {
28
                //...异常
29
            }
30
        }
31
​
32
        /// <summary>
33
        /// 求解数独
34
        /// </summary>
35
        public void Solve()
36
        {
37
            int[,] emptyLocation = new int[64, 2];  //用于存储空单元格的行列，数独最大只有64个空单元格
38
            int cursor = -1;  //游标，指示当前所在的空单元格
39
​
40
            //遍历数独，寻找空单元格，若找到空单元格，检查该单元格是否有唯一值，如果有则填上唯一值，否则将空格行列记录下来
41
            for (int i = 0; i < 9; i++)
42
            {
43
                for (int j = 0; j < 9; j++)
44
                {
45
                    if (sudokuMatrix[i,j]==0) //是否为空单元格
46
                    {
47
                        if (FillExclusiveNumble(i,j))  //是否有唯一值，如果有，则填入唯一值，并再次从头开始搜索
48
                        {
49
                            i = 0;
50
                            j = 0;
51
                            cursor = -1;
52
                        }
53
                        else  //如果没有唯一值，则将空格行列号记录下来
54
                        {
55
                            cursor += 1;
56
                            emptyLocation[cursor, 0] = i;
57
                            emptyLocation[cursor, 1] = j;
58
                        }
59
                    }
60
                }
61
            }
62
​
63
            //开始逐个空格依次尝试1-9的数字，知道所有空格都填满为止
64
            while (cursor>=0) //当剩余空格数大于0时
65
            {
66
                if (TryNext(emptyLocation[cursor,0],emptyLocation[cursor,1]))  //尝试将当前空格内的数字加1
67
                {
68
                    cursor -= 1; //前往下一个空格
69
                }
70
                else //如果该空格内无法填入任意数字，则表明前面的空格所填数字有误，返回上一个空格
71
                {
72
                    cursor += 1;
73
                }
74
            }
75
        }
76
​
77
        /// <summary>
78
        /// 尝试在当前空格内填入更大的数字
79
        /// </summary>
80
        /// <param name="row">行</param>
81
        /// <param name="col">列</param>
82
        /// <returns></returns>
83
        private bool TryNext(int row,int col)
84
        {
85
            for (int i = sudokuMatrix[row,col]+1; i <=9; i++)
86
            {
87
                if (Check(row, col, i))
88
                {
89
                    sudokuMatrix[row, col] = i; //如果能在当前空格内填入更大的数字，则填入该数字
90
                    return true;
91
                }
92
            }
93
            sudokuMatrix[row, col] = 0;  //否则将该空格内的数字改为0
94
            return false;
95
        }
96
​
97
        /// <summary>
98
        /// 根据数独规则，判断特定单元格内能否填入某数字
99
        /// </summary>
100
        /// <param name="row">行</param>
101
        /// <param name="col">列</param>
102
        /// <param name="num">尝试填入的数字</param>
103
        /// <returns></returns>
104
        private bool Check(int row,int col,int num)
105
        {
106
            for (int index = 0; index < 9; index++)
107
            {
108
                if (sudokuMatrix[row, index] == num) return false;
109
                if (sudokuMatrix[index, col] == num) return false;
110
                if (sudokuMatrix[row / 3 * 3 + index / 3, col / 3 * 3 + index % 3] == num) return false;
111
            }
112
            return true;
113
        }
114
​
115
        /// <summary>
116
        /// 数独转换成字符串
117
        /// </summary>
118
        /// <returns></returns>
119
        public override string ToString()
120
        {
121
            StringBuilder sb = new StringBuilder();
122
            for (int i = 0; i < 9; i++)
123
            {
124
                for (int j = 0; j < 9; j++)
125
                {
126
                    sb.Append(sudokuMatrix[i, j]); 
127
                }
128
                sb.Append("\n");
129
            }
130
            return sb.ToString();
131
        }
132
​
133
        /// <summary>
134
        /// 判断空格是否有唯一值，如有则填入该唯一值
135
        /// </summary>
136
        /// <param name="row">行</param>
137
        /// <param name="col">列</param>
138
        /// <returns></returns>
139
        private bool FillExclusiveNumble(int row,int col)
140
        {
141
            int count = 0;
142
            int ExclusivleNumble = 0;
143
            for (int num = 1; num <= 9; num++)
144
            {
145
                if (Check(row,col,num))
146
                {
147
                    count += 1;
148
                    ExclusivleNumble = num;
149
                }
150
            }
151
            if (count == 1)
152
            {
153
                sudokuMatrix[row, col] = ExclusivleNumble;
154
                return true;
155
            }
156
            else return false;
157
        }
158
    }
159
}
160
​