企业网站备案怎么搞/制作网站要花多少钱

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

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

输入格式

输入包含多组测试用例。

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

每个字符都是一个数字（1-9）或一个”.”（表示尚未填充）。

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

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

输出格式

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

输入样例：

.2738..1..1...6735.......293.5692.8...........6.1745.364.......9518...7..8..6534.
......52..8.4......3...9...5.1...6..2..7........3.....6...1..........7.4.......3.
end

输出样例：

527389416819426735436751829375692184194538267268174593643217958951843672782965341
416837529982465371735129468571298643293746185864351297647913852359682714128574936

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std ;
const int MAX = 1000 ;
const int N = 9 ;
int row[N] ,col[N] ,cell[3][3] ;
int ones[1<<N] ,map[1<<N] ;
char str[500] ;
inline int lowbit(int x ){return x&(-x);
}
void init(){ // 初始化, 一开 始都是可以选的for(int i = 0 ; i<N ;i++) row[i] = col[i] = (1<<N)-1 ;for(int i = 0 ; i<3 ; i++){for(int j = 0 ; j<3 ; j++ ) {cell[i][j] = (1<<N)-1 ;}}
}
// 求可选方案的交集
inline int get(int x ,int y) {return row[x] & col[y] &cell[x/3][y/3] ;
}
bool dfs(int cnt ){if(!cnt) return true ;// 剪枝// 找到可选方案数最少的空geint minv = 10 ; // 最多是 9个1int x ,y ;for(int i = 0 ; i<N ; i++ ) {for(int j = 0 ; j<N ; j++ ) {if(str[i*9+j] == '.') {int t = ones[get(i,j)] ;// 二进制表的数中 , 1 的个数if(t < minv){minv = t ;x = i ;y = j ;}}}}for(int i = get(x,y) ; i;i-=lowbit(i)){int t = map[lowbit(i)] ;// 修改状态row[x] -= 1<<t ;col[y] -= 1<<t ;cell[x/3][y/3] -= 1<<t ;str[x*9+y] = '1'+t ; // 填上 tif(dfs(cnt -1 )) return true ;//恢复现场row[x] += 1<<t ;col[y] += 1<<t ;cell[x/3][y/3] += 1<<t ;str[x*9+y] = '.' ;}return false;
}int main(){for(int i = 0 ; i<N ; i++ )map[1<<i] = i ; // 二进制for(int i = 0 ; i< 1<<N ; i++ ) {int s = 0 ;for(int j = i ; j; j-=lowbit(j)) s++ ;ones[i] = s ; //i 的二进制表示中有 s 个 i}while(cin >> str , str[0] !='e') {init() ; //  其所在行,所在列,所在九宫格都为可选int cnt = 0 ; // 记录还有几个可选空格for(int i = 0 ,k = 0; i<N  ;i++ ) {for(int j = 0 ; j<N ; j++,k++ ){if(str[k] !='.'){int t = str[k] -'1' ;row[i] -=1<<t ; // 第i行 表示的二进制的第 t 位 变为0 ,表示可选col[j] -=1<<t ; //cell[i/3][j/3] -=1<<t;}else cnt++;}}dfs(cnt) ;cout<<str<<endl;}return 0 ;
}