文档章节

sicily 1317 Sudoku

Ciel
 Ciel
发布于 2013/01/09 17:20
字数 1132
阅读 127
收藏 0

Description

Sudoku is a placement puzzle. The goal is to enter a symbol in each cell of a grid, most frequently a x 9 grid made up of x 3subgrids. Each row, column and subgrid must contain only one instance of each symbol. Sudoku initially became popular in Japan in 1986 and attained international popularity in 2005.

 

\epsfbox{p3477.eps}

The word Sudoku means ``single number" in Japanese. The symbols in Sudoku puzzles are often numerals, but arithmetic relationships between numerals are irrelevant.


According to wikipedia:

The number of valid Sudoku solution grids for the standard  x 9 grid was calculated by Bertram Felgenhauer in 2005 to be 6,670,903,752,021,072,936,960, which is roughly the number of micrometers to the nearest star. This number is equal to  9! * 72$\scriptstyle \wedge$* 2$\scriptstyle \wedge$* 27, 704, 267, 971 , the last factor of which is prime. The result was derived through logic and brute force computation. The number of valid Sudoku solution grids for the  16 x 16 derivation is not known.

Write a program to find a solution to a x 9 Sudoku puzzle given a starting configuration.

Input

The first line will contain an integer specifying the number of puzzles to be solved. The remaining lines will specify the starting configuration for each of the puzzles. Each line in a starting configuration will have nine characters selected from the numerals 1-9 and the underscore which indicates an empty cell.

Output

For each puzzle, the output should specify the puzzle number (starting at one) and describe the solution characteristics. If there is a single solution, it should be printed. Otherwise, a message indicating whether there are no solutions or multiple solutions should be printed. The output should be similar to that shown below. All input cases have less than 10,000 solutions.

Sample Input

3
________4
1____9_7_
__37_28__
____7_26_
4_______8
_91_6____
__42_36__
_3_14___9
9________
7_9__2___
3_____891
___39___4
48__6____
__5___6__
____4__23
2___57___
568_____7
___8__4_2
82_______
___5__2__
__6_4_7__
_5___1_7_
9_2_5_4_1
_3_8_6_9_
__3_6_1__
__5__2___
_______34

Sample Output

Puzzle 1 has 6 solutions

Puzzle 2 solution is
719482365
324675891
856391274
482563719
135729648
697148523
243957186
568214937
971836452

Puzzle 3 has no solution

分析:

本题较为复杂,虽然能够看出明显应该用深度搜索方法,但是即使时间限制有10s使用暴力算法仍然会超时,需要一定的优化和剪枝。按照做数独的一般思路,先对数独空格进行可能性分析将所有格子的可能答案数做记录(已有的记为1),然后每次搜索之前先进行筛选,从前向后找答案数最少的进行深搜,一旦搜完再整理结果。剪枝的方案是,搜索时遇到有格子无法填入数字(即答案数为0)就返回0值。同时,注意因为深搜是反复进行的,输入数组会被反复还原,可能的答案要另行保存不能使用原有输入的数组。本题能很好的考察搜索的特点,值得反复研究,而且数独也是很有趣的数学谜题。

PS:注意输出数据的格式调整。

代码:

// Problem#: 1317
// Submission#: 1877449
// The source code is licensed under Creative Commons Attribution-NonCommercial-ShareAlike 3.0 Unported License
// URI: http://creativecommons.org/licenses/by-nc-sa/3.0/
// All Copyright reserved by Informatic Lab of Sun Yat-sen University
#include <iostream>
#include <cstring>
#include <fstream>
using namespace std;

int sudoku[9][9],recnt,ans[9][9],p[82];
bool isvalid[9][9][10],flag;

int dfs(){
    int n = 81;
    int x,y;
    for( int i=0 ; i<81 ; i++ ){
        x = i/9;
        y = i%9;
        if( sudoku[x][y] ) continue;
        if( !p[i] ) return 0;
        if( p[i]>0 && p[i]<p[n] ) n = i;
    }
    if(n==81){
        if( flag ){
            flag = false;
            memcpy(ans,sudoku,sizeof(ans));
        }
        return 1;
    }
    x = n/9;
    y = n%9;
    int trow[81],tcol[81],c;
    int re = 0;
    for( int t=1 ; t<10 ; t++ ){
        if( isvalid[x][y][t] ){
            int tp[82];
            memcpy(tp,p,sizeof(tp));
            sudoku[x][y] = t;
            c = 0;
            p[n] = 0;
            for( int k=0 ; k<9 ; k++ ){
                if( isvalid[k][y][t] ){
                    isvalid[k][y][t] = false;
                    trow[c] = k;
                    tcol[c++] = y;
                    p[k*9+y]--;
                }
                if( isvalid[x][k][t] ){
                    isvalid[x][k][t] = false;
                    trow[c] = x;
                    tcol[c++] = k;
                    p[x*9+k]--;
                }
            }
            for( int r=x/3*3 ; r < (x/3+1)*3 ; r++ )
                for( int s=y/3*3 ; s < (y/3+1)*3 ; s++ )
                    if( isvalid[r][s][t] ){
                        isvalid[r][s][t] = false;
                        trow[c] = r;
                        tcol[c++] = s;
                        p[r*9+s]--;
                    }
            re += dfs();
            for( int i=0 ; i<c ; i++ )
                isvalid[trow[i]][tcol[i]][t] = true;
            memcpy(p,tp,sizeof(p));
            sudoku[x][y] = 0;
        }
    }
    return re;
}

int main(){
    int n;
    char c;
    cin >> n;
    for(int count=1 ; count <= n ; count++){
        recnt = 0;
        flag = true;
        memset(sudoku,0,sizeof(sudoku));
        memset(isvalid,true,sizeof(isvalid));
        memset(p,0,sizeof(p));
        p[81] = 1000;
        for( int i=0 ; i<9 ; i++ ){
            for( int j=0 ; j<9 ; j++ ){
                cin >> c;
                if( c!='_' ){
                    sudoku[i][j] = c - '0';
                    int t = sudoku[i][j];
                    for( int k=0 ; k<9 ; k++ ){
                        isvalid[k][j][t] = k==i;
                        isvalid[i][k][t] = k==j;
                        isvalid[i][j][k+1] = k+1==t;
                    }
                    for( int r=i/3*3 ; r < (i/3+1)*3 ; r++ )
                        for( int s=j/3*3 ; s < (j/3+1)*3 ; s++ )
                            if( r!=i&&s!=j ) isvalid[r][s][t] = false;
                }
            }
        }
        for( int i=0 ; i<9 ; i++ )
            for( int j=0 ; j<9 ; j++ )
                for( int k=1 ; k<10 ; k++ )
                    if( isvalid[i][j][k] ) p[i*9+j]++;
        recnt += dfs();
        cout << "Puzzle " << count;
        if(recnt){
            if( recnt>1 ) cout << " has " << recnt << " solutions" << endl;
            else{
                cout << " solution is" << endl;
                for( int i=0 ; i<9 ; i++ ){
                    for( int j=0 ; j<9 ; j++ )
                        cout << ans[i][j];
                    cout << endl;
                }
            }
        }else{
            cout << " has no solution" << endl;
        }
        if( count<n ) cout << endl;
    }
    return 0;
}

© 著作权归作者所有

Ciel
粉丝 3
博文 24
码字总数 18532
作品 0
程序员
私信 提问
Oracle 11g R2 ADG 搭建

--============Oracle ADG搭建============== --==========准备阶段========= 1.检查primary为archivelog模式。 select log_mode from v$database; 如果为noarchivelog模式,切换到archivelo......

UltraSQL
2018/07/23
0
0
Leetcode 36. Valid Sudoku

文章作者:Tyan 博客:noahsnail.com | CSDN | 简书 1. Description 2. Solution Reference https://leetcode.com/problems/valid-sudoku/description/...

SnailTyan
2018/10/27
0
0
poj 3074 Sudoku

dlx算法解数独,有空会写详解,暂时就这样了 ......52..8.4......3...9...5.1...6..2..7........3.....6...1..........7.4.......3.end Sample Output 5273894168194267354367518293756921841......

locusxt
2014/01/17
339
0
验证数独棋盘

原题   Determine if a Sudoku is valid, according to: Sudoku Puzzles - The Rules.   The Sudoku board could be partially filled, where empty cells are filled with the charact......

一贱书生
2016/12/14
68
0
poj 2676 Sudoku

Sudoku Time Limit: 2000MS Memory Limit: 65536K Total Submissions: 22158 Accepted: 10496 Special Judge Description Sudoku is a very simple task. A square table with 9 rows and 9 ......

fire_to_cheat_
2018/03/31
0
0

没有更多内容

加载失败,请刷新页面

加载更多

Spring Boot WebFlux 增删改查完整实战 demo

03:WebFlux Web CRUD 实践 前言 上一篇基于功能性端点去创建一个简单服务,实现了 Hello 。这一篇用 Spring Boot WebFlux 的注解控制层技术创建一个 CRUD WebFlux 应用,让开发更方便。这里...

泥瓦匠BYSocket
9分钟前
4
0
从0开始学FreeRTOS-(列表与列表项)-3

FreeRTOS列表&列表项的源码解读 第一次看列表与列表项的时候,感觉很像是链表,虽然我自己的链表也不太会,但是就是感觉很像。 在FreeRTOS中,列表与列表项使用得非常多,是FreeRTOS的一个数...

杰杰1号
12分钟前
3
0
Java反射

Java 反射 反射是框架设计的灵魂(使用的前提条件:必须先得到代表的字节码的 Class,Class 类 用于表示.class 文件(字节码)) 一、反射的概述 定义:JAVA 反射机制是在运行状态中,对于任...

zzz1122334
38分钟前
3
0
聊聊nacos的LocalConfigInfoProcessor

序 本文主要研究一下nacos的LocalConfigInfoProcessor LocalConfigInfoProcessor nacos-1.1.3/client/src/main/java/com/alibaba/nacos/client/config/impl/LocalConfigInfoProcessor.java p......

go4it
昨天
5
0
前端技术之:webpack热模块替换(HMR)

第一步:安装HMR中间件: npm install --save-dev webpack-hot-middleware 第二步:webpack配置中引入webpack对象 const webpack = require('webpack’); 第三步:增加devServer配置项: ho......

popgis
昨天
5
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部