C语言实现解数独 Complete Version

之前用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

/*
 * =====================================================================================
 *
 *       Filename:  sudokou.c
 *
 *    Description:
 *
 *        Version:  1.0
 *        Created:  10/21/2012 02:58:56 PM
 *       Revision:  none
 *       Compiler:  gcc
 *
 *         Author:  [e-mail] (),
 *   Organization:
 *
 * =====================================================================================
 */
#include <stdlib.h>
#include <stdio.h>
#define MMAX 9
char M[MMAX][MMAX] = {{0}};
int count = 0;

int getblockid(int row, int col){
    return row/3 * 3 + col/3;
}
void getnext(int *row, int *col, int* nrow, int* ncol){
    if(*col ==8){
        *ncol = 0;
        *nrow = (*row)+1;
    }
    else{
        *nrow = *row;
        *ncol = (*col) +1;
    }
}
void outputmatrix(char mtr[MMAX][MMAX] ){
    int i, j;
    for(i=0;i<MMAX;i++){
        for(j = 0; j<MMAX;j++){
            printf("%d ", mtr[i][j]);
        }
        printf ( "\n" );
    }
}

void fill(int row, int col, char matrix[MMAX][MMAX], char rowd[][MMAX], char cold[][MMAX], char blod[][MMAX]){
    count ++;
    if(matrix[row][col] != 0){
        if(row == 8 && col == 8){
            outputmatrix(matrix);
            return;
        }
        int nr, nc;
        getnext(&row,&col,&nr,&nc);
        fill(nr,nc,matrix,rowd,cold,blod);
        return;
    }
    int i = 1;
    char mtr[MMAX][MMAX];
    memcpy(mtr, matrix, MMAX*MMAX*sizeof(char));

    for(;i<= 9;i++){
        //duplicate all data
        int blockid = getblockid(row, col);
        if(
            blod[blockid][i-1]!= (char)1 &&
            rowd[row][i-1]!=(char)1   &&
            cold[col][i-1]!=(char)1
            ){
            //fill the cell
//            printf ( "fill [%d] [ %d] with %d\n",row, col, i  );
            matrix[row][col] = i;

            if(row == 8 && col == 8){
                outputmatrix(matrix);
                return;
            }
            //set the restriction
            blod[blockid][i-1] = 1;
            rowd[row][i-1] = 1;
            cold[col][i-1] = 1;
            int nrow,ncol;
            getnext(&row, &col, &nrow, &ncol);
            fill(nrow,ncol,matrix,rowd,cold,blod);
            //restore status
            blod[blockid][i-1] = 0;
            rowd[row][i-1] = 0;
            cold[col][i-1] = 0;
            matrix[row][col] = 0;
        }
    }
}

void trackfixedcell(char fixmtr[MMAX][MMAX], char r[MMAX][MMAX],char c[MMAX][MMAX],char b[MMAX][MMAX]){
    int row,col;
    for(row = 0; row<MMAX; row++){
        for(col= 0; col<MMAX; col++){
            if(fixmtr[row][col]!= 0){
                r[row][(int)fixmtr[row][col]-1] = 1;
                c[col][(int)fixmtr[row][col]-1] = 1;
                b[getblockid(row,col)][(int)fixmtr[row][col]-1] = 1;
            }
        }
    }
}
void readfixed(char mtr[MMAX][MMAX], char* input){
    int i = 0;
    for(;i<MMAX*MMAX;i++){
        int row = i/MMAX;
        int col = i%MMAX;
        if(input[i] != '0'){
            mtr[row][col] = input[i]-48;
        }
    }
}

/*
 * ===  FUNCTION  ======================================================================
 *         Name:  main
 *  Description:
 * =====================================================================================
 */
    int
main ( int argc, char *argv[] )
{
    char * fixed = "600087000000905706040000080030002000004000690000410023500030170080090200001076300";
    char r[MMAX][MMAX] = {{0}};
    char c[MMAX][MMAX] = {{0}};
    char b[MMAX][MMAX] = {{0}};
    readfixed(M,fixed);
    trackfixedcell(M,r,c,b);
    fill(0,0,M,r,c,b);
    printf ( "count = %d\n", count );
    return EXIT_SUCCESS;
}                /* ----------  end of function main  ---------- */