poj 2676 Sudoku_数独 17997-程序员宅基地

技术标签： ----------搜索算法----------- DFS ----------各大OJ---------- ---Primary Algorithm(POJ)--- POJ

Sudoku

Time Limit: 2000MS		Memory Limit: 65536K
Total Submissions: 17997		Accepted: 8714		Special Judge

Description

Sudoku is a very simple task. A square table with 9 rows and 9 columns is divided to 9 smaller squares 3x3 as shown on the Figure. In some of the cells are written decimal digits from 1 to 9. The other cells are empty. The goal is to fill the empty cells with decimal digits from 1 to 9, one digit per cell, in such way that in each row, in each column and in each marked 3x3 subsquare, all the digits from 1 to 9 to appear. Write a program to solve a given Sudoku-task.

Input

The input data will start with the number of the test cases. For each test case, 9 lines follow, corresponding to the rows of the table. On each line a string of exactly 9 decimal digits is given, corresponding to the cells in this line. If a cell is empty it is represented by 0.

Output

For each test case your program should print the solution in the same format as the input data. The empty cells have to be filled according to the rules. If solutions is not unique, then the program may print any one of them.

Sample Input

Sample Output

Source

Southeastern Europe 2005

提示

题意：

数独问题，就是每行，每列，每个九宫格没有重复的数字。找出符合的答案，如果不唯一输出其中一个就行。

思路：

记录下要填数字的位置会比较方便些。

示例程序

Source Code

Problem: 2676		Code Length: 1560B
Memory: 392K		Time: 16MS
Language: GCC		Result: Accepted
#include <stdio.h>
#include <string.h>
struct
{
    int x,y;
}q[81];							//q[]用来记录所需填数字的位置
int r[9][9],c[9][9],sq[3][3][9],map[9][9],bug;
void dfs(int num)
{
    int i,i1,x1,y1;
    x1=q[num].x;
    y1=q[num].y;
    if(bug==1)					//找到就不要找了
    {
        return;
    }
    if(num==-1)
    {
        for(i=0;9>i;i++)
        {
            for(i1=0;9>i1;i1++)
            {
                printf("%d",map[i][i1]);
            }
            printf("\n");
        }
        bug=1;
        return;
    }
    for(i=0;9>i;i++)
    {
        if(r[x1][i]==0&&c[y1][i]==0&&sq[x1/3][y1/3][i]==0)				//要保证列，行，九宫格不会有重复的
        {
            r[x1][i]=1;
            c[y1][i]=1;
            sq[x1/3][y1/3][i]=1;
            map[x1][y1]=i+1;
            dfs(num-1);
            r[x1][i]=0;					//回溯
            c[y1][i]=0;
            sq[x1/3][y1/3][i]=0;
        }
    }
}
int main()
{
    int t,i,i1,i2,i3,num;
    scanf("%d",&t);
    for(i=1;t>=i;i++)
    {
        bug=0;
        num=0;
        memset(c,0,sizeof(c));						//行的数字重复记录
        memset(r,0,sizeof(r));						//列的数字重复记录
        memset(sq,0,sizeof(sq));					//9个九宫格的数字重复记录
        for(i1=0;9>i1;i1++)
        {
            for(i2=0;9>i2;i2++)
            {
                scanf("%1d",&map[i1][i2]);					//因为每格为1个数字，这里用%1d来限制输入
                if(map[i1][i2]!=0)
                {
                    r[i1][map[i1][i2]-1]=1;
                    c[i2][map[i1][i2]-1]=1;
                    sq[i1/3][i2/3][map[i1][i2]-1]=1;
                }
                else
                {
                    q[num].x=i1;
                    q[num].y=i2;
                    num++;
                }
            }
        }
        dfs(num-1);
    }
    return 0;
}

本文链接：https://blog.csdn.net/a15110103117/article/details/52161844

原作者删帖不实内容删帖广告或垃圾文章投诉

智能推荐

ora hash oracle官网,oracle计算hash值-程序员宅基地

文章浏览阅读503次，点赞2次，收藏2次。oracle计算hash值1、dbms_utility.get_hash_value(name VARCHAR2,base NUMBER,hash_size NUMBER)函数说明name：输入值base：返回hash value的起始值(hash bucket最小值)hash_size：返回hash表的期望大小(hash bucket最大值)这个函数用于计算并返回落在给定范围内的hash值2、o..._oracle中ora_hash用法

【源码分析】Lottie 实现炫酷动画背后的原理_lottie.setanimation原理-程序员宅基地

文章浏览阅读272次。0. 前言自我在内网发布了一篇关于 Lottie 的原理分析的文章之后，就不断有同事来找我询问关于 Lottie 的各种东西，最近又有同事来问，就想着可能对大家也会有所帮助，就稍作处理后分享出来。需要注意的是，这文章写于两年前，基本版本 2.0.0-beta3，虽然我看过最新版本，主要的类没有什么差别，不过可能还是会存在一些差异。可以感受一下我两年前的实力。_lottie.setanimation原理

2023最新版本Activiti7系列-流程中的任务_activiti7流程和任务的关系-程序员宅基地

文章浏览阅读777次。Activiti7中各种任务的详解_activiti7流程和任务的关系

Linux ps命令详解，Linux查看进程_ps -ef grep怎么看进程号_查看服务器的所有进程命令-程序员宅基地

文章浏览阅读901次，点赞14次，收藏12次。1）查看进程的时候，让进程按照CPU使用率排序，然后展示前10行，就能清晰地看到哪些进程占用的资源比较多。(img-e2CSAgPc-1713307447143)]系统化的资料的朋友，可以添加V获取：vip204888 （备注大数据）**查看某个用户开启了哪些进程，可以使用。，就能查看内存使用最多的10个进程。3）如果不限制行数，也可以使用。来过滤指定的进程，比如。_查看服务器的所有进程命令

Chrome 扩展程序——Imagus：图片放大预览工具-程序员宅基地

文章浏览阅读3.3w次，点赞2次，收藏2次。主要介绍 Imagus 的功能及应用，Imagus 是一款简单实用的图片放大预览工具。_imagus

python 描述符_Python黑魔法之描述符-程序员宅基地

文章浏览阅读113次。引言Descriptors(描述符)是Python语言中一个深奥但很重要的一个黑魔法，它被广泛应用于Python语言的内核，熟练掌握描述符将会为Python程序员的工具箱添加一个额外的技巧。本文我将讲述描述符的定义以及一些常见的场景，并且在文末会补充一下__getattr__，__getattribute__,__getitem__这三个同样涉及到属性访问的魔术方法。描述符的定义descr__g..._python revealaccess

随便推点

基于Java,SpringBoot,Vue,UniAPP的微信商城小程序_基于springboot的微信小程序商城-程序员宅基地

文章浏览阅读507次，点赞3次，收藏8次。本课题旨在探讨和实现一个基于SpringBoot后端框架和UniApp前端框架的微信商城小程序。SpringBoot作为一种简化的、用于快速开发企业级应用的开源框架，提供了一套全面的基础架构支持，包括自动配置、依赖管理以及安全性等特性，使得开发者能够以最少的配置快速启动和运行项目。结合UniApp，一种使用Vue.js开发所有前端应用的框架，它允许开发者编写一次代码，然后发布到iOS、Android、Web（包括微信小程序及其他小程序平台）等多个平台。_基于springboot的微信小程序商城