題目大意：
給出一個已經完成的數獨，和一個未完成的數獨。
判斷前者能否經過演化后成為后者的解。演化的操作有：
1）改變數字1～9的映射
2）旋轉數獨
3）交換3x9中的行或列
4）交換兩個3x9
解法：
實際上就是常規的搜索，不過代碼難寫點。
4）中共有6*6種情況
3）中共有(6*6*6)*(6*6*6)種情況
在搜索3）的時候，首先固定列，然后枚舉行，這樣就可以節省一些時間。
我的代碼 250ms
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <cmath>
using namespace std;
int b1[9][9], b2[9][9];
int p3[][3] = {
{0,1,2},
{0,2,1},
{1,0,2},
{1,2,0},
{2,0,1},
{2,1,0}
};
int *colseg, *rowseg;
int *col[3];
int check3(int r, int *m);
int check4(int r, int *p, int *m)
{
int i, j, k, l;
int r1, c1, r2, c2;
int v1, v2;
int m2[10];
memcpy(m2, m, sizeof(int)*10);
for (j = 0; j < 3; j++)
for (k = 0; k < 3; k++)
for (l = 0; l < 3; l++) {
r1 = p[j] + rowseg[r]*3;
c1 = colseg[k]*3 + col[k][l];
r2 = j + r*3;
c2 = k*3 + l;
v1 = b1[r1][c1];
v2 = b2[r2][c2];
if (v2) {
if (!m2[v2])
m2[v2] = v1;
else if (m2[v2] != v1)
return 0;
}
}
return check3(r + 1, m2);
}
int check3(int r, int *m)
{
int i;
if (r == 3)
return 1;
for (i = 0; i < 6; i++)
if (check4(r, p3[i], m))
return 1;
return 0;
}
int check2()
{
int i, j, k;
for (i = 0; i < 6; i++)
for (j = 0; j < 6; j++)
for (k = 0; k < 6; k++) {
int m[10] = {};
col[0] = p3[i];
col[1] = p3[j];
col[2] = p3[k];
if (check3(0, m))
return 1;
}
return 0;
}
int check()
{
int i, j;
for (i = 0; i < 6; i++) {
for (j = 0; j < 6; j++) {
colseg = p3[i];
rowseg = p3[j];
if (check2())
return 1;
}
}
return 0;
}
int solve()
{
int i, j, b[9][9];
if (check())
return 1;
for (i = 0; i < 9; i++)
for (j = 0; j < 9; j++)
b[i][j] = b1[8-j][i];
memcpy(b1, b, sizeof(b));
return check();
}
int main()
{
int T, i;
scanf("%d", &T);
for (; T--; ) {
for (i = 0; i < 81; ++i) scanf(" %1d", b1[i/9]+i%9);
for (i = 0; i < 81; ++i) scanf(" %1d", b2[i/9]+i%9);
printf(solve() ? "Yes\n" : "No\n");
}
return 0;
}
標程 79ms
這個很牛逼，原理還沒搞懂！
/* Sample solution for NWERC'06: Sudoku
* Author: Per Austrin
* Algorithm:
* Fix the position of one 3x3 block at a time, then try all
* permutations within that block and proceed to the next 3x3-block.
* Keep a partial remapping of the digits as we go, and break whenever
* inconsistencies are found.
*/
#include <cstdio>
#include <algorithm>
#include <string.h>
using namespace std;
int b1[9][9], b2[9][9];
int brperm[3], bcperm[3];
int rperm[3][3], cperm[3][3];
bool tryperm(int blockrow, int blockcol, int *digmap) {
if (blockcol == 3) ++blockrow, blockcol = 0;
if (blockrow == 3) return true;
for (int i = 0; i < 3; ++i)
if (blockcol == 0 && brperm[i] == -1 ||
blockcol > 0 && brperm[i] == blockrow)
for (int j = 0; j < 3; ++j)
if (blockrow == 0 && bcperm[j] == -1 ||
blockrow > 0 && bcperm[j] == blockcol) {
int rp[3], cp[3];
brperm[i] = blockrow;
bcperm[j] = blockcol;
for (int k = 0; k < 3; ++k) rp[k] = cp[k] = k;
// Check if any of these permutations have already been fixed.
if (blockrow > 0) memcpy(cp, cperm[blockcol], sizeof(cp));
if (blockcol > 0) memcpy(rp, rperm[blockrow], sizeof(rp));
do {
do {
// Check that row and column permutations for this block
// are consistent with the current remapping of the digits.
bool inconsistent = false;
int ndigmap[10];
memcpy(ndigmap, digmap, sizeof(int)*10);
for (int r = 0; !inconsistent && r < 3; ++r)
for (int c = 0; !inconsistent && c < 3; ++c) {
int v1 = b1[3*blockrow + r][3*blockcol + c];
int v2 = b2[3*i + rp[r]][3*j + cp[c]];
if (v2) {
if (ndigmap[v2] && ndigmap[v2] != v1) inconsistent = true;
ndigmap[v2] = v1;
}
}
memcpy(cperm[blockcol], cp, sizeof(cp));
memcpy(rperm[blockrow], rp, sizeof(rp));
if (!inconsistent &&
tryperm(blockrow, blockcol+1, ndigmap))
return true;
} while (blockrow == 0 && next_permutation(cp, cp+3));
} while (blockcol == 0 && next_permutation(rp, rp+3));
// Restore block permutations
if (blockcol == 0) brperm[i] = -1;
if (blockrow == 0) bcperm[j] = -1;
}
return false;
}
int main(void) {
int T, i;
scanf("%d", &T);
for (; T--; ) {
for (i = 0; i < 81; ++i) scanf(" %1d", b1[i/9]+i%9);
for (i = 0; i < 81; ++i) scanf(" %1d", b2[i/9]+i%9);
// Only need to check rotation by 90 degrees since additional
// rotation by 180 degrees can be achieved by the permutations.
for (i = 0; i < 2; ++i) {
int digmap[10];
int nb2[9][9];
for (int r = 0; r < 9; ++r)
for (int c = 0; c < 9; ++c)
nb2[r][c] = b2[c][8-r];
memcpy(b2, nb2, sizeof(b2));
memset(brperm, -1, sizeof(brperm));
memset(bcperm, -1, sizeof(bcperm));
memset(digmap, 0, sizeof(digmap));
if (tryperm(0, 0, digmap)) {
printf("Yes\n");
break;
}
}
if (i == 2) printf("No\n");
}
return 0;
}