Make it Possible

软工大作业数独

一个简单的数独

需求简介

生成n个数独终局,解决若干个有单独解的数独。
项目地址

算法简述

数独生成

要求我们生成至多1,000,000个数独终局,直接暴力生成数独显现性能很低,所以我们需要其他的方法。
我们注意到一个数独终局做一些转化可以生成另一个数独终局
1. 交换两行
可以交换在同一个“块”中的两行,例如交换123, 456,789这三组中一组的两行
2. 交换两列
可以交换在同一个“块”中的两列,例如交换123, 456,789这三组中一组的两列
3. 大型块交换
按3*3把矩阵进行分块,从左上到右下进行编号,交换13块,46块,79块
4. 矩阵翻转
对矩阵进行90度旋转,180度旋转,镜像对称
5. 数字交换
把数字a全部变成b,把数字b全部变成a

我们可以只用1,2两种交换模式。
先随机出两个在同一块中的行,交换这两行,重复20次;再随机选出在两个块中的列,交换两列,重复20次。
为保证左上角的数是一个确定的数,我们在做这样一步操作:
如果左上角的数就是想要的数,就直接跳过这个操作;
如果不是就交换当前左上角的数和需要的数字
这种算法可以生成(3\times 2)^{20}\times(3\times2)^{20}种数独,绝对远远大于题目要求。如果伪随机算法足够优秀,便不会生成相同的数独

数独求解

我们可以用传统的回溯算法解决数独问题,也可以吧数独转换为一个精确匹配问题,然后用dancing link算法求解。这个项目选择的是回溯算法。
思路其实非常简单,就是针对每个空白的点,遍历每一个空白的字符,寻找每一种可能,如果走进了死胡同就退回去。
这只是最朴素的想法,当然在这上面也可进行优化,比如说在每个状态自动填充一次可被填充的空格,但是在回溯上就会出现问题。

资料搜集过程

在北京大学poj的poj 2676题目就是一道数独求解的题目,针对这道题目有很多高效的解法。
在这里我们主要参考了这篇博客中的剪枝方法。
生成数独的算法借鉴了博客

代码分析

生成数独

    int mat_num = rand() % 4;
    Sudoku rt;
    // init
    for(int i = 0; i < 9; i++) for(int j = 0; j < 9; j++)
        rt.sudoku[i][j] = init_matrix[mat_num][i][j];
    // shift line
    for(int i = 0; i < 20; i++){
        int block_num = rand() % 3; //随机选择一个“块”
        int first_shift = rand() % 3;
        int second_shift = rand() % 2;
        if(second_shift >= first_shift) second_shift ++; //随机选择要交换的两行
        first_shift += block_num * 3;
        second_shift += block_num * 3; //与块相加
        int tmp;
        for(int i = 0; i < 9; i++){
            tmp = rt.sudoku[first_shift][i];
            rt.sudoku[first_shift][i] = rt.sudoku[second_shift][i];
            rt.sudoku[second_shift][i] = tmp;
        } //交换两行
    }
    //shift column
    for(int i = 0; i < 20; i++){
        int block_num = rand() % 3; //选择一个块
        int first_shift = rand() % 3; 
        int second_shift = rand() % 2;
        if(second_shift >= first_shift) second_shift ++;
        first_shift += block_num * 3;
        second_shift += block_num * 3; //选择要交换的两列
        int tmp;
        for(int i = 0; i < 9; i++){
            tmp = rt.sudoku[i][first_shift];
            rt.sudoku[i][first_shift] = rt.sudoku[i][second_shift];
            rt.sudoku[i][second_shift] = tmp;
        } //交换两列
    }

求解数独

void solve_traceback(Sudoku * s){
    if(_sudoku_solve) return; //如果已经解决就直接退出
    int _cnt = 0;
    for(int i = 0; i < 9; i++) for(int j = 0; j < 9; j++)
        if(s->sudoku[i][j]) _cnt ++;
    if(_cnt != s->filled) error=1;
    if(s->filled == 81){ //如果填满就打印数独,并且设置为已解决
        _sudoku_solve = 1;
        print_sudoku(s);
        return;
    }
    //find the empty point
    int i, j = 0;
    _find_empty(s, &i, &j); //寻找空白点
    s->filled++;
    for(int num = 1; num < 10; num++){
        int flag = check_one(s, i, j, num);
        if(flag){
            s->sudoku[i][j] = num;
            solve_traceback(s);
        }
    }
    //traceback
    s->filled--;
    //s->filled -= fill_num;
    s->sudoku[i][j] = 0;
    //for(i = 0; i < fill_num; i++)
    //    s->sudoku[fill_x[i]][fill_y[i]] = 0;
}

实现过程

由于C语言没有类的概念,所以本程序没有类的概念,而用结构体来代替

#ifndef _SUDOKU_STRUCT
#define _SUDOKU_STRUCT
typedef struct{
    int sudoku[9][9];
    int filled;
}Sudoku;
#endif

Sudoku数据结构由两部分组成,一部分是9*9的数独矩阵,另一部分是已填的数据,这个数据在回溯求解的时候会用得上。
有下面几个函数:
* 将数独输出到文件
int output_to_file(FILE* file, Sudoku s);
* 从文件中读取数独
int load_from_file(FILE* file, Sudoku * s);
* 生成数独
Sudoku generate_sudoku();
* 检查数独是否合法
int check_sudoku(Sudoku* s);
* 检查某个位置是否能填上某个数字
int check_one(Sudoku *s, int pt_i, int pt_j);
* 回溯求解
void solve_traceback(Sudoku * s);
* 输出数独
`void print_sudoku(Sudoku * s);“

性能分析

函数调用分析

数独终局生成:
《软工大作业数独》
我们可以发现大部分时间都集中在输入输出上
数独求解:
《软工大作业数独》
数独求解的大部分时间花在递归调用回溯求解数独上。

PSP表格

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

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据