Chinaunix首页 | 论坛 | 博客
  • 博客访问: 1006630
  • 博文数量: 150
  • 博客积分: 3017
  • 博客等级: 少校
  • 技术积分: 3829
  • 用 户 组: 普通用户
  • 注册时间: 2011-11-19 14:40
个人简介

Now in Baidu WISE team

文章分类

全部博文(150)

文章存档

2014年(8)

2013年(31)

2012年(111)

分类: C/C++

2012-10-21 17:30:33

之前用perl做过一遍数独,但是脑子不是很清楚。今天又用c清清楚楚的写了一遍。很有成就感。
到现在为止,数读问题彻底Mission complete~
在不考虑给定数据的情况下,大概核心算法用了1个小时多一点.连想带写还是比较慢。希望面试被面到的话的能够顺利解决。
2012.10.22 update: 感谢网友@momser的指正,更正保存现场的多余代码和拼写错误。 另外修正了一处漏掉的return,是循环次数由52153次减少到了24943次。


原理如下。
我们先假设填入的数字为0~8共9个数字。
将整个图分成9个3*3的方块,从左到右,从上到下,依次编号0~8
----------------------------------------------------------------------------------------------
填每个格子的时候,我们可以选择.0~8
对于选择的数字,有3种限制,我们通过这三种限制来对回溯过程进行剪枝。
1.行不重复  r[9][9]
2.列不重复  c[9][9]
3.块不重复  b[9][9]
对使用3个9×9的数组来描述这三种限制。
对于行 n 来说,所有之前填过的数字nums,都有r[n][nums] = 1
同理,对与列和块来说,之前每个填过的数字都相应标记为1.
----------------------------------------------------------------------------------------------
当尝试向一个格子[row][col] (块序号为bi)填充数据i  (0<=i<=8 ,的时候,
如果对应r[row][i] =1 或 c[col][i] = 1 或 b[bi][i] =1,说明无法满足条件,是非法的。
这时再尝试i = i+1.
----------------------------------------------------------------------------------------------
当向坐标为[row][col] 填入一个满足条件的数字i的时候,我们更新限制数组如下
  r[row][i] = 1;
  c[col][i] = 1;
  b[bi][i] = 1;
----------------------------------------------------------------------------------------------
然后坐标移到下一个,这里选用的顺序是右移动。
---------------------------------------------------------------------------------------------
对于一个格子CX的后续CY,如果我们遍历0~9完成,那么返回。
尝试CX的其他可能性。
----------------------------------------------------------------------------------------------
当填入的格子是 [8][8]时,整个问题处理完毕


对于给定的输入,
直接将初始状态的矩阵设置成相应的值,同时,根据给定的值,设置初始的r, c, b的限制条件。
当读到的格子内已经有给定值的时候,无需做其他尝试,直接进入处理下一个格子。

实际填入的是1~9,所以要对0~8做一点转换。

对于每次尝试完一个可能填入的数后,需要恢复现场,包括将该格子内的数重置为初始值0.同时,相应的限制条件r,c,b都应把刚才填入的值的位置0.


代码和测试数据如下:
GCC编译执行通过测试。
600087000000905706040000080030002000004000690000410023500030170080090200001076300



点击(此处)折叠或打开

  1. /*
  2.  * =====================================================================================
  3.  *
  4.  * Filename: sudokou.c
  5.  *
  6.  * Description:
  7.  *
  8.  * Version: 1.0
  9.  * Created: 10/21/2012 02:58:56 PM
  10.  * Revision: none
  11.  * Compiler: gcc
  12.  *
  13.  * Author: royn.wang.renyuan@gmail.com (),
  14.  * Organization:
  15.  *
  16.  * =====================================================================================
  17.  */
  18. #include <stdlib.h>
  19. #include <stdio.h>
  20. #define MMAX 9
  21. char M[MMAX][MMAX] = {{0}};
  22. int count = 0;

  23. int getblockid(int row, int col){
  24.     return row/3 * 3 + col/3;
  25. }
  26. void getnext(int *row, int *col, int* nrow, int* ncol){
  27.     if(*col ==8){
  28.         *ncol = 0;
  29.         *nrow = (*row)+1;
  30.     }
  31.     else{
  32.         *nrow = *row;
  33.         *ncol = (*col) +1;
  34.     }
  35. }
  36. void outputmatrix(char mtr[MMAX][MMAX] ){
  37.     int i, j;
  38.     for(i=0;i<MMAX;i++){
  39.         for(j = 0; j<MMAX;j++){
  40.             printf("%d ", mtr[i][j]);
  41.         }
  42.         printf ( "\n" );
  43.     }
  44. }

  45. void fill(int row, int col, char matrix[MMAX][MMAX], char rowd[][MMAX], char cold[][MMAX], char blod[][MMAX]){
  46.     count ++;
  47.     if(matrix[row][col] != 0){
  48.         if(row == 8 && col == 8){
  49.             outputmatrix(matrix);
  50.             return;
  51.         }
  52.         int nr, nc;
  53.         getnext(&row,&col,&nr,&nc);
  54.         fill(nr,nc,matrix,rowd,cold,blod);
  55.         return;
  56.     }
  57.     int i = 1;
  58.     char mtr[MMAX][MMAX];
  59.     memcpy(mtr, matrix, MMAX*MMAX*sizeof(char));

  60.     for(;i<= 9;i++){
  61.         //duplicate all data
  62.         int blockid = getblockid(row, col);
  63.         if(
  64.             blod[blockid][i-1]!= (char)1 &&
  65.             rowd[row][i-1]!=(char)1 &&
  66.             cold[col][i-1]!=(char)1
  67.             ){
  68.             //fill the cell
  69. //            printf ( "fill [%d] [ %d] with %d\n",row, col, i );
  70.             matrix[row][col] = i;

  71.             if(row == 8 && col == 8){
  72.                 outputmatrix(matrix);
  73.                 return;
  74.             }
  75.             //set the restriction
  76.             blod[blockid][i-1] = 1;
  77.             rowd[row][i-1] = 1;
  78.             cold[col][i-1] = 1;
  79.             int nrow,ncol;
  80.             getnext(&row, &col, &nrow, &ncol);
  81.             fill(nrow,ncol,matrix,rowd,cold,blod);
  82.             //restore status
  83.             blod[blockid][i-1] = 0;
  84.             rowd[row][i-1] = 0;
  85.             cold[col][i-1] = 0;
  86.             matrix[row][col] = 0;
  87.         }
  88.     }
  89. }

  90. void trackfixedcell(char fixmtr[MMAX][MMAX], char r[MMAX][MMAX],char c[MMAX][MMAX],char b[MMAX][MMAX]){
  91.     int row,col;
  92.     for(row = 0; row<MMAX; row++){
  93.         for(col= 0; col<MMAX; col++){
  94.             if(fixmtr[row][col]!= 0){
  95.                 r[row][(int)fixmtr[row][col]-1] = 1;
  96.                 c[col][(int)fixmtr[row][col]-1] = 1;
  97.                 b[getblockid(row,col)][(int)fixmtr[row][col]-1] = 1;
  98.             }
  99.         }
  100.     }
  101. }
  102. void readfixed(char mtr[MMAX][MMAX], char* input){
  103.     int i = 0;
  104.     for(;i<MMAX*MMAX;i++){
  105.         int row = i/MMAX;
  106.         int col = i%MMAX;
  107.         if(input[i] != '0'){
  108.             mtr[row][col] = input[i]-48;
  109.         }
  110.     }
  111. }

  112. /*
  113.  * === FUNCTION ======================================================================
  114.  * Name: main
  115.  * Description:
  116.  * =====================================================================================
  117.  */
  118.     int
  119. main ( int argc, char *argv[] )
  120. {
  121.     char * fixed = "600087000000905706040000080030002000004000690000410023500030170080090200001076300";
  122.     char r[MMAX][MMAX] = {{0}};
  123.     char c[MMAX][MMAX] = {{0}};
  124.     char b[MMAX][MMAX] = {{0}};
  125.     readfixed(M,fixed);
  126.     trackfixedcell(M,r,c,b);
  127.     fill(0,0,M,r,c,b);
  128.     printf ( "count = %d\n", count );
  129.     return EXIT_SUCCESS;
  130. }                /* ---------- end of function main ---------- */

阅读(11098) | 评论(3) | 转发(4) |
给主人留下些什么吧!~~

momser2012-10-23 10:48:43

runningdark: line58-65 当时写的头比较大,我最开始也没copy来着,但是没跑过,我还很奇怪,只是为了保险复制了份,直接就过了,也没在意。
line72-79 确实是。。我今天还在.....
共同学习,我是菜鸟,提出一点看法,还望多多指教^_^

runningdark2012-10-22 22:20:07

momser: 这个程序挺好玩的哈,学习了,不过提一点意见希望不要见怪
line37多了个;
line58-65似乎没有必要复制一遍四个矩阵的数值
line72-79也可以不用拷贝,每次拷贝都要.....
line58-65 当时写的头比较大,我最开始也没copy来着,但是没跑过,我还很奇怪,只是为了保险复制了份,直接就过了,也没在意。
line72-79 确实是。。我今天还在想说这部分浪费空间,想怎么恢复现场,还想用栈之类的。。没想到直接最后加一句就行了。
确实是matrix..纠正了我一直以来的错误。。
灰常感谢。 我再改改。

momser2012-10-22 20:23:40

这个程序挺好玩的哈,学习了,不过提一点意见希望不要见怪
line37多了个;
line58-65似乎没有必要复制一遍四个矩阵的数值
line72-79也可以不用拷贝,每次拷贝都要分配内存,只要在if语句的最后加上清零就可以了
还有matrix是矩阵metrix好像是拼写有错误?
我修改了一份程序也可以编译通过,去掉了line58-65和line72-79