手把手教你写数独计算器（1）

现在的位置: 首页 > 综合 > 正文

RSS

手把手教你写数独计算器（1）

2013年05月30日 ⁄ 综合 ⁄ 共 6720字 ⁄ 字号小中大 ⁄ 评论关闭

---恢复内容开始---

最近在一个数独网站玩数独游戏，网站地址为：http://www.sudokufans.org.cn/。

由于自己数独能力不是特别强，解题比较慢，但是自己是程序猿，所以，我想，自己写个数独计算器吧，让电脑帮我去算得了。

由于我是C程序猿，所以第一步要做的是，先不管界面，做一个黑底白字的win32控制台应用程序，用于验证自己的算法。

好了，开工，所以做一个简单的儿童4阶数独，如图：

，

我程序是这样使用的，首先，在程序的同目录下放一个input.txt文件用于输入，其中，未知数用0表示，每个数之间一个空格，例如上图的input.txt文件的内容为：

4 0 3 0
3 0 0 0
0 0 0 0
0 0 0 1

然后点击根据我代码生成的程序，就得到输出结果。

。

由于数据比较简单，比较才是4X4的数独，所以也没做什么优化，就是通过数据结构里图论中的DFS从第一个未知数开始，至上而下，从左到右依次枚举每种可能解。

代码如下：

  1 #include <iostream>
  2 #include <fstream>
  3 #include <set>
  4 #include <vector>
  5 using namespace std;
  6 
  7 //#define DEBUG
  8 
  9 vector<vector<int> > Sudo;
 10 
 11 void PrintSudo()
 12 {
 13     for (int i=0; i<4; i++)
 14     {
 15         for (int j=0; j<4; j++)
 16         {
 17             cout << Sudo[i][j] << " ";
 18         }
 19         cout << endl;
 20     }
 21 }
 22 
 23 bool DFS(int X, int Y)
 24 {
 25     if (Y >= 4)
 26     {
 27         return true;
 28     }
 29 
 30     if (X >= 4)
 31     {
 32         return DFS(0, Y + 1);
 33     }
 34 
 35     if (Sudo[Y][X] != 0)
 36     {
 37         return DFS(X + 1, Y);
 38     }
 39 
 40     set<int> HaveExist;
 41     int i, j;
 42 
 43     for (i=0; i<4; i++)
 44     {
 45         if (Sudo[Y][i] != 0)
 46         {
 47             HaveExist.insert(Sudo[Y][i]); //同行中已存在的数
 48         }
 49 
 50         if (Sudo[i][X] != 0)
 51         {
 52             HaveExist.insert(Sudo[i][X]); //同列中已存在的数
 53         }
 54     }
 55 
 56     for (i=Y/2*2; i<Y/2*2 + 2; i++)
 57     {
 58         for (j=X/2*2; j<X/2*2 + 2; j++)
 59         {
 60             if (Sudo[i][j] != 0)
 61             {
 62                 HaveExist.insert(Sudo[i][j]);
 63             }
 64         }
 65     }
 66 
 67 
 68     for (i=1; i<=4; i++)
 69     {
 70         if (HaveExist.find(i) == HaveExist.end()) //数字i在当前数独还未存在,是候选数
 71         {
 72             Sudo[Y][X] = i;
 73 #ifdef DEBUG
 74             cout << "X=" << X << ", Y=" << Y << endl;
 75             cout << "已存在的数:";
 76 
 77             for (set<int>::iterator it=HaveExist.begin(); it!=HaveExist.end(); it++)
 78             {
 79                 cout << *it << " ";
 80             }
 81             cout << endl;
 82             cout << "将Sudo[" << Y << "][" << X << "]设置成" << i << endl;
 83             PrintSudo();
 84 #endif
 85             if (DFS(X+1, Y))
 86             {
 87                 return true;
 88             }
 89         }
 90     }
 91 
 92     Sudo[Y][X] = 0;
 93     return false;
 94 }
 95 
 96 int main()
 97 {
 98     ifstream cin("input.txt");
 99 
100 
101 
102     for (int i=0; i<4; i++)
103     {
104         vector<int> vecTmp;
105         for (int j=0; j<4; j++)
106         {
107             int nTmp;
108 
109             cin >> nTmp;
110             vecTmp.push_back(nTmp);
111         }
112         Sudo.push_back(vecTmp);
113         vecTmp.clear();
114     }
115 
116     if(!DFS(0, 0))
117     {
118         cout << "输入数据有误" << endl;
119     }
120 
121     for (int i=0; i<4; i++)
122     {
123         for (int j=0; j<4; j++)
124         {
125             cout << Sudo[i][j] << " ";
126         }
127         cout << endl;
128     }
129 
130     while (true)
131     {
132 
133     }
134 
135     return 0;
136 }

好了，尝试了4X4的数独之后，再来尝试9X9的数独，首先，我们先简单的将之前的4改成9（当然，同区域的56和58的2改成3）看看情况会怎么样；

看代码

  1 #include <iostream>
  2 #include <fstream>
  3 #include <set>
  4 #include <vector>
  5 using namespace std;
  6 
  7 //#define DEBUG
  8 
  9 vector<vector<int> > Sudo;
 10 
 11 void PrintSudo()
 12 {
 13     for (int i=0; i<9; i++)
 14     {
 15         for (int j=0; j<9; j++)
 16         {
 17             cout << Sudo[i][j] << " ";
 18         }
 19         cout << endl;
 20     }
 21 }
 22 
 23 bool DFS(int X, int Y)
 24 {
 25     if (Y >= 9)
 26     {
 27         return true;
 28     }
 29 
 30     if (X >= 9)
 31     {
 32         return DFS(0, Y + 1);
 33     }
 34 
 35     if (Sudo[Y][X] != 0)
 36     {
 37         return DFS(X + 1, Y);
 38     }
 39 
 40     set<int> HaveExist;
 41     int i, j;
 42 
 43     for (i=0; i<9; i++)
 44     {
 45         if (Sudo[Y][i] != 0)
 46         {
 47             HaveExist.insert(Sudo[Y][i]); //同行中已存在的数
 48         }
 49 
 50         if (Sudo[i][X] != 0)
 51         {
 52             HaveExist.insert(Sudo[i][X]); //同列中已存在的数
 53         }
 54     }
 55 
 56     for (i=Y/3*3; i<Y/3*3 + 3; i++)
 57     {
 58         for (j=X/3*3; j<X/3*3 + 3; j++)
 59         {
 60             if (Sudo[i][j] != 0)
 61             {
 62                 HaveExist.insert(Sudo[i][j]);
 63             }
 64         }
 65     }
 66 
 67 
 68     for (i=1; i<=9; i++)
 69     {
 70         if (HaveExist.find(i) == HaveExist.end()) //数字i在当前数独还未存在,是候选数
 71         {
 72             Sudo[Y][X] = i;
 73 #ifdef DEBUG
 74             cout << "X=" << X << ", Y=" << Y << endl;
 75             cout << "已存在的数:";
 76 
 77             for (set<int>::iterator it=HaveExist.begin(); it!=HaveExist.end(); it++)
 78             {
 79                 cout << *it << " ";
 80             }
 81             cout << endl;
 82             cout << "将Sudo[" << Y << "][" << X << "]设置成" << i << endl;
 83             PrintSudo();
 84 #endif
 85             if (DFS(X+1, Y))
 86             {
 87                 return true;
 88             }
 89         }
 90     }
 91 
 92     Sudo[Y][X] = 0;
 93     return false;
 94 }
 95 
 96 int main()
 97 {
 98     ifstream cin("input.txt");
 99 
100 
101 
102     for (int i=0; i<9; i++)
103     {
104         vector<int> vecTmp;
105         for (int j=0; j<9; j++)
106         {
107             int nTmp;
108 
109             cin >> nTmp;
110             vecTmp.push_back(nTmp);
111         }
112         Sudo.push_back(vecTmp);
113         vecTmp.clear();
114     }
115 
116     if(!DFS(0, 0))
117     {
118         cout << "输入数据有误" << endl;
119     }
120 
121     for (int i=0; i<9; i++)
122     {
123         for (int j=0; j<9; j++)
124         {
125             cout << Sudo[i][j] << " ";
126         }
127         cout << endl;
128     }
129 
130     while (true)
131     {
132 
133     }
134 
135     return 0;
136 }

好，用上面提到的，在input.txt中输入下面的数独，测试一下。

我的能够成功，速度也还接受得了。

好了，下面来点有难度的了。

例如下面的数独：

这个数独，用上面的程序计算的话，那就不是一般的慢了。

所以，必须考虑优化算法。

那么该怎么优化呢？我想先听听大家的看法。

本文待续......

---恢复内容结束---

最近在一个数独网站玩数独游戏，网站地址为：http://www.sudokufans.org.cn/。

由于自己数独能力不是特别强，解题比较慢，但是自己是程序猿，所以，我想，自己写个数独计算器吧，让电脑帮我去算得了。

由于我是C程序猿，所以第一步要做的是，先不管界面，做一个黑底白字的win32控制台应用程序，用于验证自己的算法。

好了，开工，所以做一个简单的儿童4阶数独，如图：

，

4 0 3 0
3 0 0 0
0 0 0 0
0 0 0 1

然后点击根据我代码生成的程序，就得到输出结果。

。

代码如下：

  1 #include <iostream>
  2 #include <fstream>
  3 #include <set>
  4 #include <vector>
  5 using namespace std;
  6 
  7 //#define DEBUG
  8 
  9 vector<vector<int> > Sudo;
 10 
 11 void PrintSudo()
 12 {
 13     for (int i=0; i<4; i++)
 14     {
 15         for (int j=0; j<4; j++)
 16         {
 17             cout << Sudo[i][j] << " ";
 18         }
 19         cout << endl;
 20     }
 21 }
 22 
 23 bool DFS(int X, int Y)
 24 {
 25     if (Y >= 4)
 26     {
 27         return true;
 28     }
 29 
 30     if (X >= 4)
 31     {
 32         return DFS(0, Y + 1);
 33     }
 34 
 35     if (Sudo[Y][X] != 0)
 36     {
 37         return DFS(X + 1, Y);
 38     }
 39 
 40     set<int> HaveExist;
 41     int i, j;
 42 
 43     for (i=0; i<4; i++)
 44     {
 45         if (Sudo[Y][i] != 0)
 46         {
 47             HaveExist.insert(Sudo[Y][i]); //同行中已存在的数
 48         }
 49 
 50         if (Sudo[i][X] != 0)
 51         {
 52             HaveExist.insert(Sudo[i][X]); //同列中已存在的数
 53         }
 54     }
 55 
 56     for (i=Y/2*2; i<Y/2*2 + 2; i++)
 57     {
 58         for (j=X/2*2; j<X/2*2 + 2; j++)
 59         {
 60             if (Sudo[i][j] != 0)
 61             {
 62                 HaveExist.insert(Sudo[i][j]);
 63             }
 64         }
 65     }
 66 
 67 
 68     for (i=1; i<=4; i++)
 69     {
 70         if (HaveExist.find(i) == HaveExist.end()) //数字i在当前数独还未存在,是候选数
 71         {
 72             Sudo[Y][X] = i;
 73 #ifdef DEBUG
 74             cout << "X=" << X << ", Y=" << Y << endl;
 75             cout << "已存在的数:";
 76 
 77             for (set<int>::iterator it=HaveExist.begin(); it!=HaveExist.end(); it++)
 78             {
 79                 cout << *it << " ";
 80             }
 81             cout << endl;
 82             cout << "将Sudo[" << Y << "][" << X << "]设置成" << i << endl;
 83             PrintSudo();
 84 #endif
 85             if (DFS(X+1, Y))
 86             {
 87                 return true;
 88             }
 89         }
 90     }
 91 
 92     Sudo[Y][X] = 0;
 93     return false;
 94 }
 95 
 96 int main()
 97 {
 98     ifstream cin("input.txt");
 99 
100 
101 
102     for (int i=0; i<4; i++)
103     {
104         vector<int> vecTmp;
105         for (int j=0; j<4; j++)
106         {
107             int nTmp;
108 
109             cin >> nTmp;
110             vecTmp.push_back(nTmp);
111         }
112         Sudo.push_back(vecTmp);
113         vecTmp.clear();
114     }
115 
116     if(!DFS(0, 0))
117     {
118         cout << "输入数据有误" << endl;
119     }
120 
121     for (int i=0; i<4; i++)
122     {
123         for (int j=0; j<4; j++)
124         {
125             cout << Sudo[i][j] << " ";
126         }
127         cout << endl;
128     }
129 
130     while (true)
131     {
132 
133     }
134 
135     return 0;
136 }

好了，尝试了4X4的数独之后，再来尝试9X9的数独，首先，我们先简单的将之前的4改成9（当然，同区域的56和58的2改成3）看看情况会怎么样；

看代码

  1 #include <iostream>

  2 #include <fstream>

  3 #include <set>

  4 #include <vector>

  5 using namespace std;

  6

  7 //#define DEBUG

  8

  9 vector<vector<int> > Sudo;

 10

 11 void PrintSudo()

 12 {

 13     for (int i=0; i<9; i++)

 14     {

 15         for (int j=0; j<9; j++)

 16         {

 17             cout << Sudo[i][j] << " ";

 18         }

 19         cout << endl;

 20     }

 21 }

 22

 23 bool DFS(int X, int Y)

 24 {

 25     if (Y >= 9)

 26     {

 27         return true;

 28     }

 29

 30     if (X >= 9)

 31     {

 32         return DFS(0, Y + 1);

 33     }

 34

 35     if (Sudo[Y][X] != 0)

 36     {

 37         return DFS(X + 1, Y);

 38     }

 39

 40     set<int> HaveExist;

 41     int i, j;

 42

 43     for (i=0; i<9; i++)

 44     {

 45         if (Sudo[Y][i] != 0)

 46         {

 47             HaveExist.insert(Sudo[Y][i]); //同行中已存在的数

 48         }

 49

 50         if (Sudo[i][X] != 0)

 51         {

 52             HaveExist.insert(Sudo[i][X]); //同列中已存在的数

 53         }

 54     }

 55

 56     for (i=Y/3*3; i<Y/3*3 + 3; i++)

 57     {

 58         for (j=X/3*3; j<X/3*3 + 3; j++)

 59         {

 60             if (Sudo[i][j] != 0)

 61             {

 62                 HaveExist.insert(Sudo[i][j]);

 63             }

 64         }

 65     }

 66

 67

 68     for (i=1; i<=9; i++)

 69     {

 70         if (HaveExist.find(i) == HaveExist.end()) //数字i在当前数独还未存在,是候选数

 71         {

 72             Sudo[Y][X] = i;

 73 #ifdef DEBUG

 74             cout << "X=" << X << ", Y=" << Y << endl;

 75             cout << "已存在的数:";

 76

 77             for (set<int>::iterator it=HaveExist.begin(); it!=HaveExist.end(); it++)

 78             {

 79                 cout << *it << " ";

 80             }

 81             cout << endl;

【上篇】甲午风云观后感
【下篇】轻松理解Java 多线程

作者: luminaire

该日志由 luminaire 于11年前发表在综合分类下，最后更新于 2013年05月30日.
转载请注明: 手把手教你写数独计算器（1） | 学步园 +复制链接

抱歉!评论已关闭.

返回首页

（其他合作也可洽谈）

必威体育

必威电竞

学步园