一亩三分地论坛

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

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

[算法题] 回溯法求解数独的一个CPP程序

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

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

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

x
  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. }

复制代码
我没搞清楚,a[0][0]=b[0][0]=8,运行到84行应该直接返回false了啊,怎么还能接着运行下去?
 楼主| TonyJang 发表于 2014-7-15 17:06:23 | 显示全部楼层
这个false返回到116行吗?那有什么意义?。。。
回复 支持 反对

使用道具 举报

 楼主| TonyJang 发表于 2014-7-15 17:38:50 | 显示全部楼层
我操尼玛,++y,太隐蔽了,这作者逼格太高......小弟弄懂了,大牛不用回复了
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-4 02:06

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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