Problem Description
As if there were not already enough sudoku-like puzzles, the July 2009 issue of Games Magazine describes the following variant that combines facets of both sudoku and dominos. The puzzle is a form of a standard sudoku, in which there is a nine-by-nine grid that must be filled in using only digits 1 through 9. In a successful solution:
Each row must contain each of the digits 1 through 9.
Each column must contain each of the digits 1 through 9.
Each of the indicated three-by-three squares must contain each of the digits 1 through 9.
For a su-domino-ku, nine arbitrary cells are initialized with the numbers 1 to 9. This leaves 72 remaining cells. Those must be filled by making use of the following set of 36 domino tiles. The tile set includes one domino for each possible pair of unique numbers from 1 to 9 (e.g., 1+2, 1+3, 1+4, 1+5, 1+6, 1+7, 1+8, 1+9, 2+3, 2+4, 2+5, ...). Note well that there are not separate 1+2 and 2+1 tiles in the set; the single such domino can be rotated to provide either orientation. Also, note that dominos may cross the boundary of the three-by-three squares (as does the 2+9 domino in our coming example).
To help you out, we will begin each puzzle by identifying the location of some of the dominos. For example, Figure 1 shows a sample puzzle in its initial state. Figure 2 shows the unique way to complete that puzzle.
Input Each puzzle description begins with a line containing an integer N, for 10 ≤ N ≤ 35, representing the number of dominos that are initially placed in the starting configuration. Following that are N lines, each describing a single domino as U LU V LV. Value U is one of the numbers on the domino, and LU is a two-character string representing the location of value U on the board based on the grid system diagrammed in Figure 1. The variables V and LV representing the respective value and location of the other half of the domino. For example, our first sample input beings with a domino described as 6 B2 1 B3. This corresponds to the domino with values 6+1 being placed on the board such that value 6 is in row B, column 2 and value 1 in row B, column 3. The two locations for a given domino will always be neighboring.
After the specification of the N dominos will be a final line that describes the initial locations of the isolated numbers, ordered from 1 to 9, using the same row-column conventions for describing locations on the board. All initial numbers and dominos will be at unique locations.
The input file ends with a line containing 0.
Output For each puzzle, output an initial line identifying the puzzle number, as shown below. Following that, output the 9x9 sudoku board that can be formed with the set of dominos. There will be a unique solution for each puzzle.
Sample Input 10 6 B2 1 B3 2 C4 9 C3 6 D3 8 E3 7 E1 4 F1 8 B7 4 B8 3 F5 2 F6 7 F7 6 F8 5 G4 9 G5 7 I8 8 I9 7 C9 2 B9 C5 A3 D9 I4 A9 E5 A2 C6 I1 11 5 I9 2 H9 6 A5 7 A6 4 B8 6 C8 3 B5 8 B4 3 C3 2 D3 9 D2 8 E2 3 G2 5 H2 1 A2 8 A1 1 H8 3 I8 8 I3 7 I4 4 I6 9 I7 I5 E6 D1 F2 B3 G9 H7 C9 E5 0
Sample Output Puzzle 1 872643195 361975842 549218637 126754983 738169254 495832761 284597316 657381429 913426578 Puzzle 2 814267593 965831247 273945168 392176854 586492371 741358629 137529486 459683712 628714935
数独游戏，把条件转换成约束用dlx搞定
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define rep(i,j,k) for (int i = j; i <= k; i++)
const int maxn = 5e5 + 10;
int n, a, b, tot, X, Y, T = 0;
int r[10][10], c[10][10], d[10][10], f[10][10], mp[10][10];
int p[maxn][6];
char x[3], y[3], s[11][11];
struct DLX
{
int L[maxn], R[maxn], U[maxn], D[maxn];
int row[maxn], col[maxn], ans[maxn], cnt[maxn];
int n, m, num, sz;
void add(int now, int l, int r, int u, int d, int x, int y)
{
L[now] = l; R[now] = r; U[now] = u;
D[now] = d; row[now] = x; col[now] = y;
}
void reset(int n, int m)
{
this->n = n; this->m = m;
for (int i = 0; i <= m; i++)
{
add(i, i - 1, i + 1, i, i, 0, i);
cnt[i] = 0;
}
L[0] = m; num = R[m] = 0; sz = m + 1;
}
void insert(int x, int y)
{
int ft = sz - 1;
if (row[ft] != x)
{
add(sz, sz, sz, U[y], y, x, y);
U[D[sz]] = sz; D[U[sz]] = sz;
}
else
{
add(sz, ft, R[ft], U[y], y, x, y);
R[L[sz]] = sz; L[R[sz]] = sz;
U[D[sz]] = sz; D[U[sz]] = sz;
}
++cnt[y]; ++sz;
}
void remove(int now)
{
R[L[now]] = R[now];
L[R[now]] = L[now];
for (int i = D[now]; i != now; i = D[i])
for (int j = R[i]; j != i; j = R[j])
{
D[U[j]] = D[j];
U[D[j]] = U[j];
--cnt[col[j]];
}
}
void resume(int now)
{
for (int i = U[now]; i != now; i = U[i])
for (int j = L[i]; j != i; j = L[j])
{
D[U[j]] = j;
U[D[j]] = j;
++cnt[col[j]];
}
R[L[now]] = now;
L[R[now]] = now;
}
bool dfs(int x)
{
if (!R[0]) { num = x; return true; }
int now = R[0];
for (int i = now; i != 0; i = R[i])
if (cnt[now]>cnt[i]) now = i;
remove(now);
for (int i = D[now]; i != now; i = D[i])
{
ans[x] = row[i];
for (int j = R[i]; j != i; j = R[j]) remove(col[j]);
if (dfs(x + 1)) return true;
for (int j = L[i]; j != i; j = L[j]) resume(col[j]);
}
resume(now);
return false;
}
void display()
{
for (int i = 0; i < num; ++i)
{
if (ans[i] == 1) continue;
s[p[ans[i]][0]][p[ans[i]][1]] = p[ans[i]][2] + '0';
s[p[ans[i]][3]][p[ans[i]][4]] = p[ans[i]][5] + '0';
}
for (int i = 1; i <= 9; i++) s[i][10] = 0, puts(s[i] + 1);
}
}dlx;
int un(int x, int y) { return (x - 1) / 3 * 3 + (y - 1) / 3; }
void insert(int x, int y, int z)
{
dlx.insert(tot, 9 * (x - 1) + y);
dlx.insert(tot, 81 + 9 * (x - 1) + z);
dlx.insert(tot, 162 + 9 * (y - 1) + z);
dlx.insert(tot, 243 + 9 * un(x, y) + z);
}
int main()
{
while (scanf("%d", &n) != EOF, n)
{
tot = 1;
dlx.reset(2000, 405);
memset(r, 0, sizeof(r));
memset(f, 0, sizeof(f));
memset(c, 0, sizeof(c));
memset(d, 0, sizeof(d));
memset(mp, 0, sizeof(mp));
rep(i, 1, n)
{
scanf("%d%s%d%s", &a, x, &b, y);
f[min(a, b)][max(a, b)] = 1;
X = x[0] - 'A' + 1, Y = x[1] - '0';
r[X][a] = c[Y][a] = mp[X][Y] = d[un(X, Y)][a] = 1;
insert(X, Y, a); s[X][Y] = '0' + a;
X = y[0] - 'A' + 1, Y = y[1] - '0';
r[X][b] = c[Y][b] = mp[X][Y] = d[un(X, Y)][b] = 1;
insert(X, Y, b); s[X][Y] = '0' + b;
dlx.insert(tot, 324 + (a - 1) * 9 + b);
dlx.insert(tot, 324 + (b - 1) * 9 + a);
}
rep(i, 1, 9)
{
scanf("%s", x);
X = x[0] - 'A' + 1, Y = x[1] - '0';
r[X][i] = c[Y][i] = mp[X][Y] = d[un(X, Y)][i] = 1;
insert(X, Y, i); s[X][Y] = '0' + i;
dlx.insert(tot, 324 + (i - 1) * 9 + i);
}
rep(i, 1, 9)
{
rep(j, 1, 9)
{
if (mp[i][j]) continue;
rep(x, 1, 9)
{
if (r[i][x] || c[j][x] || d[un(i, j)][x]) continue;
rep(y, 1, 9)
{
if (x == y || f[min(x, y)][max(x, y)]) continue;
if (i + 1 < 10 && !mp[i + 1][j])
{
if (!(r[i + 1][y] || c[j][y] || d[un(i + 1, j)][y]))
{
++tot;
insert(i, j, x);
insert(i + 1, j, y);
dlx.insert(tot, 324 + 9 * (x - 1) + y);
dlx.insert(tot, 324 + 9 * (y - 1) + x);
p[tot][0] = i; p[tot][1] = j; p[tot][2] = x;
p[tot][3] = i + 1; p[tot][4] = j; p[tot][5] = y;
}
}
if (j + 1 < 10 && !mp[i][j + 1])
{
if (!(r[i][y] || c[j + 1][y] || d[un(i, j + 1)][y]))
{
++tot;
insert(i, j, x);
insert(i, j + 1, y);
dlx.insert(tot, 324 + 9 * (x - 1) + y);
dlx.insert(tot, 324 + 9 * (y - 1) + x);
p[tot][0] = i; p[tot][1] = j; p[tot][2] = x;
p[tot][3] = i; p[tot][4] = j + 1; p[tot][5] = y;
}
}
}
}
}
}
dlx.dfs(0);
printf("Puzzle %d\n", ++T);
dlx.display();
}
return 0;
}标签：HDU,int,puzzle,each,dominos,ku,ans,domino From： https://blog.51cto.com/u_15870896/5838887