数独答案查询器_8阶数独

数独答案查询器_8阶数独数独是一种传统益智游戏,你需要把一个 9×9 的数独补充完整,使得图中每行、每列、每个 3×3 的九宫格内数字 1∼9 均恰好出现一次。请编写一个程序填写数独。输入格式输入包含多组测试用例。每个测试用例占一行,包含 81 个字符,代表数独的 81 个格内数据(顺序总体由上到下,同行由左到右)。每个字符都是一个数字(1−9)或一个 .(表示尚未填充)。您可以假设输入中的每个谜题都只有一个解决方案。文件结尾处为包含单词 end 的单行,表示输入结束。输出格式每个测试用例,输出一行数据,代表填充

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

数独是一种传统益智游戏,你需要把一个 9×9 的数独补充完整,使得图中每行、每列、每个 3×3 的九宫格内数字 1∼9 均恰好出现一次。

请编写一个程序填写数独。

输入格式
输入包含多组测试用例。

每个测试用例占一行,包含 81 个字符,代表数独的 81 个格内数据(顺序总体由上到下,同行由左到右)。

每个字符都是一个数字(1−9)或一个 .(表示尚未填充)。

您可以假设输入中的每个谜题都只有一个解决方案。

文件结尾处为包含单词 end 的单行,表示输入结束。

输出格式
每个测试用例,输出一行数据,代表填充完全后的数独。

输入样例:
4.....8.5.3..........7......2.....6.....8.4......1.......6.3.7.5..2.....1.4......
......52..8.4......3...9...5.1...6..2..7........3.....6...1..........7.4.......3.
end
输出样例:
417369825632158947958724316825437169791586432346912758289643571573291684164875293
416837529982465371735129468571298643293746185864351297647913852359682714128574936

题解
剪枝策略:

  1. 有限分支数较少的节点。
  2. 排除等价冗余
  3. 可行性减枝
  4. 最优性减枝
  5. 记忆化搜索
#include<bits/stdc++.h>
using namespace std;
const int N = 9;
char g[N][N];
int col[N],row[N],grid[3][3];
int ones[1 << N];
int Map[1 << N];
int res = 0;
int sum = 0;
string line;
int get(int x,int y){ 
   
    return ones[row[x] & col[y] & grid[x / 3][y / 3]];
}
int lowbit(int x){ 
   
    return (x & (-x));
}
void push(int x,int y,int v){ 
   
    col[y] -= (1 << v);
    row[x] -= (1 << v);
    grid[x / 3][y / 3] -= (1 << v);
    int in = x * 9 + y;
    line[in] = '1' + v;
    g[x][y] = '1' + v;
}
void back(int x,int y,int v){ 
   
    col[y] += (1 << v);
    row[x] += (1 << v);
    grid[x / 3][y / 3] += (1 << v);
    int in = x * 9 + y;
    line[in] = '.';
    g[x][y] = '.';
}
bool dfs(int k){ 
   
    // cout<<k<<endl;
    if(k == sum){ 
   
        cout<<line<<endl;
        return true;
    }
    int x, y, v = 10;
    for(int i = 0;i < N;i ++){ 
   
        for(int j = 0;j < N;j ++){ 
   
            if(g[i][j] == '.'){ 
   
                if(v > get(i,j)){ 
   
                    v = get(i , j);
                    x = i,y = j;
                }
            }
        }
    }
    int t = col[y] & row[x] & grid[x / 3][y / 3];
    while(t > 0){ 
   
        int tt = lowbit(t);
        t -= tt;
        push(x,y,Map[tt]);
        if(dfs(k + 1))return true;
        back(x,y,Map[tt]);
    }
    return false;
}
int main(){ 
   
    for(int i = 0;i < 1 << N;i ++){ 
   
        for(int j = 0;j < N;j ++){ 
   
            if((i >> j) & 1)ones[i] ++;
        }
    }
    for(int i = 0;i < N;i ++)Map[1 << i] = i;
    while(cin>>line,line != "end"){ 
   
        for(int i = 0;i < line.size();i ++){ 
   
            int x = i / N,y = i % N;
            g[x][y] = line[i];
        }
        memset(col,0,sizeof col);
        memset(row,0,sizeof row);
        memset(grid,0,sizeof grid);
        sum = 0;
        for(int i = 0;i < N;i ++){ 
   
            col[i] = (1 << N) - 1;
            row[i] = (1 << N) - 1;
            grid[i / 3][i % 3] = (1 << N) - 1;
        }
        for(int i = 0;i < N;i ++){ 
   
            for(int j = 0;j < N;j ++){ 
   
                if(g[i][j] != '.'){ 
   
                    int x = g[i][j] - '1';
                    col[j] -= (1 << x);
                    row[i] -= (1 << x);
                    grid[i / 3][j / 3] -= (1 << x);
                }else sum ++;
            }
        }
        dfs(0);
    }
    return 0;
}
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/168664.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • c语言-日期格式化[通俗易懂]

    c语言-日期格式化[通俗易懂]7-12日期格式化(5分)世界上不同国家有不同的写日期的习惯。比如美国人习惯写成“月-日-年”,而中国人习惯写成“年-月-日”。下面请你写个程序,自动把读入的美国格式的日期改写成中国习惯的日期。输入格式:输入在一行中按照“mm-dd-yyyy”的格式给出月、日、年。题目保证给出的日期是1900年元旦至今合法的日期。输出格式:在一行中按照“yyyy-mm-dd”的格式给出年…

  • 指令重排详解_cpu指令重排序

    指令重排详解_cpu指令重排序指令重排:编译器指令重排,cpu指令重排,内存指令重排。编译器可能会调整顺序,如下图,左边是c++源码,右边是优化后顺序一条汇编指令的执行是可以分为很多步骤的,分为不同的硬件执行取指IF译码和取寄存器操作数ID执行或者有效地址计算EX(ALU逻辑计算单元)存储器访问MEM写回WB(寄存器)指令重排只可能发生在毫无关系的指令之间,如果指令之间存在依赖关系,则不会重排。单线程内程序的执行结果不能被改变。1原子性是指一个操作是不可中断的.

    2022年10月17日
  • acwing-361. 观光奶牛(0/1分数规划)「建议收藏」

    acwing-361. 观光奶牛(0/1分数规划)「建议收藏」给定一张 L 个点、P 条边的有向图,每个点都有一个权值 f[i],每条边都有一个权值 t[i]。求图中的一个环,使“环上各点的权值之和”除以“环上各边的权值之和”最大。输出这个最大值。注意:数据保证至少存在一个环。输入格式第一行包含两个整数 L 和 P。接下来 L 行每行一个整数,表示 f[i]。再接下来 P 行,每行三个整数 a,b,t[i],表示点 a 和 b 之间存在一条边,边的权值为 t[i]。输出格式输出一个数表示结果,保留两位小数。数据范围2≤L≤1000,2≤P≤50

  • servlet映射中的<url pattern>[xxxxx]无效[通俗易懂]

    servlet映射中的<url pattern>[xxxxx]无效[通俗易懂]urlpattern格式错误导致tomcat无法启动

    2022年10月26日
  • 爬虫课第一次报错总结

    爬虫课第一次报错总结1importurllib.requesturl=’https://www.baidu.com/s?wd=海贼王’res=urllib.request.urlopen(url)UnicodeEncodeError:‘ascii’codeccan’tencodecharactersinposition10-12:ordinalnotinrange(128)原因:url包含不是ascii的字符处理:把“海贼王”改为%+十六进制(法1:百度,法2urllib.par

  • 反向传播——通俗易懂[通俗易懂]

    反向传播——通俗易懂[通俗易懂]最近在看深度学习的东西,一开始看的吴恩达的UFLDL教程,有中文版就直接看了,后来发现有些地方总是不是很明确,又去看英文版,然后又找了些资料看,才发现,中文版的译者在翻译的时候会对省略的公式推导过程进行补充,但是补充的又是错的,难怪觉得有问题。反向传播法其实是神经网络的基础了,但是很多人在学的时候总是会遇到一些问题,或者看到大篇的公式觉得好像很难就退缩了,其实不难,就是一个链式求导法则反复用。如果…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号