POJ Sudoku(数独) 2676 2918 3074 3076
Description
填补数独空白处
Analyze
对于2676 和 2918 两题来说，不需要复杂的剪枝，普通DFS即可过
Code
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
int ans[12][12];
string s[12];
bool flag;
bool check (int x, int y, int num)
{
for(int i = 1; i <= 9; ++i)
if(ans[x][i] == num || ans[i][y] == num)
return 0;
int base_x = (x - 1) / 3 * 3;
int base_y = (y - 1) / 3 * 3;
int xx = x % 3, yy = y % 3;
int cx = (xx + 1) % 3;
int dx = (xx + 2) % 3;
int cy = (yy + 1) % 3;
int dy = (yy + 2) % 3;
if(!cx)
cx = 3;
if(!dx)
dx = 3;
if(!cy)
cy = 3;
if(!dy)
dy = 3;
if(ans[base_x + cx][base_y + cy] == num
|| ans[base_x + cx][base_y + dy] == num
|| ans[base_x + dx][base_y + cy] == num
|| ans[base_x + dx][base_y + dy] == num)
return 0;
return 1;
}
void DFS(int x, int y)
{
if(x == 10)
{
flag = 1;
return ;
}
if(flag)
return ;
if(y > 9)
DFS(x + 1, 1);//每次DFS完测一次flag:任意一次退出都可能是完成任务
if(flag)
return ;
if(ans[x][y])
DFS(x, y + 1);
else//原先没把这个for放在else里
{
for(int i = 1; i <= 9; ++i)
if(check(x, y, i))
{
ans[x][y] = i;
DFS(x, y + 1);
if(flag)
return ;
ans[x][y] = 0;
}
}
if(flag)
return ;
}
int main()
{
int _;
scanf("%d", &_);
while(_--)
{
flag = 0;
for(int i = 0; i < 9; ++i)
cin >> s[i];
for(int i = 1; i <= 9; ++i)
for(int j = 1; j <= 9; ++j)
ans[i][j] = s[i - 1][j - 1] - '0';
DFS(1, 1);
for(int i = 1; i <= 9; ++i)
{
for(int j = 1; j <= 9; ++j)
cout << ans[i][j];
cout << '\n';
}
}
return 0;
}
对于3074（数据强一些）
如果发现某行、某列、某九宫格可填的数字比较少，那么优先处理他们
可关键在于如何标记某行(或某列、某九宫格)有哪些可填数字呢？
可填数字总共9个，我们可以想到使用二进制进行状态压缩
用一个十进制数字的二进制形态的1/0位代表可填否
Code
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int INF = 0x3f3f3f3f;
char a[120];
char b[12][12];
int tot;//空的个数
int row[12];//第i行可填的数字(二进制状态压缩为一个十进制的int)
int col[12];
int room[12];
int cnt[520];
int num[520];
int get_room(int x, int y)
{
return (x - 1) / 3 * 3 + (y - 1) / 3 + 1;
/* 1 4 7
2 5 8
3 6 9 */
}
//某个数字的存在引起该行该列该九宫格不可再填该数字
void flip(int x, int y, int z)
{
row[x] ^= (1 << z);
col[y] ^= (1 << z);
room[get_room(x, y)] ^= (1 << z);
}
void init()
{
//(1 << 9) - 1 == 2 ^ 10 - 1 == 11111111(二进制)
//默认9个数字皆可填
for(int i = 1; i <= 9; ++i)
row[i] = col[i] = room[i] = (1 << 9) - 1;
tot = 0;
for(int i = 1; i <= 9; ++i)
for(int j = 1; j <= 9; ++j)
{
b[i][j] = a[ (i - 1) * 9 + j - 1 ];
if(b[i][j] != '.')
flip(i, j, b[i][j] - '1');
else
tot++;
}
}
bool DFS(int tot)
{
if(tot == 0)
return 1;
int mmin = INF, x, y;
for(int i = 1; i <= 9; ++i)
for(int j = 1 ;j <= 9; ++j)
{
if(b[i][j] != '.')
continue;
int val = row[i] & col[j] & room[get_room(i, j)];
if(val == 0)//当前格子可填数字的个数为0
return 0;
if(cnt[val] < mmin)
{
x = i, y = j;//这个格子可填数字的个数最少
mmin = cnt[val];//可填数字的个数
}
}
int val = row[x] & col[y] & room[get_room(x, y)];
for(; val; val -= (val & -val))//之前那种方法不太行了....
{
int tem = num[val & -val];
b[x][y] = tem + '1';
flip(x, y, tem);
if(DFS(tot - 1))
return 1;
flip(x, y, tem);//消除影响
b[x][y] = '.';
}
return 0;
}
// (i & -i) == 2 ^ p (p为i的最低位1所在位)
int main()
{
//十进制数字i转为二进制时含数字1的个数(对应可填数字个数)
for(int i = 0; i < (1 << 9); ++i)
for(int j = i; j; j >>= 1)
if(j & 1)
cnt[i]++;
for(int i = 0; i <= 9; ++i)//打表2的整数幂
num[1 << i] = i;
while(scanf("%s", a))
{
if(a[0] == 'e')
break;
init();
DFS(tot);
for(int i = 1; i <= 9; ++i)
for(int j = 1; j <= 9; ++j)
cout << b[i][j];
cout << '\n';
}
return 0;
}
由于DFS不是本体正解，900ms卡过，而且是交C++过，交G++就超时
对于3076：剪枝情况多而易漏
DFS：
①遍历所有格子：处理空白格子
(1)未填空格出错：虽是空白格子，已无可填数字——return 0；
(2)唯一数字可填：某个空白格子(受所在行列宫的影响)只能填一个数字——填上
②遍历所有行：每行遍历所有数字[1, 16]
(1)已填数字出错：某一数字在一行上出现了不止一次——return 0；
(2)唯一空格可填：这一行上好多空格，某个数字只能填那一个特定的
③遍历所有列（同②）
④遍历所有宫（同②）
⑤从情况少的地方入手（这里的数据备份特重要）
Code
#include <ctime>
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int INF = 0x3f3f3f3f;
#define ll long long
char b[20][20];
int tot;///空的个数
int row[20];///第i行可填的数字(二进制状态压缩为一个十进制的int)
int b_row[20];///第i行剩余的空位
int col[20];
int b_col[20];
int room[20];
int b_room[20];
int cnt[65540];
int num[65540];
/* 1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16 */
int get_room(int x, int y)
{
return (x - 1) / 4 * 4 + (y - 1) / 4 + 1;
}
int get_b_room(int x, int y)
{
int xx = x % 4, yy = y % 4;
if(xx == 0)
xx = 4;
if(yy == 0)
yy = 4;
return 4 * (xx - 1) + yy;
}
int get_one(int tem)
{
int ans = 0;
while(tem)
{
if(tem & 1)
ans++;
tem >>= 1;
}
return ans;
}
///某个数字的存在:
///①引起该行、该列、该九宫格不可再填该数字
///②该行对应列、该列对应行、该九宫格对应格成为已填格
void flip(int x, int y, int z)
{
///x行、y列、该九宫格：不能再填第z位代表的字符了 z∈[0, 15]
row[x] ^= (1 << z);
col[y] ^= (1 << z);
room[get_room(x, y)] ^= (1 << z);
// cout << "Check flip : " << x << ' ' << y << ' ' << z << '\n';
// cout << get_room(x, y) << ' ' << get_b_room(x, y) << '\n' << '\n';
b_row[x] ^= (1 << (y - 1));///x行的第y列已填好数字
b_col[y] ^= (1 << (x - 1));///y列的第x行已填好数字
b_room[get_room(x, y)] ^= (1 << (get_b_room(x, y) - 1));///该九宫格的对应格已填好数字
///将[1, 16]转为[0, 15]
}
//void rev(int i, int ID, int & x, int & y)
//{
// int rx = (ID - 1) / 4 + 1;
// int ry = ID - 4 * (rx - 1);
// int xx = (i - 1) / 4 + 1;
// int yy = i - 4 * (xx - 1);
// x = 4 * (xx - 1) + rx;
// y = 4 * (yy - 1) + ry;
//}
void init()
{
tot = 256;
///这16位是从0位开始用的
///(1 << 16) - 1 == 2 ^ 16 - 1 == 1111 1111 1111 1111 (二进制)
///默认16个数字皆可填(1可填0不可填),16个空位均未填(1待填，0已填)
for(int i = 1; i <= 16; ++i)
b_row[i] = b_col[i] = b_room[i] = row[i] = col[i] = room[i] = (1 << 16) - 1;
for(int i = 1; i <= 16; ++i)
for(int j = 1; j <= 16; ++j)
if(b[i][j] != '-')
{
tot--;
flip(i, j, b[i][j] - 'A');/// [0, 15] 代表 [A, P]
}
}
bool DFS(int tot)
{
if(tot == 0)
return 1;
// print();
//遍历所有格子：处理空白格
//出现矛盾：及时止损
//唯一可选：及时填上
for(int i = 1; i <= 16; ++i)
for(int j = 1; j <= 16; ++j)
if(b[i][j] == '-')
{
int val = row[i] & col[j] & room[get_room(i, j)];
if(!val)//空白格没有可填数字
return 0;
if(get_one(val) == 1)//空白格有唯一可填数字
{
int tem = num[val & -val];//[0, 15]
b[i][j] = tem + 'A';
flip(i, j, tem);
tot--;
}
}
//遍历所有行：对于每行遍历所有数字
for(int i = 1; i <= 16; ++i)
for(int k = 1; k <= 16; ++k)
{
int k_num = 0, choice = 0, tem_y;
for(int j = 1; j <= 16; ++j)
{
int val = row[i] & col[j] & room[get_room(i, j)];
if(b[i][j] == (k - 1) + 'A')
k_num++;
if(k_num == 2)//某行出现两次k
return 0;
if(b[i][j] == '-' && val & (1 << (k - 1)))//能填k的空白格
choice++, tem_y = j;
}
if(k_num == 0 && choice == 0)//k在这行未出现过，但没有能填k的空白格
return 0;
if(k_num == 0 && choice == 1)//数字 对 不唯一空白格 的 唯一可选(多个空白格，只能填在那个上)
{
b[i][tem_y] = (k - 1) + 'A';
flip(i, tem_y, k - 1);
tot--;
}
}
for(int j = 1; j <= 16; ++j)
for(int k = 1; k <= 16; ++k)
{
int k_num = 0, choice = 0, tem_x = 0;
for(int i = 1; i <= 16; ++i)
{
int val = row[i] & col[j] & room[get_room(i, j)];
if(b[i][j] == (k - 1) + 'A')
k_num++;
if(k_num == 2)
return 0;
if(b[i][j] == '-' && val & (1 << (k - 1)))
choice++, tem_x = i;
}
if(k_num == 0 && choice == 0)
return 0;
if(k_num == 0 && choice == 1)
{
b[tem_x][j] = (k - 1) + 'A';
flip(tem_x, j, k - 1);
tot--;
}
}
for(int i = 1; i <= 16; ++i)
{
int x = (i + 3) / 4, y = i - (x - 1) * 4;
for(int k = 1; k <= 16; ++k)
{
int k_num = 0, choice = 0, tem_x, tem_y;
for(int ii = (x - 1) * 4 + 1; ii <= 4 * x; ++ii)
for(int jj = (y - 1) * 4 + 1; jj <= 4 * y; ++jj)
{
int val = row[ii] & col[jj] & room[get_room(ii, jj)];
if(b[ii][jj] == (k - 1) + 'A')
k_num++;
if(k_num == 2)
return 0;
if(b[ii][jj] == '-' && val & (1 << (k - 1)))
choice++, tem_x = ii, tem_y = jj;
}
if(k_num == 0 && choice == 0)
return 0;
if(k_num == 0 && choice == 1)
{
b[tem_x][tem_y] = (k - 1) + 'A';
flip(tem_x, tem_y, (k - 1));
tot--;
}
}
}
if(tot == 0)
return 1;
///(优先处理)优先选择候选数字少的格子填数字更高效
int mmin = INF, x, y;
for(int i = 1; i <= 16; ++i)
for(int j = 1 ; j <= 16; ++j)
{
if(b[i][j] != '-')
continue;
int val = row[i] & col[j] & room[get_room(i, j)];
if(val == 0)///当前格子可填数字的个数为0
return 0;
if(cnt[val] < mmin)
{
x = i, y = j;///这个格子可填数字的个数最少
mmin = cnt[val];///可填数字的个数
}
}
int t_b[20][20], t_row[20], t_col[20], t_room[20];
memcpy(t_b, b, sizeof(b));
memcpy(t_row, row, sizeof(row));
memcpy(t_col, col, sizeof(col));
memcpy(t_room, room, sizeof(room));
int t_tot = tot;
int val = row[x] & col[y] & room[get_room(x, y)];
for(; val; val -= (val & -val))///之前那种方法不太行了....
{
int tem = num[val & -val];
b[x][y] = tem + 'A';
flip(x, y, tem);
if(DFS(tot - 1))
return 1;
else///原来这儿有猫腻儿
{
memcpy(b, t_b, sizeof(t_b));
memcpy(row, t_row, sizeof(t_row));
memcpy(col, t_col, sizeof(t_col));
memcpy(room, t_room, sizeof(t_room));
tot = t_tot;
}
}
return 0;
}
/// (i & -i) == 2 ^ p (p为i的最低位1所在位)
int main()
{
///十进制数字i转为二进制时含数字1的个数(对应可填数字个数)
for(int i = 0; i < (1 << 16); ++i)
for(int j = i; j; j >>= 1)
if(j & 1)
cnt[i]++;
for(int i = 0; i <= 16; ++i)///打表2的整数幂
num[1 << i] = i;
while(~scanf("%s", b[1] + 1))
{
for(int i = 2; i <= 16; ++i)
scanf("%s", b[i] + 1);
init();
DFS(tot);
for(int i = 1; i <= 16; ++i)
{
for(int j = 1; j <= 16; ++j)
cout << b[i][j];
cout << '\n';
}
cout << '\n';
}
return 0;
}
Code(Other ‘s)
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
#define LL long long
#define mem(a, b) memset(a, b, sizeof(a))
//head
const int N = 17;
int mp[N][N];///字符[A,P]转数字[1,16]
int st[N][N];///禁用标记
int sum = 0;///已填
char s[N][N+5];///原图
void add(int x, int y, int t)
{
mp[x][y] = t;
sum++;
for (int i = 1; i <= 16; i++)
{
///t - 1 : 依然是从0开始
/// 或 | 1 强，多次| 本1还是1：表示该位置不可放t了
st[i][y] |= 1<<t-1;///同列不可放t
st[x][i] |= 1<<t-1;///同行不可放t
}
int xx = (x+3)/4, yy = (y+3)/4;
for (int i = (xx-1)*4 + 1; i <= xx*4; i++)
for (int j = (yy-1)*4 + 1; j <= yy*4; j++)
st[i][j] |= 1<<t-1;///同16宫格不可放t
}
void print()
{
for (int i = 1; i <= 16; i++)
{
for (int j = 1; j <= 16; j++)
putchar(mp[i][j]-1+'A');
puts("");
}
puts("");
}
///两种剪枝：
///①格子有唯一可填的数字
///②数字有唯一可填的格子
///②有时候一个空白格看起来有好多数字可填(其所在行列宫并不满)，但某个数字(比如1)以外的数字(2~16)分别出现在了他所在的行列宫，那这一个格只能填该数字
bool dfs()
{
if(sum == 256)
{
print();
return true;
}
cout << "Check tot : " << 256 - sum << "---------------" << '\n';
///遍历每个格子:检测所有的"未填空格"
///有矛盾：及时返回
///只能填一个数字：及时填上
print();
for (int i = 1; i <= 16; i++)
for (int j = 1; j <= 16; j++)
if(!mp[i][j])
{
int cnt = 0, t = 0;
for (int k = 1; k <= 16; k++)
if((st[i][j] & (1<<k-1)) == 0)///与& 0强,可行方案: k -> st[i][j]
{
cnt++;
t = k;
if(cnt == 2)
break;
}
///①未填空格出错：虽是空格，无可填数字
if(!cnt)///当前格子虽然是空的，但是不能填数字了!(很明显没有兼顾行、列、16格)例如：这一格所在行其他数字都填了只剩4，但这一格所在16宫格有4了
return false;
if(cnt == 1)///唯一可填(是由st[i][j]决定的，而st数组本身就是综合了行列宫，所以此处填上此数字是"当前方案性"正确的)
{
add(i, j, t);
cout << "ADD 1 : ------------------\n";
cout << "add : " << i << ' ' << j << ' ' << t << '\n';
// print();
}
///真就填上了???!!!这层DFS尝试方案有误怎么办?全局的mp数组不能恢复到原样啊!!
}
///遍历每一行(这一行有好多空白格，但某个数字只有一个可填格子)
for (int i = 1; i <= 16; i++)
for (int k = 1; k <= 16; k++)///遍历16个数字
{
int cnt1 = 0, cnt2 = 0, y;
for (int j = 1; j <= 16; j++)///某一行上对应的16个格子
{
if(mp[i][j] == k)
cnt1++;
///②已填数字出错：某行出现同一个数字两次(没有兼顾行列宫)例如：某格子根据所在列性质填了数字4，同行的一个格子根据他的所在列性质也填了数字4
if(cnt1 == 2)
return false;
if(!mp[i][j] && (st[i][j] & (1<<k-1)) == 0)///找到了空白格的可填数字k
cnt2++, y = j;
}
if(!cnt1 && !cnt2)///数字k在这一行没有出现过 同时 (没有空白格 或 空白格无可填数字)
return false;
if(!cnt1 && cnt2 == 1)///数字k在这一行没有出现过 同时 (此行唯一空白格mp[i][y]有唯一可填数字k)
{
add(i, y, k);///唯一可填（只考虑本行决定的,也"是当前方案性"正确）
cout << "ADD 2 : ------------------\n";
cout << "add : " << i << ' ' << y << ' ' << k << '\n';
// print();
}
}
///遍历每一列
for (int j = 1; j <= 16; j++)
for (int k = 1; k <= 16; k++)
{
int cnt1 = 0, cnt2 = 0, x;
for (int i = 1; i <= 16; i++)
{
if(mp[i][j] == k)
cnt1++;
if(cnt1 == 2)
return false;
if(!mp[i][j] && (st[i][j] & (1<<k-1)) == 0)
cnt2++, x = i;
}
if(!cnt1 && !cnt2)
return false;
if(!cnt1 && cnt2 == 1)
{
add(x, j, k);
cout << "ADD 3 : --------------------- \n";
cout << "add : " << x << ' ' << j << ' ' << k << '\n';
// print();
}
}
///遍历每一个16宫格
for (int i = 1; i <= 16; i++)
{
int x = (i+3)/4, y = i - (x-1)*4;
for (int k = 1; k <= 16; k++)
{
int cnt1 = 0, cnt2 = 0, xx, yy;
for (int ii = (x-1)*4+1; ii <= x*4; ii++)
for (int jj = (y-1)*4+1; jj <= y*4; jj++)
{
if(mp[ii][jj] == k)
cnt1++;
if(cnt1 == 2)
return false;
if(!mp[ii][jj] && (st[ii][jj] & (1<<k-1)) == 0)
cnt2++, xx = ii, yy = jj;
}
if(!cnt1 && !cnt2)
return false;
if(!cnt1 && cnt2 == 1)
{
add(xx, yy, k);
cout << "ADD 4 : ------------------\n";
cout << "add : " << xx << ' ' << yy << ' ' << k << '\n';
// print();
}
}
}
if(sum == 256)
{
print();
return true;
}
///选择可填数字最少的空白格尝试填数
///①找到格子
int mn = N, x, y;
for (int i = 1; i <= 16; i++)
for (int j = 1; j <= 16; j++)
if(!mp[i][j])///空白格
{
int cnt = 0;
for (int k = 1; k <= 16; k++)
if((st[i][j] & (1<<k-1)) == 0)
{
cnt++;///该空白格可填数字数目
if(cnt >= mn)
break;
}
if(cnt < mn)
{
mn = cnt;
x = i;
y = j;
}
}
int tst[N][N], tmp[N][N];
memcpy(tst, st, sizeof(st));
memcpy(tmp, mp, sizeof(mp));
int tsum = sum;
///②尝试填数
for (int k = 1; k <= 16; k++)
if((st[x][y] & (1<<k-1)) == 0)
{
add(x, y, k);///之前的唯一性add都是"当前方案"正确的，这里是尝试性add，可能是错的，便用到了上面的"出错剪枝"
bool f = dfs();///唯一的递归口（上面的都执行完了才尝试性递归）
if(!f)
{
///数据还原
cout << "---------------Change---------------\n";
memcpy(st, tst, sizeof(tst));
memcpy(mp, tmp, sizeof(tmp));
sum = tsum;
}
else
return true;
}
return false;
}
int main()
{
while(scanf("%s", s[1]+1) != EOF)
{
for (int i = 2; i <= 16; i++)
scanf("%s", s[i]+1);
sum = 0;
mem(mp, 0);
mem(st, 0);
for (int i = 1; i <= 16; i++)
for (int j = 1; j <= 16; j++)
if(isalpha(s[i][j]))
add(i, j, s[i][j] - 'A' + 1);
dfs();
}
return 0;
}
/*
--A----C-----O-I
-J--A-B-P-CGF-H-
--D--F-I-E----P-
-G-EL-H----M-J--
----E----C--G---
-I--K-GA-B---E-J
D-GP--J-F----A--
-E---C-B--DP--O-
E--F-M--D--L-K-A
-C--------O-I-L-
H-P-C--F-A--B---
---G-OD---J----H
K---J----H-A-P-L
--B--P--E--K--A-
-H--B--K--FI-C--
--F---C--D--H-N-
*/