5 条题解

  • 6
    @ 2021-8-7 21:05:12 
    #include <stdio.h>
#include <iostream>
#include <string.h>
using namespace std;
string s;
int a[15][15];
int h[15],l[15],g[15];
int sum[520]; // 存储二进制当中的一的个数 
void init()
{
	for(int i = 0 ; i < 10 ; i++)
		h[i] = l[i] = g[i] = 511;
}
int calc(int i, int j)
{
	return h[i] & l[j] & g[ i/3*3 + j/3 ];
}
bool dfs()
{
	int ans = 10; 
	int x,y;
	for(int i = 0 ; i < 9 ; i++)
		for(int j = 0 ;j < 9 ;j++)
			if(a[i][j] == 0)
			{
				int k = sum[ calc(i,j) ]; // 当前的格子当中可以填写数字的个数 
				if(ans > k)
					ans = k , x = i, y = j;
			}
	if(ans == 10)
		return true;
	int num = calc(x,y);
	for(int i = 0 ; i < 9 ; i++)
	{
		int p = (1<<i);
		if( num & p )
		{
			h[x] -= p;  l[y] -= p;
			g[ x/3*3 + y/3 ] -= p;
			a[x][y] = i+1;
			if(dfs())	
				return true;
			h[x] += p;  l[y] += p;
			g[ x/3*3 + y/3 ] += p;
			a[x][y] = 0;
		}
	}
	return false;
}
int main()
{
	for(int i = 0 ; i < 512 ; i++)
	{
		int j = i;
		while(j)
		{
			j =j - (j&-j); // 寻找二进制当中的最后一个1的位置
			sum[i]++;
		}
	}

	while(cin >> s && s != "end")
	{
		memset(a,0,sizeof a);
		init();
		for(int i = 0 ;i  < 81 ; i++)
		{
			int x;
			if(s[i] == '.') x = 0;
			else x = s[i] - 48;
			a[i/9][i%9] = x;
		}
		for(int i = 0 ; i < 9 ; i++)
		{ 
			for(int j = 0 ;j  < 9 ; j++)
			{
				if(a[i][j] != 0)
				{
					int num = 1 << (a[i][j] - 1);
					h[i] -= num;
					l[j] -= num;
					g[ i/3*3 + j/3 ] -= num;
				}
			}
		}
		dfs();
		for(int i = 0 ; i < 9 ; i++)
			for(int j = 0 ; j < 9 ; j++)
				cout << a[i][j] ;
		cout << endl;
	}
}
    • 3
      @ 2023-7-17 11:17:46 
      #include <bits/stdc++.h>
#define LL long long
using namespace std;
const int N = 1e6 + 10;
const int INF = 0x3f3f3f3f;
int a[15][15];
int c[12],r[12],g[12];
int st[511];
string s;
void init() 
{
	memset(a,0,sizeof(a));
	for (int i=0;i<=9;i++) c[i] = r[i] = g[i] = 511;
}
int find(int x,int y) 
{
	return r[x] & c[y] & g[ x/3*3 + y/3];
}
bool dfs() 
{
	int ans = 10;
	int x,y;
	for (int i=0;i<9;i++) 
	{
		for (int j=0;j<9;j++) 
		{
			if(a[i][j] == 0) 
			{
				int num = st[find(i,j)];
				if(num < ans) ans = num, x = i,y = j;
			}
		}
	}
	if(ans == 10) return true;
	int p = find(x,y);
	for (int i=0;i<9;i++) 
	{
		int num = 1 << i;
		if(num & p) 
		{
			r[x] -= num;
			c[y] -= num;
			g[ x/3*3 + y/3] -= num;
			a[x][y] = i + 1;
			if(dfs()) return true;
			r[x] += num;
			c[y] += num;
			g[ x/3*3 + y/3] += num;
			a[x][y] = 0;
		}
	}
	return false;
}
int main() 
{
	for (int i=0;i<512;i++) 
	{
		int f = i;
		while(f) 
		{
			st[i] ++;
			f -= (f&-f);
		}
	}
	while(cin >> s && s != "end") 
	{
		init();
		for (int i=0;i<81;i++) 
		{
			a[i/9][i%9] = (s[i] == '.' ? 0 : s[i] - 48);
		}
		for (int i=0;i<9;i++) 
		{
			for (int j=0;j<9;j++) 
			{
				if(a[i][j] != 0) 
				{
					int num = 1 << (a[i][j] - 1);
					r[i] -= num;
					c[j] -= num;
					g[i/3*3 + j/3] -= num;
				}
			}
		}
		dfs();
		for (int i=0;i<9;i++) 
		{
			for (int j=0;j<9;j++) 
			{
				cout << a[i][j];
			}
		}
		cout << endl;
	}
	return 0;
}

      ```‸
      • 2
        @ 2023-7-17 11:18:17 
        #include<iostream>
#include<cstdio>
#include<iomanip>
#include<cmath>
#include<bits/stdc++.h>
#include<algorithm>
#include<cstring>
#include<string>
#include<stack>
#include<queue>
#define LL long long
using namespace std;
const int INF=0x3f3f3f3f;
const int N=1e5+10;
string s;
int a[15][15];
int h[15],l[15],g[15];
int sum[520];
void init() {
    for(int i = 0 ; i < 10 ; i++)
        h[i] = l[i] = g[i] = 511;
}
int find(int i, int j) {
    return h[i] & l[j] & g[ i/3*3 + j/3 ];
}
bool dfs() {
    int ans = 10;
    int x,y;
    for(int i = 0 ; i < 9 ; i++)
        for(int j = 0 ; j < 9 ; j++)
            if(a[i][j] == 0) {
                int k = sum[ find(i,j) ];
                if(ans > k)
                    ans = k , x = i, y = j;
            }
    if(ans == 10)
        return true;
    int num = find(x,y);
    for(int i = 0 ; i < 9 ; i++) {
        int p = (1<<i);
        if( num & p ) {
            h[x] -= p;
            l[y] -= p;
            g[ x/3*3 + y/3 ] -= p;
            a[x][y] = i+1;
            if(dfs())
                return true;
            h[x] += p;
            l[y] += p;
            g[ x/3*3 + y/3 ] += p;
            a[x][y] = 0;
        }
    }
    return false;
}
int main() {
    for(int i = 0 ; i < 512 ; i++) {
        int j = i;
        while(j) {
            j =j - (j&-j);
            sum[i]++;
        }
    }

    while(cin >> s && s != "end") {
        memset(a,0,sizeof a);
        init();
        for(int i = 0 ; i  < 81 ; i++) {
            int x;
            if(s[i] == '.') x = 0;
            else x = s[i] - 48;
            a[i/9][i%9] = x;
        }
        for(int i = 0 ; i < 9 ; i++) {
            for(int j = 0 ; j  < 9 ; j++) {
                if(a[i][j] != 0) {
                    int num = 1 << (a[i][j] - 1);
                    h[i] -= num;
                    l[j] -= num;
                    g[ i/3*3 + j/3 ] -= num;
                }
            }
        }
        dfs();
        for(int i = 0 ; i < 9 ; i++)
            for(int j = 0 ; j < 9 ; j++)
                cout << a[i][j] ;
        cout << endl;
    }
}



```
        • 0
          @ 2023-7-17 11:29:24 
          #include<iostream>
#include<cstdio>
#include<iomanip>
#include<cmath>
#include<bits/stdc++.h>
#include<algorithm>
#include<cstring>
#include<string>
#include<stack>
#include<queue>
#define LL long long
using namespace std;
const int INF=0x3f3f3f3f;
const int N=1e5+10;
string s;
int a[15][15];
int h[15],l[15],g[15];
int sum[520];
void init() {
    for(int i = 0 ; i < 10 ; i++)
        h[i] = l[i] = g[i] = 511;
}
int find(int i, int j) {
    return h[i] & l[j] & g[ i/3*3 + j/3 ];
}
bool dfs() {
    int ans = 10;
    int x,y;
    for(int i = 0 ; i < 9 ; i++)
        for(int j = 0 ; j < 9 ; j++)
            if(a[i][j] == 0) {
                int k = sum[ find(i,j) ];
                if(ans > k)
                    ans = k , x = i, y = j;
            }
    if(ans == 10)
        return true;
    int num = find(x,y);
    for(int i = 0 ; i < 9 ; i++) {
        int p = (1<<i);
        if( num & p ) {
            h[x] -= p;
            l[y] -= p;
            g[ x/3*3 + y/3 ] -= p;
            a[x][y] = i+1;
            if(dfs())
                return true;
            h[x] += p;
            l[y] += p;
            g[ x/3*3 + y/3 ] += p;
            a[x][y] = 0;
        }
    }
    return false;
}
int main() {
    for(int i = 0 ; i < 512 ; i++) {
        int j = i;
        while(j) {
            j =j - (j&-j);
            sum[i]++;
        }
    }

    while(cin >> s && s != "end") {
        memset(a,0,sizeof a);
        init();
        for(int i = 0 ; i  < 81 ; i++) {
            int x;
            if(s[i] == '.') x = 0;
            else x = s[i] - 48;
            a[i/9][i%9] = x;
        }
        for(int i = 0 ; i < 9 ; i++) {
            for(int j = 0 ; j  < 9 ; j++) {
                if(a[i][j] != 0) {
                    int num = 1 << (a[i][j] - 1);
                    h[i] -= num;
                    l[j] -= num;
                    g[ i/3*3 + j/3 ] -= num;
                }
            }
        }
        dfs();
        for(int i = 0 ; i < 9 ; i++)
            for(int j = 0 ; j < 9 ; j++)
                cout << a[i][j] ;
        cout << endl;
    }
}
          • 0
            @ 2022-10-18 17:37:57 
            #include <stdio.h>
#include <iostream>
#include <string.h>
using namespace std;
string s;
int a[15][15];
int h[15],l[15],g[15];
int sum[520];
void init()
{
	for(int i = 0 ; i < 10 ; i++)
		h[i] = l[i] = g[i] = 511;
}
int calc(int i, int j)
{
	return h[i] & l[j] & g[ i/3*3 + j/3 ];
}
bool dfs()
{
	int ans = 10; 
	int x,y;
	for(int i = 0 ; i < 9 ; i++)
		for(int j = 0 ;j < 9 ;j++)
			if(a[i][j] == 0)
			{
				int k = sum[ calc(i,j) ]; 
				if(ans > k)
					ans = k , x = i, y = j;
			}
	if(ans == 10)
		return true;
	int num = calc(x,y);
	for(int i = 0 ; i < 9 ; i++)
	{
		int p = (1<<i);
		if( num & p )
		{
			h[x] -= p;  l[y] -= p;
			g[ x/3*3 + y/3 ] -= p;
			a[x][y] = i+1;
			if(dfs())
				return true;
			h[x] += p;  l[y] += p;
			g[ x/3*3 + y/3 ] += p;
			a[x][y] = 0;
		}
	}
	return false;
}
int main()
{
	for(int i = 0 ; i < 512 ; i++)
	{
		int j = i;
		while(j)
		{
			j =j - (j&-j); 
			sum[i]++;
		}
	}

	while(cin >> s && s != "end")
	{
		memset(a,0,sizeof a);
		init();
		for(int i = 0 ;i  < 81 ; i++)
		{
			int x;
			if(s[i] == '.') x = 0;
			else x = s[i] - 48;
			a[i/9][i%9] = x;
		}
		for(int i = 0 ; i < 9 ; i++)
		{ 
			for(int j = 0 ;j  < 9 ; j++)
			{
				if(a[i][j] != 0)
				{
					int num = 1 << (a[i][j] - 1);
					h[i] -= num;
					l[j] -= num;
					g[ i/3*3 + j/3 ] -= num;
				}
			}
		}
		dfs();
		for(int i = 0 ; i < 9 ; i++)
			for(int j = 0 ; j < 9 ; j++)
				cout << a[i][j] ;
		cout << endl;
	}
}
            • 1

            数独

            信息

            ID
            77
            时间
            1000ms
            内存
            128MiB
            难度
            5
            标签
            递交数
            264
            已通过
            98
            上传者
            1. 关于
            2. 联系我们
            3. 隐私
            4. 服务条款
            5. 版权申诉
            6. Language
            7. Theme
            3. Worker 0 in 21ms
            4. Powered by Hydro v3.15.13 Community