数独的生成和求解

1.代码托管地址

https://github.com/dong199903/suDu

2.耗费时间

3.需求分析

• 用熟悉的编程语言实现数独的题目
• 总体分为生成不重复的数独文件，并求解数独文件的数独程序
• 要求按照软件工程规范来设计，且数独的第一个是按照学号计算来的
• 要求数独可以用两种命令去实现对应的功能
• 要求列出程序的性能图

4.解题思想

• 按照题目要求，大致分为两个模块去分别实现，所以我初步设计两个类，一个是Sudu_Construct类，一个是Sudu_Deal类分别处理数独，其中Sudu_Construct类就是用户可以通过-r 行数的方式构造出数独，并将数独文件写在suduku.txt里面。另外一个Sudu_Deal类是求解对应数独文件，求出数独的解过程。
• 首先要求构造数独，且不能重复，那我开始还很犹豫用什么写，于是搜集网上各种建议，并通过test文件测试这些方法，决定用全排列也就是回溯的方法去解决问题。

5.设计过程

• 大体固定两个类，一个构造数独的类，一个求解数独的类。
• 结合网络资料，从模仿学习到自己的独立去完整实现。
• 不断优化各类程序解决的复杂，保证程序健壮性，符合软件工程代码规范
• 将每次改进和代码优化以及文档的编写，都去逐步完善。

6.程序性能时间

1.jpg

7.代码说明

首先是两个类的定义

• Sudu_Construct类的定义

#pragma once
//构造数独
class Sudu_Construct
{
private:
    int count;//个数
public:
    Sudu_Construct(int num);//构造函数
    ~Sudu_Construct();
    void getSudu();
    int getCount();
};

• Sudu_Deal类的定义

#pragma once
class Sudu_Deal {
public:
    int data[10][10];
    int biaoji[10][10];
public:
    Sudu_Deal();
    void deal();
    int find(int x,int y);
    ~Sudu_Deal();
};

• 构造数独的核心过程

//构造数独
void  Sudu_Construct::getSudu()
{
    int count = 0,temp;
    int port[10] = { 0,0,6,5,4,3,2,1,7,8 };
    char str[10] = { '9','3','1','2','7','4','5','6','8','9' };
    if (count < this->count)
    {
        for (int a = 0; a < 6; a++)
        {
            if (count == this->count)
                break;
            if (a)
                next_permutation(port + 4, port + 6);
            for (int b = 0; b < 6; b++)
            {
                if (b)
                    next_permutation(port + 7, port + 9);
                int t = 0;
                //char kong = ' ';
                do {
                    if (t)
                        next_permutation(str + 2, str + 9);
                    for (int i = 1; i <= 9; i++)
                    {
                        for (int j = 1; j <= 9; j++)
                        {

                            if (j - port[i] >= 0)
                                temp = j - port[i];
                            else
                                temp = j - port[i] + 9;
                            //putchar(str[temp % 9]);
                            cout << str[temp % 9];
                            if (j < 9)
                                //putchar(' ');
                                cout << " ";
                        }
                        cout << endl;
                    }
                    count++;
                    t++;
                    if (count == this->count)
                        break;
                    else
                        cout << endl;
                } while (t<40320);
                if (count == this->count)
                    break;
            }
        }
    }
}

• 处理数独

int Sudu_Deal::find(int x, int y)
{
    if (x > 9 || y > 9) return 1;
    if (biaoji[x][y])
    {
        if (y < 9)
        {
            if (find(x, y + 1))
                return 1;
        }
        else
        {
            if (x < 9)
            {
                if (find(x + 1, 1))
                    return 1;
            }
            else
                return 1;
        }
    }
    else
    {
        for (int n1 = 1; n1 <= 9; n1++)
        {
            int slogan = 1;
            for (int i = 1; i <= 9; i++)//看列有没有
            {
                if (this->data[i][y] == n1)
                {
                    slogan = 0;
                    break;
                }
            }
            if (slogan)//看行有没有
            {
                for (int j = 1; j <= 9; j++)
                {
                    if (this->data[x][j] == n1)
                    {
                        slogan = 0;
                        break;
                    }
                }
            }
            if (slogan)
            {
                int rawtop, columntop;
                if (x % 3 == 0)
                    rawtop = x;
                else
                    rawtop = (x / 3) * 3 + 3;
                if (y % 3 == 0)
                    columntop = y;
                else
                    columntop = (y / 3) * 3 + 3;
                for (int i = rawtop - 2; i <= rawtop; i++)
                {
                    for (int j = columntop - 2; j <= columntop; j++)
                    {
                        if (this->data[i][j] == n1)
                        {
                            slogan = 0;
                            break;
                        }
                    }
                    if (!slogan)
                        break;
                }
            }
            if (slogan)//判断过后看1-9放哪一个
            {
                this->data[x][y] = n1;
                if (y < 9)
                {
                    if (find(x, y + 1))
                        return 1;
                }
                else
                {
                    if (x < 9)
                    {
                        if (find(x + 1, 1))
                            return 1;
                    }
                    else
                        return 1;
                }
                this->data[x][y] = 0;
            }
        }
    }
    return 0;
}

总结

通过本次个人项目数独程序的完成，我用软件工程中的需求分析，和代码规范去理解问题，组织程序，到最后的实现完成，整个过程其实还是磕磕绊绊的，因为回溯法没理解深刻，上手code也比较费劲，最后通过网上阅读回溯，和问同学，完成了整个基本流程。