算法实践:数独(1)

算法实践:数独(1)数独(1)描述为了找到百年沉睡的原因,寻回百年前与公主一起的记忆碎片,明白自己是谁,林克必须激活成功教程数独谜题。林克需要在限定时间内,把9×9的数独补充完整,使得图中每行、每列、每个3×3的九宫格内数字1~9均恰好出现一次。林克需要寻回失去的记忆碎片,你,作为林克的朋友,需要帮忙林克寻回9×9棋盘中失去的数字。或许有一天,林克也能帮助你,寻回关于你是谁,你从哪里来的记忆碎片。这是数独试炼…

数独(1)

描述

为了找到百年沉睡的原因,寻回百年前与公主一起的记忆碎片,明白自己是谁,林克必须激活成功教程数独谜题。

林克需要在限定时间内,把9×9的数独补充完整,使得图中每行、每列、每个3 × 3的九宫格内数字1~9均恰好出现一次。

林克需要寻回失去的记忆碎片,你,作为林克的朋友,需要帮忙林克寻回9×9棋盘中失去的数字。

或许有一天,林克也能帮助你,寻回关于你是谁,你从哪里来的记忆碎片。

这是数独试炼I(解密成功可以解锁林克前25%的记忆碎片)
在这里插入图片描述

输入

输入为9×9的数据。一共9行,每行有9个数字。

数字为0表示对应的数字盘为空。

输出

对于每个测试用例,程序应以与输入数据相同的格式打印解决方案(9×9)。

空单元格必须根据规则进行填充。

如果解决方案不是唯一的,则程序可以打印其中任何一种。

样例

103000509
002109400
000704000
300502006
060000050
700803004
000401000
009205800
804000107
143628579
572139468
986754231
391542786
468917352
725863914
237481695
619275843
854396127

难度

高,深搜

解法

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-7N0nHGum-1586941483353)(C:\Users\HUAWEI\AppData\Roaming\Typora\typora-user-images\image-20200415165457178.png)]

数独数据结构设计如上

Sudu[ N ] [ N ] 存放数独棋盘中的数字,0代表还没有填

row[ N ] [ N ],col [ N ] [ N ],grid[ N ] [ N ] 为三个标志位,用于判断数字是否重复摆放。例如上述图中(0,0)号位置为1,它的所在行为0,所在列为0,所在grid为0 (把每个3*3的九宫格看成一个grid)按行至列排序为 0-8,转换方法为:

第r行第c列的元素在 第k个grid里(k = (r/3) * 3 + c/3)

紧接着进行常规法深搜。

代码

#include<bits/stdc++.h>
using namespace std;

const int N9 = 9; //递归9层
const int N = 10;
int Sudu[N][N];
bool row[N][N],col[N][N],grid[N][N];
//每一行每一列扫描
bool dfs(int r,int c){ 
   
    if(r==N9) return true;  //[0-8]
    bool flag = false;  //是否找到可行解
    if(Sudu[r][c]){ 
         //Sudu中数字不为1
        if(c==8) flag = dfs(r+1,0);  //搜索下一行
        else flag = dfs(r,c+1);
        return flag;
    }
    //每一个3*3的grid,寻找第k个grid
    int k = (r/3)*3 + c/3;
    for(int i=1;i<=9;i++){ 
      //尝试在Sudu[r][c]摆下1-9的数字
        if(!row[r][i] && !col[c][i] && !grid[k][i]){ 
     //如果该数字还没有被摆放
            row[r][i] = true; col[c][i] = true; grid[k][i] = true;  //每行每列每grid标志
            Sudu[r][c] = i;  //从1-9开始尝试摆下数字
            if(c==8) flag = dfs(r+1,0);  //搜索下一行
            else flag = dfs(r,c+1);
            if(flag) return true;
            //还原状态
            Sudu[r][c]=0;
            row[r][i] = false; col[c][i] = false; grid[k][i] = false;
        }
    }
    return false;
}

int main()
{ 
   
    //输入输出加速
    std::ios::sync_with_stdio(false);
    std::cin.tie(NULL);
    std::cout.tie(NULL);

    memset(row,false,sizeof(row));
    memset(col,false,sizeof(col));
    memset(grid,false,sizeof(grid));
    for(int i=0;i<N9;i++)
        for(int j=0;j<N9;j++){ 
   
            char ch;
            cin>>ch;
            Sudu[i][j] = ch - '0';
            if(Sudu[i][j]){ 
   
                row[i][Sudu[i][j]] = true;  //第i行中Sudu中的数字已经被使用
                col[j][Sudu[i][j]] = true; //第j行中Sudu中的数字已经被使用
                grid[(i/3)*3 + j/3][Sudu[i][j]] = true;  //第grid方块中Sudu中的数字已经被使用
            }
        }
    dfs(0,0);
    cout<<"解为:"<<endl;
    for(int i=0;i<N9;i++){ 
   
        for(int j=0;j<N9;j++)
            cout<<Sudu[i][j];
        cout<<endl;
    }
}

今天的文章算法实践:数独(1)分享到此就结束了,感谢您的阅读。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:https://bianchenghao.cn/11447.html

(0)
编程小号编程小号

相关推荐

发表回复

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