一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 1251|回复: 17
收起左侧

[算法题] 大牛战个痛,这道题要是面试几分钟搞定?

[复制链接] |试试Instant~ |关注本帖
TonyJang 发表于 2014-7-11 16:21:11 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x

Title :

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

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


6597142334424340433.jpg


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

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

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

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



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


readman 发表于 2014-7-11 19:37:20 | 显示全部楼层
回复 支持 1 反对 0

使用道具 举报

readman 发表于 2014-7-11 19:15:34 | 显示全部楼层
用dfs
too ez
回复 支持 反对

使用道具 举报

tobyljj 发表于 2014-7-12 01:11:57 | 显示全部楼层
DFS在数据量巨大的时候会挂....
看见sudoku的第一反应应该是写Dancing Links = =
回复 支持 反对

使用道具 举报

donnice 发表于 2014-7-12 05:07:27 | 显示全部楼层
tobyljj 发表于 2014-7-12 01:11
DFS在数据量巨大的时候会挂....
看见sudoku的第一反应应该是写Dancing Links = =

这个的数据量还好吧……一般要到象棋里的DFS那么大才会挂,所以只能DFS到一定程度
回复 支持 反对

使用道具 举报

浅浅 发表于 2014-7-12 06:07:10 | 显示全部楼层
用概率算法中的拉斯维加斯算法实现数独问题的生成

这个是什么算法呀,这个真心第一次听说……
回复 支持 反对

使用道具 举报

tobyljj 发表于 2014-7-12 06:41:18 | 显示全部楼层
donnice 发表于 2014-7-12 05:07
这个的数据量还好吧……一般要到象棋里的DFS那么大才会挂,所以只能DFS到一定程度

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

但是数据再大一点就挂了。。
回复 支持 反对

使用道具 举报

花农 发表于 2014-7-12 09:53:59 | 显示全部楼层
用走迷宫类似的思路,回溯法,可以做迭代版的深搜。

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

使用道具 举报

pyemma 发表于 2014-7-12 11:20:49 | 显示全部楼层
leetcode上貌似有一个解数独的题,那个可以用dfs过,不过生成数独那是个啥东西,第一次听说
回复 支持 反对

使用道具 举报

 楼主| TonyJang 发表于 2014-7-14 22:35:33 | 显示全部楼层

求解没什么......关键是随机生成数独
回复 支持 反对

使用道具 举报

readman 发表于 2014-7-14 23:06:03 | 显示全部楼层
TonyJang 发表于 2014-7-14 22:35
求解没什么......关键是随机生成数独

- = 简单网站的数独生成是挖空生成的.. 我不知道拉斯维加斯算法
回复 支持 反对

使用道具 举报

readman 发表于 2014-7-15 00:54:17 | 显示全部楼层
TonyJang 发表于 2014-7-14 22:35
求解没什么......关键是随机生成数独

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

- = 我稍微改了一下.
不过不是所有的sudoku都可以被solve.
当然,如果不怕复杂, 可以test是不是能被solve, 然后再挖数...
回复 支持 反对

使用道具 举报

readman 发表于 2014-7-15 01:00:02 | 显示全部楼层
TonyJang 发表于 2014-7-14 22:35
求解没什么......关键是随机生成数独

- = 原来拉斯维加斯不是算法. 是求解方法.

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

这个是肯定能生成的
empty是有几个空格.
hardness是打乱难度
回复 支持 反对

使用道具 举报

wizard19900509 发表于 2014-7-15 01:33:29 | 显示全部楼层
没听过拉斯维加斯算法。。。
只是生成数独的话 如果没有特别要求 有种偷懒的方法 先随便生成个3*3的数字矩阵 然后通过行列变换就能生成剩下8个3*3数字矩阵了
回复 支持 反对

使用道具 举报

 楼主| TonyJang 发表于 2014-7-15 17:00:43 | 显示全部楼层
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. #include <iostream>
  4. #include <vector>
  5. using namespace std;

  6. const int N = 9;

  7. void valid(const int a[N][N], int x, int y, vector<int>& validList)
  8. {
  9.         for(int m=1; m<=N; m++)
  10.         {
  11.                 bool flag = true;
  12.                 for(int j = 0; j<N; j++)
  13.                 {
  14.                         if(a[x][j] == m) //每行只能出现一次
  15.                         {
  16.                                 flag = false;
  17.                                 break;
  18.                         }
  19.                         if(a[j][y] == m)//每列只能出现一次
  20.                         {
  21.                                 flag = false;
  22.                                 break;
  23.                         }
  24.                         int xx,yy;//每3*3格子只能出现一次
  25.                         xx = (x/3)*3 + j/3;
  26.                         yy = (y/3)*3 + j%3;
  27.                         if(a[xx][yy] == m)
  28.                         {
  29.                                 flag = false;
  30.                                 break;
  31.                         }
  32.                 }
  33.                 if(flag) validList.push_back(m);
  34.         }
  35. }

  36. int b[N][N] = {
  37.                                 8, 0, 0, 0, 0, 0, 0, 0, 0,
  38.                                 0, 0, 3, 6, 0, 0, 0, 0, 0,
  39.                                 0, 7, 0, 0, 9, 0, 2, 0, 0,
  40.                                 0, 5, 0, 0, 0, 7, 0, 0, 0,
  41.                                 0, 0, 0, 0, 4, 5, 7, 0, 0,
  42.                                 0, 0, 0, 1, 0, 0, 0, 3, 0,
  43.                                 0, 0, 1, 0, 0, 0, 0, 6, 8,
  44.                                 0, 0, 8, 5, 0, 0, 0, 1, 0,
  45.                                 0, 9, 0, 0, 0, 0, 4, 0, 0
  46.                         };
  47. void print(int a[N][N])
  48. {
  49.         for(int i=0; i<N; i++)
  50.         {
  51.                 for(int j=0; j<N; j++)
  52.                 {
  53.                         printf("%d ", a[i][j]);
  54.                 }
  55.                 printf("        ");
  56.                 for(int j=0; j<N; j++)
  57.                 {
  58.                         printf("%d ", b[i][j]);
  59.                 }
  60.                 printf("\n");
  61.         }
  62.         cout<<endl;
  63. }

  64. bool success = false;

  65. bool solve(int a[N][N], int x, int y)
  66. {
  67.         while(a[x][y] != 0)
  68.         {
  69.                 if(++y==9)
  70.                 {
  71.                         y=0;
  72.                         x++;
  73.                         if(x==9) //到达右下角,游戏结束
  74.                                 return true;
  75.                 }
  76.         }
  77.         if(b[x][y] != 0) return false;
  78.         vector<int> validList;
  79.         valid(a, x, y, validList); // 将这个格子所有可以填的数字放到list里
  80.         if(validList.size() == 0) return false;
  81.         //遍历这个list,每个数填进去试一试
  82.         for(int i=0; i<validList.size(); i++)
  83.         {
  84.                 a[x][y]=validList[i];
  85.                 bool f=solve(a, x,y);//递归试算
  86.                 if(f) return true;
  87.                 a[x][y]=0;
  88.         }
  89.         return false;
  90. }



  91. int main()
  92. {
  93.         int a[N][N] = {
  94.                                         8, 0, 0, 0, 0, 0, 0, 0, 0,
  95.                                         0, 0, 3, 6, 0, 0, 0, 0, 0,
  96.                                         0, 7, 0, 0, 9, 0, 2, 0, 0,
  97.                                         0, 5, 0, 0, 0, 7, 0, 0, 0,
  98.                                         0, 0, 0, 0, 4, 5, 7, 0, 0,
  99.                                         0, 0, 0, 1, 0, 0, 0, 3, 0,
  100.                                         0, 0, 1, 0, 0, 0, 0, 6, 8,
  101.                                         0, 0, 8, 5, 0, 0, 0, 1, 0,
  102.                                         0, 9, 0, 0, 0, 0, 4, 0, 0
  103.                                 };

  104.         solve(a,0,0);
  105.         print(a);
  106.         return 0;
  107. }

复制代码
回复 支持 反对

使用道具 举报

 楼主| TonyJang 发表于 2014-7-15 17:03:33 | 显示全部楼层
readman 发表于 2014-7-15 01:00
- = 原来拉斯维加斯不是算法. 是求解方法.

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

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

使用道具 举报

readman 发表于 2014-7-15 17:52:53 | 显示全部楼层
TonyJang 发表于 2014-7-15 17:03
这段是CPP的解法用的回溯,不过我没搞清楚,a[0][0]=b[0][0]=8,运行到84行应该直接返回false了啊,怎么还 ...

抱歉..我看不懂cpp...
回复 支持 反对

使用道具 举报

miss_snow 发表于 2014-10-10 23:10:54 | 显示全部楼层
tobyljj 发表于 2014-7-12 01:11
DFS在数据量巨大的时候会挂....
看见sudoku的第一反应应该是写Dancing Links = =

dancing links是王道
但是如果面试的话就一个dfs足以
面试的时候敲一版dancing links可行吗?木有面试过……
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-9 10:02

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表