大牛战个痛，这道题要是面试几分钟搞定？

Title :

• 算法，数独问题
• 用概率算法中的拉斯维加斯算法实现数独问题的生成
• 用回溯法实现对数独问题的求解
  

注：数独问题与数度难题的区别是数度难题只有一个解，而数独问题的解有一个或多个。

标准的数独游戏是在一个 9 X 9 的棋盘上填写 1 – 9 这 9 个数字，规则是这样的：

• 棋盘分成上图所示的 9 个区域（不同颜色做背景标出，每个区域是 3 X 3 的子棋盘），在每个子棋盘中填充 1 – 9 且不允许重复 ，下面简称块重复
• 每一行不许有重复值 ，下面简称行重复
• 每一列不许有重复值 ，下面简称列重复
  

如上红色框出的子区域中的亮黄色格子只能填 8。

扩展阅读：http://en.wikipedia.org/wiki/Sudoku

我表示代码写了500行，二十一个函数，三个类，面试出这题是不是直接可以摔门走了。。。

https://gist.github.com/gaoyike/5b99f2ab71e8506a5c98

readman 发表于 2014-7-15 01:00
- = 原来拉斯维加斯不是算法. 是求解方法.

https://gist.github.com/gaoyike/e7dc056a27d132decf79

1. // sudoku.cpp : Defines the entry point for the console application.
   
2. //
   
3. 
   
4. 
   
5. #include <iostream>
   
6. #include <vector>
   
7. using namespace std;
   
8. 
   
9. const int N = 9;
   
10. 
    
11. void valid(const int a[N][N], int x, int y, vector<int>& validList)
    
12. {
    
13.         for(int m=1; m<=N; m++)
    
14.         {
    
15.                 bool flag = true;
    
16.                 for(int j = 0; j<N; j++)
    
17.                 {
    
18.                         if(a[x][j] == m) //每行只能出现一次
    
19.                         {
    
20.                                 flag = false;
    
21.                                 break;
    
22.                         }
    
23.                         if(a[j][y] == m)//每列只能出现一次
    
24.                         {
    
25.                                 flag = false;
    
26.                                 break;
    
27.                         }
    
28.                         int xx,yy;//每3*3格子只能出现一次
    
29.                         xx = (x/3)*3 + j/3;
    
30.                         yy = (y/3)*3 + j%3;
    
31.                         if(a[xx][yy] == m)
    
32.                         {
    
33.                                 flag = false;
    
34.                                 break;
    
35.                         }
    
36.                 }
    
37.                 if(flag) validList.push_back(m);
    
38.         }
    
39. }
    
40. 
    
41. int b[N][N] = {
    
42.                                 8, 0, 0, 0, 0, 0, 0, 0, 0,
    
43.                                 0, 0, 3, 6, 0, 0, 0, 0, 0,
    
44.                                 0, 7, 0, 0, 9, 0, 2, 0, 0,
    
45.                                 0, 5, 0, 0, 0, 7, 0, 0, 0,
    
46.                                 0, 0, 0, 0, 4, 5, 7, 0, 0,
    
47.                                 0, 0, 0, 1, 0, 0, 0, 3, 0,
    
48.                                 0, 0, 1, 0, 0, 0, 0, 6, 8,
    
49.                                 0, 0, 8, 5, 0, 0, 0, 1, 0,
    
50.                                 0, 9, 0, 0, 0, 0, 4, 0, 0
    
51.                         };
    
52. void print(int a[N][N])
    
53. {
    
54.         for(int i=0; i<N; i++)
    
55.         {
    
56.                 for(int j=0; j<N; j++)
    
57.                 {
    
58.                         printf("%d ", a[i][j]);
    
59.                 }
    
60.                 printf("        ");
    
61.                 for(int j=0; j<N; j++)
    
62.                 {
    
63.                         printf("%d ", b[i][j]);
    
64.                 }
    
65.                 printf("\n");
    
66.         }
    
67.         cout<<endl;
    
68. }
    
69. 
    
70. bool success = false;
    
71. 
    
72. bool solve(int a[N][N], int x, int y)
    
73. {
    
74.         while(a[x][y] != 0)
    
75.         {
    
76.                 if(++y==9)
    
77.                 {
    
78.                         y=0;
    
79.                         x++;
    
80.                         if(x==9) //到达右下角，游戏结束
    
81.                                 return true;
    
82.                 }
    
83.         }
    
84.         if(b[x][y] != 0) return false;
    
85.         vector<int> validList;
    
86.         valid(a, x, y, validList); // 将这个格子所有可以填的数字放到list里
    
87.         if(validList.size() == 0) return false;
    
88.         //遍历这个list，每个数填进去试一试
    
89.         for(int i=0; i<validList.size(); i++)
    
90.         {
    
91.                 a[x][y]=validList[i];
    
92.                 bool f=solve(a, x,y);//递归试算
    
93.                 if(f) return true;
    
94.                 a[x][y]=0;
    
95.         }
    
96.         return false;
    
97. }
    
98. 
    
99. 
    
100. 
     
101. int main()
     
102. {
     
103.         int a[N][N] = {
     
104.                                         8, 0, 0, 0, 0, 0, 0, 0, 0,
     
105.                                         0, 0, 3, 6, 0, 0, 0, 0, 0,
     
106.                                         0, 7, 0, 0, 9, 0, 2, 0, 0,
     
107.                                         0, 5, 0, 0, 0, 7, 0, 0, 0,
     
108.                                         0, 0, 0, 0, 4, 5, 7, 0, 0,
     
109.                                         0, 0, 0, 1, 0, 0, 0, 3, 0,
     
110.                                         0, 0, 1, 0, 0, 0, 0, 6, 8,
     
111.                                         0, 0, 8, 5, 0, 0, 0, 1, 0,
     
112.                                         0, 9, 0, 0, 0, 0, 4, 0, 0
     
113.                                 };
     
114. 
     
115.         solve(a,0,0);
     
116.         print(a);
     
117.         return 0;
     
118. }
     
119. 
     

复制代码

readman 发表于 2014-7-15 01:00
- = 原来拉斯维加斯不是算法. 是求解方法.

https://gist.github.com/gaoyike/e7dc056a27d132decf79

这段是CPP的解法用的回溯，不过我没搞清楚，a[0][0]=b[0][0]=8,运行到84行应该直接返回false了啊，怎么还能接着运行下去

用dfs
too ez

DFS在数据量巨大的时候会挂....
看见sudoku的第一反应应该是写Dancing Links = =

tobyljj 发表于 2014-7-12 01:11
DFS在数据量巨大的时候会挂....
看见sudoku的第一反应应该是写Dancing Links = =

这个的数据量还好吧……一般要到象棋里的DFS那么大才会挂，所以只能DFS到一定程度

用概率算法中的拉斯维加斯算法实现数独问题的生成

这个是什么算法呀，这个真心第一次听说……

donnice 发表于 2014-7-12 05:07
这个的数据量还好吧……一般要到象棋里的DFS那么大才会挂，所以只能DFS到一定程度

单就样例的数据量而言肯定是DFS秒过>_<
再大一点小心爆栈。。处理一下也没问题 = =

但是数据再大一点就挂了。。

用走迷宫类似的思路，回溯法，可以做迭代版的深搜。

可以用三个boolean数组或者set来辅助做标记，减少冗余操作。但是平均running time无法改善, 总是O(n^3)。

leetcode上貌似有一个解数独的题，那个可以用dfs过，不过生成数独那是个啥东西，第一次听说

readman 发表于 2014-7-11 19:15
用dfs
too ez

求解没什么......关键是随机生成数独