数独口诀_数独技巧xwing推导过程

数独口诀_数独技巧xwing推导过程数独是一种传统益智游戏,你需要把一个 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/168847.html原文链接:https://javaforall.cn

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

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

(0)


相关推荐

  • LASSO回归与L1正则化 西瓜书「建议收藏」

    1.结构风险与经验风险在支持向量机部分,我们接触到松弛变量,正则化因子以及最优化函数,在朴素贝叶斯分类,决策树我们也遇到类似的函数优化问题。其实这就是结构风险和经验风险两种模型选择策略,经验风险负责最小化误差,使得模型尽可能的拟合数据,而结构风险则负责规则化参数,使得参数的形式尽量简洁,从而达到防止过拟合的作用.所以针对常见模型,我们都有下式:                           …

  • use ida6.8 + windbg on win10[通俗易懂]

    use ida6.8 + windbg on win10[通俗易懂]序用ida6.8pro+windbgx64调试x64的pip.exe,说找不到windbg.我已经装了一个从csdn下载的windbgx64-v6.x.找资料,说要修改ida.cfg,添加IDA环境变量DBGTOOLS为x86版的windbg路径。尝试在dbg_windbg.cfg中添加DBGTOOLS,IDA启动时说在dbg_windbg.cfg中的DBGTOOLS环境

  • java如何实现封装_java如何实现封装

    java如何实现封装_java如何实现封装Java中类的封装是如何实现的封装是将对象的信息隐藏在对象内部,禁止外部程序直接访问对象内部的属性和方法。java封装类通过三个步骤实现:(1)修改属性的可见性,限制访问。(2)设置属性的读取方法。(3)在读取属性的方法中,添加对属性读取的限制。Java中什么叫封装呢?继承和多态都明白些,就是封装理解不上去,老师没关于这个问题,我想举一个例子:lz如果你接触过老的面向过程的编程,以前…

  • Wi-Fi曝安全漏洞 面临KRACK攻击风险

    Wi-Fi曝安全漏洞 面临KRACK攻击风险近日,WPA2被曝存在严重安全漏洞。WPA2在2004年发布,自2006年3月起已经成为一种强制性的标准,是目前使用范围最广的Wi-Fi网络保护协议。何为KRACK攻击?在回答这个问题之前,让我们快速普及一些Crypto101课程的内容。高级加密标准(AES)已经采用了十几年。它是一种对称密钥密码,即使用相同的密钥来加密和解密。虽然传统上标准的AE…

  • uva 11151 Longest Palindrome (最长公共子序列)[通俗易懂]

    uva 11151 Longest Palindrome (最长公共子序列)[通俗易懂]uva11151LongestPalindromeApalindromeisastringthatreadsthesamefromtheleftasitdoesfromtheright.Forexample,I,GAGandMADAMarepalindromes,butADAMisnot.Here,weconsideralso

  • java中sql如何嵌套查找_SQL 查询嵌套使用[通俗易懂]

    java中sql如何嵌套查找_SQL 查询嵌套使用[通俗易懂]示例表如下:createtableit_student(idintprimarykeyauto_increment,–主键idnamevarchar(20),–姓名genderenum(‘male’,’female’),–性别class_idtinyintunsigned,–班级号ageintunsigned,–年龄homevar…

发表回复

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

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