OR70. 数独
描述
数独是一个非常有名的游戏。整个是一个9X9的大宫格，其中又被划分成9个3X3的小宫格。要求在每个小格中放入1-9中的某个数字。要求是：每行、每列、每个小宫格中数字不能重复。 现要求用计算机求解数独。（50分）输入描述
输入9行，每行为空格隔开的9个数字，为0的地方就是需要填充的数字。输出描述
输出九行，每行九个空格隔开的数字，为解出的答案。示例1
输入:
0 9 0 0 0 0 0 6 0 8 0 1 0 0 0 5 0 9 0 5 0 3 0 4 0 7 0 0 0 8 0 7 0 9 0 0 0 0 0 9 0 8 0 0 0 0 0 6 0 2 0 7 0 0 0 8 0 7 0 5 0 4 0 2 0 5 0 0 0 8 0 7 0 6 0 0 0 0 0 9 0
输出:
7 9 3 8 5 1 4 6 2 8 4 1 2 6 7 5 3 9 6 5 2 3 9 4 1 7 8 3 2 8 4 7 6 9 5 1 5 7 4 9 1 8 6 2 3 9 1 6 5 2 3 7 8 4 1 8 9 7 3 5 2 4 6 2 3 5 6 4 9 8 1 7 4 6 7 1 8 2 3 9 5
C++ 解法, 执行用时: 3ms, 内存消耗: 352KB, 提交时间: 2019-04-06
// test.cpp : Defines the entry point for the console application.
//
//#define DEBUG
#ifdef DEBUG
#else
#include <bits/stdc++.h>
using namespace std;
#define vi vector<int>
#define si set<int>
#define pii pair<int,int>
#define piii pair<int, pii>
#define piiii pair<int, piii>
#define umii unordered_map<int,int>
#define lowbit(t) t&(-t)
#define x first
#define y second
#define sqr(x) ((x) * (x))
#define eps 1e-9
#define m_init(arr, val) memset(arr, val, sizeof arr)
#define all(x) x.begin(),x.end()
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define SZ(x) int(x.size())
#define pi acos(-1)
#define mod 1000000007
#define MOD 1000000009
#define INF 0x3f3f3f3f
#define ll long long
#define DBG(x) cerr<<(#x)<<"="<<x<<"\n";
#define bcase break;case
#define bdefault break;default
#define repi(i, a, b) for(int i = (a),i##len=(b); i<i##len; i++)
#define peri(i,a,b) for(int i=(a);i>=(b);i--)
#define repll(i, a, b) for(ll i = a; i<b; i++)
#define has_e(s,e) (s.find(e)!=s.end())
#define ceili(a, b) \
((a)/(b) + ((a)%(b) ? 1 : 0))
template <class U, class T> void Max(U &x, T y) { if (x<y)x = y; }
template <class U, class T> void Min(U &x, T y) { if (x>y)x = y; }
template <class T> void add(int &a, T b) { a = (a + b) % mod; }
int dx[] = {1,0,0,-1,1,1,-1,-1};
int dy[] = {0,1,-1,0,-1,1,-1,1};
ll qmul_mod(ll a, ll b, ll m) {
ll ans = 0LL;
while (b) {
if (b & 1)ans = (ans + a) % m;
a = (a + a) % m, b >>= 1;
}
return ans % m;
}
ll qpow_mod(ll x, ll y, int m) {
ll res=1;
while(y)
{
if(y%2)(res*=x)%=m;
(x*=x)%=m;
y>>=1;
}
return res;
}
const int msize = 15;
struct Matrix {
int m[msize][msize];
Matrix() { memset(m, 0, sizeof m); }
void print() {
repi(i,0,msize) {
repi(j,0,msize) {
printf("%d%c", m[i][j], " \n"[j==msize-1]);
}
}
puts("");
}
void Unit() { repi(i, 0, msize) m[i][i] = 1; }
};
inline Matrix operator * (Matrix a, Matrix b) {
Matrix res;
repi(i, 0, msize)
repi(k, 0, msize)
if (a.m[i][k])
repi(j, 0, msize)
(res.m[i][j] += 1LL * a.m[i][k] * b.m[k][j] % mod) %= mod;
return res;
}
Matrix qmat_pow(Matrix a, int n) {
Matrix res;
res.Unit();
while (n)
{
if (n & 1) {
res = res * a;
}
n >>= 1;
a = a * a;
}
return res;
}
template <class T>
inline T lcm(T x,T y)
{
T a, b, c;
a = x;
b = y;
c = x%y;
while(c!=0)
{
x = y;
y = c;
c = x%y;
}
return a*b/y;
}
template <class T>
inline T gcd(T __m, T __n)
{
while (__n != 0)
{
T __t = __m % __n;
__m = __n;
__n = __t;
}
return __m;
}
#define N 8005
//ll f[N], inv[N];
//
//ll Combination(int a, int b) {
// return b > a ? 0 : 1LL * f[a] * inv[b] % mod*inv[a - b] % mod;
//}
//
//void C_init() {
// f[0] = 1;
// repi(i, 1, N) {
// f[i] = 1LL * i* f[i - 1] % mod;
// }
// inv[N - 1] = qpow_mod(f[N - 1], mod - 2, mod);
// peri(i, N - 2, 0) {
// inv[i] = 1LL * (i + 1)*inv[i + 1] % mod;
// }
//}
//int prime[N];
//bool vis[N];
//int cnt = 0;
//
//void sift_prime() {
// vis[0]=vis[1]=1;
// repi(i,2,N) {
// if(!vis[i]) {
// prime[cnt++] = i;
// }
// for(int j = 0; j<cnt && i*prime[j] < N; j++) {
// vis[prime[j]*i] = 1;
// if(i%prime[j]==0)break;
// }
// }
//}
int T = 1;
int n, m, k;
int A[N];
struct node {
int val;
}tree[N<<3];
void down(int p,int L,int R) {
if (tree[p].val!=-1) {
tree[p<<1].val = tree[p<<1|1].val = tree[p].val;
tree[p].val = -1;
}
}
//void up(int p,int L,int R) {
//// lsum[p] = lsum[p << 1];
//// rsum[p] = rsum[p << 1 | 1];
//// int mid = (L + R) >> 1;
//// if (lsum[p] == md - L + 1) {
//// lsum[p] += lsum[p << 1 | 1];
//// }
//// if (rsum[p] == R - md) {
//// rsum[p] += rsum[p << 1];
//// }
// if(L>R)
// return;
// tree[p].mmax = max(tree[p<<1].mmax, tree[p<<1|1].mmax);
// tree[p].max = max(min(tree[p<<1].mmax, tree[p<<1|1].mmax), max(tree[p<<1].max, tree[p<<1|1].max));
//}
void build(int p, int L, int R) {
tree[p].val = -1;
if (L == R) {
return;
}
int mid = (L + R) >> 1;
build(p << 1, L, mid);
build(p << 1 | 1, mid + 1, R);
}
//void upd(int p, int pos, int L, int R, int v) {
// if (L == R) {
// tree[p].mmax = v;
// tree[p].max = -1;
// return;
// }
//// down(p, L, R);
// int mid = (L + R) >> 1;
// if (pos <= mid)
// upd(p << 1, pos, L, mid, v);
// if (pos > mid)
// upd(p << 1 | 1, pos, mid + 1, R, v);
// up(p,L,R);
//}
void upd(int p, int l, int r, int L, int R, int v) {
if (l <= L && R <= r) {
tree[p].val = v;
return;
}
down(p, L, R);
int mid = (L + R) >> 1;
if (l <= mid)
upd(p << 1, l, r, L, mid, v);
if (r > mid)
upd(p << 1 | 1, l, r, mid + 1, R, v);
// up(p,L,R);
}
void query(int p, int l, int r, int L, int R, int v) {
if (tree[p].val != -1) {
printf("%d %d\n", tree[p].val, v);
// vis[v][tree[p].val] = 1;
return;
}
if(L==R)
return;
// down(p,L,R);
int mid = (L + R) >> 1;
if (l <= mid) {
query(p << 1, l, r, L, mid, v);
}
if (r > mid) {
query(p << 1 | 1, l, r, mid + 1, R, v);
}
}
//int num[10005];
//
//int qry(int pos) {
// int ans = 0;
// while (pos>0) {
// ans += num[pos];
// pos -= lowbit(pos);
// }
// return ans;
//}
//
//void upd(int pos, int val) {
// while (pos<=n) {
// num[pos]+=val;
// pos+=lowbit(pos);
// }
//}
//int prime[1005], sift[1005];
//
//void sift_prime(int num) {
// sift[1]=1;
// repi(i,2,num+1) {
// if(!sift[i]) {
// prime[k++] = i;
// }
// for(int j=0; j<k && i*prime[j]<=num; j++) {
// sift[i*prime[j]] = 1;
// if (i%prime[j] == 0)
// break;
// }
// }
//}
int str[10][10];
int space = 0;
pii spaces[81];
bool solve(int id) {
if (id == space) {
return 1;
}
int x = spaces[id].x, y = spaces[id].y;
bool vis[10];
m_init(vis,0);
repi(i,0,9) {
vis[str[x][i]] = 1;
vis[str[i][y]] = 1;
}
int stx = x-x%3, sty = y - y%3;
repi(i,stx,stx+3) {
repi(j,sty, sty+3) {
vis[str[i][j]] = 1;
}
}
repi(i,1,10) {
if (!vis[i]) {
str[x][y] = i;
if (solve(id+1)) {
return 1;
}
str[x][y] = 0;
}
}
return 0;
}
int main()
{
srand(time(NULL)+clock());
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
// freopen("out1.txt", "w", stdout);
#endif
// scanf("%d", &T);
// C_init();
while (T--)
// while (~scanf("%d", &n))
// repi(c,1,T+1)
{
repi(i,0,9) {
repi(j,0,9) {
scanf("%d", str[i]+j);
if (str[i][j] == 0) {
spaces[space].x = i;
spaces[space].y = j;
space++;
}
}
}
solve(0);
repi(i,0,9) {
repi(j,0,9) {
printf("%d%c", str[i][j], " \n"[j==8]);
}
}
}
#ifndef ONLINE_JUDGE
fclose(stdin);
// fclose(stdout);
#endif
return 0;
}
#endif
C++ 解法, 执行用时: 3ms, 内存消耗: 356KB, 提交时间: 2020-03-09
#include <bits/stdc++.h>
int rnumb[9][9];
int temp[9][9];
int col[9][10];
int row[9][10];
int gongge[9][10];
void shudu(int n)
{
if(n==81)
{
for(int i=0;i<9;i++)
for(int j=0;j<9;j++)
temp[i][j]=rnumb[i][j];
return;
}
int x=n/9,y=n%9;
if(rnumb[x][y]==0)
{
for(int i=1;i<=9;i++)
{
if(row[x][i]!=1&&col[y][i]!=1&&gongge[x/3*3+y/3][i]!=1)
{
row[x][i]=1;
col[y][i]=1;
gongge[x/3*3+y/3][i]=1;
rnumb[x][y]=i;
shudu(n+1);
row[x][i]=0;
col[y][i]=0;
gongge[x/3*3+y/3][i]=0;
rnumb[x][y]=0;
}
}
}
else
shudu(n+1);
}
int main()
{
int cn;
memset(col,0,sizeof(col));
memset(row,0,sizeof(row));
memset(gongge,0,sizeof(gongge));
for(int i=0;i<9;i++)
for(int j=0;j<9;j++)
{
std::cin>>cn;
rnumb[i][j]=cn;
if(cn!=0)
{
row[i][cn]=1;
col[j][cn]=1;
gongge[i/3*3+j/3][cn]=1;
}
}
shudu(0);
for(int i=0;i<9;i++)
{
int j;
for(j=0;j<8;j++)
std::cout<<temp[i][j]<<" ";
std::cout<<temp[i][j]<<std::endl;
}
}