Error message here!

Hide Error message here!

忘记密码?

Error message here!

请输入正确邮箱

Hide Error message here!

密码丢失?请输入您的电子邮件地址。您将收到一个重设密码链接。

Error message here!

返回登录

Close

【POJ - 2676】Sudoku(数独 dfs+回溯)

Sky丨Star 2019-07-16 19:15:00 阅读数:31 评论数:0 点赞数:0 收藏数:0

-->Sudoku

直接中文

Descriptions:

Sudoku对数独非常感兴趣,今天他在书上看到了几道数独题: 
给定一个由3*3的方块分割而成的9*9的表格(如图),其中一些表格填有1-9的数字,其余的则为空白(数字0为空白)。请在空白表格中填入数字1-9使得9*9表格的每行、每列、每个3*3块内无重复数字。 

Input

第一行输入一个整数T,表示样例数量。对于每个样例, 一共9行, 表示数独表格的每一行。接下来每一行输入一个字符串表示数独表格的每一行的9个数字。数独表格中空白用数字0表示。

Output

对于每组样例,输出完整的数独表格,即数独表格的每一个空白都按规定填满数字。如果答案不唯一,输出任何一个答案就行。

Sample Input

1
103000509
002109400
000704000
300502006
060000050
700803004
000401000
009205800
804000107

Sample Output

143628579
572139468
986754231
391542786
468917352
725863914
237481695
619275843
854396127

提示可能会有多组解,输出其中一种即可。

题目链接:

https://vjudge.net/problem/POJ-2676

 

1~9 一个一个枚举

dfs试探,失败则回溯

用三个数组进行标记每行、每列、每个子网格已用的数字,用于剪枝

bool row[10][10];    //row[i][x]  标记在第i行中数字x是否出现了

bool col[10][10];    //col[j][y]  标记在第j列中数字y是否出现了

bool grid[10][10];   //grid[k][x] 标记在第k个3*3子格中数字z是否出现了

row 和 col的标记比较好处理,关键是找出grid子网格的序号与 行i列j的关系

即要知道第i行j列的数字是属于哪个子网格的

 

首先我们假设子网格的序号如下编排:

 

由于1<=i、j<=9,我们有: (其中“/”是C++中对整数的除法)

 

令a= i/3 , b= j/3  ,根据九宫格的 行列 与 子网格 的 关系,我们有:

 

不难发现 3a+b=k

即 3*(i/3)+j/3=k

 

又我在程序中使用的数组下标为 1~9,grid编号也为1~9

因此上面的关系式可变形为 3*((i-1)/3)+(j-1)/3+1=k
以上论述转自https://blog.csdn.net/lyy289065406/article/details/6647977

AC代码:

#include <iostream>
#include <cstdio>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <deque>
#include <vector>
#include <queue>
#include <string>
#include <cstring>
#include <map>
#include <stack>
#include <set>
#include <sstream>
#define mod 1000000007
#define eps 1e-6
#define ll long long
#define INF 0x3f3f3f3f
#define MEM(x,y) memset(x,y,sizeof(x))
#define Maxn 15
using namespace std;
int result;
int T,h,w;
int mp[Maxn][Maxn];//地图
bool row[Maxn][Maxn];//row[i][x]  标记在第i行中数字x是否出现了
bool col[Maxn][Maxn];//col[j][y]  标记在第j列中数字y是否出现了
bool grid[Maxn][Maxn];//grid[k][x] 标记在第k个3*3子格中数字z是否出现了
int dfs(int x,int y)
{
    if(x==)
        return ;
    int f=;
    if(mp[x][y])
    {
        if(y==)
            f=dfs(x+,);
        else
            f=dfs(x,y+);
        if(f)//回溯
            return ;
        else
            return ;
    }
    else
    {
        int k=*((x-)/)+(y-)/+;
        for(int i=; i<=; i++)//枚举1~9填空
            if(!row[x][i]&&!col[y][i]&&!grid[k][i])
            {
                mp[x][y]=i;
                row[x][i]=;
                col[y][i]=;
                grid[k][i]=;
                if(y==)
                    f=dfs(x+,);
                else
                    f=dfs(x,y+);
                if(!f)//回溯,继续枚举
                {
                    mp[x][y]=;
                    row[x][i]=;
                    col[y][i]=;
                    grid[k][i]=;
                }
                else
                    return ;
            }
    }
    return ;
}
int main()
{
    int h=w=;
    cin>>T;
    while(T--)
    {
        MEM(row,);
        MEM(col,);
        MEM(grid,);
        for(int i=; i<=h; i++)
            for(int j=; j<=w; j++)
            {
                char ch;//注意,这里一定要用char类型,不然读不进去
                cin>>ch;
                mp[i][j]=ch-'';
                if(mp[i][j])
                {
                    int k=*((i-)/)+(j-)/+;
                    row[i][mp[i][j]]=;
                    col[j][mp[i][j]]=;
                    grid[k][mp[i][j]]=;
                }
            }
        //从(1,1)开始搜索
        dfs(,);
        //输出
        for(int i=; i<=h; i++)
        {
            for(int j=; j<=w; j++)
                cout<<mp[i][j];
            cout<<endl;
        }
    }
}

 

版权声明
本文为[Sky丨Star]所创,转载请带上原文链接,感谢
https://www.cnblogs.com/sky-stars/p/11196903.html