两个题都是数独，题意很明确。
建图的思路大神写的很好：
行：一共9 * 9 * 9 == 729行。一共9 * 9小格，每一格有9种可能性(1 - 9)， 每一种可能都对应着一行。
列：一共(9 + 9 + 9) * 9 + 81 == 324 种前面三个9分别代表着9行9列和9小 块。乘以9的意思是9种可能，因为每种可能只可以选择一个。81代表着81个 小格，限制着每一个小格只可以放一个地方。
我个人的理解是行就是所有的可能，列就是限制条件，这里就是列
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <queue>
#include <stack>
#include <vector>
#include <set>
#include <string>
using namespace std;
#define For(i,a) for(i=0;i<a;i++)
#define Foru(i,a,b) for(i=a;i<=b;i++)
#define Ford(i,a,b) for(i=a;i>=b;i--)
#define clr(ar,vel) memset(ar,vel,sizeof(ar))
#define PB push_back
#define maxint 0x7fffffff
int ans[300];
string s;
const int maxn = 502011;
const int head = 0;
int size;
int col[maxn];
int row[maxn];
int cell[maxn];
int R[maxn], L[maxn], U[maxn], D[maxn];
int S[maxn], C[maxn], O[maxn], H[maxn], X[maxn];
void remove(const int &c) {
//cout << "remove " << c << endl;
//remove column c and all row i that A[i][c] == 1
L[R[c]] = L[c]; R[L[c]] = R[c];
//remove column c;
for (int i = D[c]; i != c; i = D[i]) {
//remove i that A[i][c] == 1
for (int j = R[i]; j != i; j = R[j]) {
//cout << "remove" << endl;
U[D[j]] = U[j]; D[U[j]] = D[j]; --S[C[j]]; //decrease the count of column C[j];
}
}
}
void resume(const int &c) {
for (int i = U[c]; i != c; i = U[i]) {
for (int j = L[i]; j != i; j = L[j]) {
++S[C[j]];
U[D[j]] = j;
D[U[j]] = j;
}
}
L[R[c]] = c;
R[L[c]] = c;
}
bool dfs(const int &k) {
if (R[head] == head) {
//One of the answers has been found.
//cout << "answer " << k << endl;
for(int i = 0; i < k; i ++){
int num, pos;
num = X[O[i]]/256;
pos = X[O[i]]%256;
s[pos] = num+'A'-1;
//cout << num << ' ' << pos << endl;
}
for(int i = 0; i < 16; i ++) {
for(int j = 0; j < 16; j ++){
cout << s[i*16+j];
}
cout << endl;
}
return true;
}
int s(maxint), c;
for (int t = R[head]; t != head; t = R[t]) {
//select the column c which has the fewest number of element.
if (S[t] < s) {
s = S[t];
c = t;
}
}
//cout << k << endl;
remove(c);
for (int i = D[c]; i != c; i = D[i]) {
O[k] = i;
//record the answer.
for (int j = R[i]; j != i; j = R[j]) {
remove(C[j]);
}
if (dfs(k + 1)) {return true;}
for (int j = L[i]; j != i; j = L[j]) {
resume(C[j]);
}
}
resume(c);
return false;
}
void link(int r,int c)
{
++S[C[size]=c];
D[size]=D[c];
U[D[c]]=size;
U[size]=c;
D[c]=size;
if(H[r]<0)H[r]=L[size]=R[size]=size;
else
{
R[size]=R[H[r]];
L[R[H[r]]]=size;
L[size]=H[r];
R[H[r]]=size;
}
X[size++]=r;
}
void init(int m){
clr(col,0);
clr(row,0);
clr(cell,0);
clr(ans, -1);
clr(H, -1);
for(int i = 0; i <= m; i ++){
S[i] = 0;
R[i] = i+1;
L[i+1] = i;
U[i] = D[i] = i;
}
R[m] = 0;
L[0] = m;
size = m+1;
}
int main(){
int rownum;
int c1, c2, c3, c4;
char str[20];
int flag = 0;
while(~scanf("%s",str)){
if(flag) cout << endl;
flag = 1;
s = str;
for(int i = 1; i < 16; i ++) {
scanf("%s",str);
s+= str;
}
//cout << s << endl;
init(1024);
rownum = 1;
int cnt = 0;
//for(int i = 0; i < 10; i ++) cout << ans[i] << ' ';cout << endl;
for(int i = 1; i <= 16; i ++){
for(int j = 1; j <= 16; j ++){
if(s[cnt] != '-'){
int w = s[cnt] - 'A'+1;
ans[cnt] = w;
// cout << w << endl;
chance(i, j, w, rownum, c1, c2, c3, c4);
link(rownum,c1);
link(rownum,c2);
link(rownum,c3);
link(rownum,c4);
// cout << c1 << ' ' << c2 << ' ' << c3 << ' ' << c4 << endl;
//system("pause");
row[c1] = 1;
col[c2] = 1;
cell[c3] = 1;
}
cnt++;
}
}
//for(int i = 0; i < 10; i ++) cout << ans[i] << ' ';cout << endl;
//for(int i = 0; i < 324; i ++) cout << S[i] << ' ' ;cout << endl;
for(int i = 1; i <= 16; i ++){
for(int j = 1; j <= 16; j ++){
if( ans[i*16-16+j-1] == -1){
for(int w = 1; w <= 16; w ++){
chance(i, j, w, rownum, c1, c2, c3, c4);
if( row[c1] || col[c2] || cell[c3] ) continue;
link(rownum,c1);
link(rownum,c2);
link(rownum,c3);
link(rownum,c4);
// cout << c4 << endl;
}
//rownum++;
}
}
}
dfs(0);
//cout << "answer" << endl;
}
return 0;
}