TOJ 3287 Sudoku 9*9数独 dfs

2024-03-29 13:08
文章标签 dfs 数独 sudoku toj 3287

本文主要是介绍TOJ 3287 Sudoku 9*9数独 dfs,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

描述

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. 

输入

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.

输出

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.

样例输入

1
103000509
002109400
000704000
300502006
060000050
700803004
000401000
009205800
804000107

样例输出

143628579
572139468
986754231
391542786
468917352
725863914
237481695
619275843
854396127

题目来源

Southeastern Europe 2005

数独规则:横向,纵向,3*3的小方格里,1-9各出现一次。

题意:0的位置填补数,输出一种填法。3*(i/3)+j/3是计算在第几个小方格里。

#include<stdio.h>
#include<string.h>
#include<math.h>
#include<iostream>
#include<string>
#include<algorithm>
#include<map>
#include<set>
#include<queue>
#include<vector>
using namespace std;
#define inf 0x3f3f3f3f
#define LL long long
int a[20][20],flag;
int r[20][20],l[20][20],s[20][20];//r行 l列 s小方阵 
void dfs(int i,int j)
{if(i==9&&j==0)flag=1;	else{if(a[i][j]!=0){if(j<8)dfs(i,j+1);elsedfs(i+1,0);}else{for(int k=1;k<=9;k++){if(!r[i][k]&&!l[j][k]&&!s[3*(i/3)+j/3][k]){a[i][j]=k;r[i][k]=1;l[j][k]=1;s[3*(i/3)+j/3][k]=1;if(j<8)dfs(i,j+1);elsedfs(i+1,0);if(flag)return;//回溯重置 a[i][j]=0;r[i][k]=0;l[j][k]=0;s[3*(i/3)+j/3][k]=0;}}}}
}
int main()
{int t,i,j;scanf("%d",&t);while(t--){memset(r,0,sizeof r);memset(l,0,sizeof l);		memset(s,0,sizeof s);for(i=0;i<9;i++){for(j=0;j<9;j++){scanf("%1d",&a[i][j]);if(a[i][j]){r[i][a[i][j]]=1;l[j][a[i][j]]=1;s[3*(i/3)+j/3][a[i][j]]=1;}}}flag=0;dfs(0,0);for(i=0;i<9;i++){for(j=0;j<9;j++){printf("%d",a[i][j]);}printf("\n");}}
}

 

这篇关于TOJ 3287 Sudoku 9*9数独 dfs的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/858673

相关文章

hdu 2489 (dfs枚举 + prim)

题意: 对于一棵顶点和边都有权值的树,使用下面的等式来计算Ratio 给定一个n 个顶点的完全图及它所有顶点和边的权值,找到一个该图含有m 个顶点的子图,并且让这个子图的Ratio 值在所有m 个顶点的树中最小。 解析: 因为数据量不大,先用dfs枚举搭配出m个子节点,算出点和,然后套个prim算出边和,每次比较大小即可。 dfs没有写好,A的老泪纵横。 错在把index在d

poj 3050 dfs + set的妙用

题意: 给一个5x5的矩阵,求由多少个由连续6个元素组成的不一样的字符的个数。 解析: dfs + set去重搞定。 代码: #include <iostream>#include <cstdio>#include <set>#include <cstdlib>#include <algorithm>#include <cstring>#include <cm

ural 1149. Sinus Dances dfs

1149. Sinus Dances Time limit: 1.0 second Memory limit: 64 MB Let  An = sin(1–sin(2+sin(3–sin(4+…sin( n))…) Let  Sn = (…( A 1+ n) A 2+ n–1) A 3+…+2) An+1 For given  N print  SN Input One

hdu 6198 dfs枚举找规律+矩阵乘法

number number number Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Problem Description We define a sequence  F : ⋅   F0=0,F1=1 ; ⋅   Fn=Fn

深度优先(DFS)和广度优先(BFS)——算法

深度优先 深度优先搜索算法(英语:Depth-First-Search,DFS)是一种用于遍历或搜索树或图的算法。 沿着树的深度遍历树的节点,尽可能深的搜索树的分支,当节点v的所在边都己被探寻过,搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点,则选择其中一个作为源节点并重复以上过程,整个进程反复进行直到所有节点都被访

nyoj99(并查集+欧拉路+dfs)

单词拼接 时间限制: 3000 ms  |  内存限制: 65535 KB 难度: 5 描述 给你一些单词,请你判断能否把它们首尾串起来串成一串。 前一个单词的结尾应该与下一个单词的道字母相同。 如 aloha dog arachnid gopher tiger rat   可以拼接成:aloha.arachnid.dog.gopher.rat.tiger 输入 第一行是一个整

【CF】E. Anya and Cubes(双向DFS)

根据题意的话每次递归分3种情况 一共最多25个数,时间复杂度为3^25,太大了 我们可以分2次求解第一次求一半的结果,也就是25/2 = 12,记录结果 之后利用剩余的一半求结果 s-结果 = 之前记录过的结果 就可以 时间复杂度降低为 3 ^ (n/2+1) 题目链接:http://codeforces.com/contest/525/problem/E #include<set

力扣 797. 所有可能路径【DFS】

1. 题目 2. 代码 DFS , 直接见代码 class Solution {public:vector<int> path;vector<vector<int>> res; // 结果集void dfs(vector<vector<int>>& graph, int cur, int n){// 找出所有从节点 0 到节点 n-1 的路径// 下标从 0 开始的if (

CF Bayan 2015 Contest Warm Up B.(dfs+暴力)

B. Strongly Connected City time limit per test 2 seconds memory limit per test 256 megabytes input standard input output standard output 题目链接: http://codeforces.com/contest/475/probl

POJ 2386 Lake Counting(DFS)

题目: http://poj.org/problem?id=2386 题解: 遍历一次,遇到w,一次DFS后,与此w连接的所有w都被替换成‘ . ’,直到遍历完图中不再存在w为止,总共进行DFS的次数就是答案了。 代码: #include<stdio.h>int N,M;char map[110][110];void dfs(int x,int y){map[x][y]='