解题思路

拿到题目后，心里一凉，怎么还没开学就整这么难的题。。。然后去网上百度、论坛找各种资料，发现还蛮有意思。看了几种解法，发现回溯法好像和大二学的数据结构里的方法有些类似，有点印象。然后看了题目，直觉告诉我用回溯法应该能解。回溯法的基本思想是：从问题的某一种状态（初始状态）出发，搜索从这种状态出发所能达到的所有“状态”，当一条路走到“尽头”的时候（不能再前进），再后退一步或若干步，从另一种可能“状态”出发，继续搜索，直到所有的“路径”（状态）都试探过。这种不断“前进”、不断“回溯”寻找解的方法，就称作“回溯法”。数独这题可以用回溯法。

设计实现

用回溯法实现的流程图如下：

代码说明

1.判断可以放哪些数字

void ConfirmCandidate( int (*a)[9], int i, int j )  
{  
    for( int i_candidate = 0; i_candidate < 9; i_candidate++ )  
        candidate[i_candidate] = i_candidate+1;  
    for( int colm = 0; colm < 9; colm++ )  
    {  
        if( a[i][colm] != 0 )  
            candidate[a[i][colm]-1] = 0;  
    }  
    for( int line = 0; line < 9; line++ )  
    {  
        if( a[line][j] != 0 )  
            candidate[a[line][j]-1] = 0;  
    }  
    for( int line = i/3*3; line < i/3*3+3; line++ )  
    {  
        for( int colm = j/3*3; colm < j/3*3+3; colm++ )  
            if( a[line][colm] != 0 )  
                candidate[a[line][colm]-1] = 0;  
    }  
}

2.标记每个空格位置

void TotalNumbers( int (*a)[9], int i, int j )  
{  
    for( int line = 0; line < i; line++ )  
    {  
        for( int colm = 0; colm < j; colm++ )  
            if( a[line][colm] == 0 )  
            {  
                g_a[line][colm] = 1;  
            }  
    }  
}

3.判断所填数字是否正确

bool JudgeValue( int (*a)[9],int i, int j )  
{  
    for( int colm = 0; colm < 9; colm++ )  
    {  
        if( a[i][colm] == a[i][j] && j != colm )  
            return false;  
    }  
    for( int line = i/3*3; line < i/3*3+3; line++ )  
    {  
        for( int colm = j/3*3; colm < j/3*3+3; colm++ )  
            if( a[line][colm] == a[i][j] && i != line && j != colm )  
                return false;  
    }  
    return true;  
}

4.判断是否成功

bool success( int(*a)[9], int i, int j )  
{  
    if( i < 0 || j < 0 ) return false;  
    int line = i;  
    int colm = j;  
    for( ; line < 9; line++, colm = 0 )  
    {  
        for( ; colm < 9; colm++ )  
        {  
            if( a[line][colm] != 0 && g_a[line][colm] == 0 ) continue;  
            ConfirmCandidate(a, line, colm);  
            for(int c = 0; c < 9; c++ )  
            {  
                if( candidate[c] > a[line][colm] )  
                {  
                    a[line][colm] = candidate[c];  
                
                    for(int i = 0; i < 9; i++ ) 
                        cout << candidate[i] << " "; 
                    cout << endl << endl; 
                    */  
                    //print(a);  
                    bool bRet = JudgeValue( a, line, colm );  
                    if(!bRet)   
                    {  
                        //cout << "bRet  is  false" << endl;  
                    }  
                    else{  
             
                        break;  
                    }  
                }  
                else if( c == 8 && candidate[c] <= a[line][colm] )  
                {  
                    int set_colm = 8;  
                    a[line][colm] = 0;  
                    if( colm == 0 )  
                    {  
                        while( g_a[line-1][set_colm] == 0)  
                        {  
                            if( set_colm == 0)   
                            {  
                                line--;  
                                set_colm = 8;  
                            }  
                            else set_colm--;  
                        }  
                        return success( a, line - 1, set_colm);  
                    }  
                    else{  
                        while( g_a[line][colm-1] == 0)  
                        {  
                            if( colm-1 == 0)   
                            {  
                                line--;  
                                colm = 9;  
                            }  
                            else colm--;  
                        }  
                        return success( a ,line, colm-1 );  
                    }  
                }  
            }  
        }  
    }  
    return true;  
}

测试运行

性能分析与改进

单元测试还没完成，正在探索中。。。因为开学这几天比较忙，没时间，附加题也来不及做。另外，程序中有bug，有时输出的结果会出现重复的数独棋盘，这几天会不断完善。

PSP表格

PSP2.1	Personal Software Process Stages	预估耗时（分钟）	实际耗时（分钟）
Planning	计划	30	40
· Estimate	· 估计这个任务需要多少时间	35	50
Development	开发	20	20
· Analysis	· 需求分析 (包括学习新技术)	25	30
· Design Spec	· 生成设计文档	50	40
· Design Review	· 设计复审 (和同事审核设计文档)	30	40
· Coding Standard	· 代码规范 (为目前的开发制定合适的规范)	30	35
· Design	· 具体设计	20	30
· Coding	· 具体编码	60	120
· Code Review	· 代码复审	50	30
· Test	· 测试（自我测试，修改代码，提交修改）	90	150
Reporting	报告	30	45
· Test Report	· 测试报告	35	40
· Size Measurement	· 计算工作量	20	25
· Postmortem & Process Improvement Plan	· 事后总结, 并提出过程改进计划	20	25
合计		525	750

因为时间确实很紧，也没有尽全力在做，不过这两天会不断完善。O(∩_∩)O