[UVA][DLX] 211 - The Domino Effect
The Domino Effect
| The Domino Effect |
A standard set of Double Six dominoes contains 28 pieces (called bones) each displaying two numbers from 0 (blank) to 6 using dice-like pips. The 28 bones, which are unique, consist of the following combinations of pips:
Bone # Pips Bone # Pips Bone # Pips Bone # Pips
1 0 | 0 8 1 | 1 15 2 | 3 22 3 | 6
2 0 | 1 9 1 | 2 16 2 | 4 23 4 | 4
3 0 | 2 10 1 | 3 17 2 | 5 24 4 | 5
4 0 | 3 11 1 | 4 18 2 | 6 25 4 | 6
5 0 | 4 12 1 | 5 19 3 | 3 26 5 | 5
6 0 | 5 13 1 | 6 20 3 | 4 27 5 | 6
7 0 | 6 14 2 | 2 21 3 | 5 28 6 | 6
All the Double Six dominoes in a set can he laid out to display a 7 x 8 grid of pips. Each layout corresponds at least one ``map" of the dominoes. A map consists of an identical 7 x 8 grid with the appropriate bone numbers substituted for the pip numbers appearing on that bone. An example of a 7 x 8 grid display of pips and a corresponding map of bone numbers is shown below.
7 x 8 grid of pips map of bone numbers
6 6 2 6 5 2 4 1 28 28 14 7 17 17 11 11
1 3 2 0 1 0 3 4 10 10 14 7 2 2 21 23
1 3 2 4 6 6 5 4 8 4 16 25 25 13 21 23
1 0 4 3 2 1 1 2 8 4 16 15 15 13 9 9
5 1 3 6 0 4 5 5 12 12 22 22 5 5 26 26
5 5 4 0 2 6 0 3 27 24 24 3 3 18 1 19
6 0 5 3 4 2 0 3 27 6 6 20 20 18 1 19
Write a program that will analyze the pattern of pips in any 7 x 8 layout of a standard set of dominoes and produce a map showing the position of all dominoes in the set. If more than one arrangement of dominoes yield the same pattern, your program should generate a map of each possible layout.
Input
The input file will contain several of problem sets. Each set consists of seven lines of eight integers from 0 through 6, representing an observed pattern of pips. Each set is corresponds to a legitimate configuration of bones (there will be at least one map possible for each problem set). There is no intervening data separating the problem sets.
Output
Correct output consists of a problem set label (beginning with Set #1) followed by an echo printing of the problem set itself. This is followed by a map label for the set and the map(s) which correspond to the problem set. (Multiple maps can be output in any order.) After all maps for a problem set have been printed, a summary line stating the number of possible maps appears.
At least three lines are skipped between the output from different problem sets while at least one line separates the labels, echo printing, and maps within the same problem set.
A sample input file of two problem sets along with the correct output are shown.
Sample Input
5 4 3 6 5 3 4 6 0 6 0 1 2 3 1 1 3 2 6 5 0 4 2 0 5 3 6 2 3 2 0 6 4 0 4 1 0 0 4 1 5 2 2 4 4 1 6 5 5 5 3 6 1 2 3 1 4 2 5 2 6 3 5 4 5 0 4 3 1 4 1 1 1 2 3 0 2 2 2 2 1 4 0 1 3 5 6 5 4 0 6 0 3 6 6 5 4 0 1 6 4 0 3 0 6 5 3 6 2 1 5 3
Sample Output
Layout #1:
5 4 3 6 5 3 4 6
0 6 0 1 2 3 1 1
3 2 6 5 0 4 2 0
5 3 6 2 3 2 0 6
4 0 4 1 0 0 4 1
5 2 2 4 4 1 6 5
5 5 3 6 1 2 3 1
Maps resulting from layout #1 are:
6 20 20 27 27 19 25 25
6 18 2 2 3 19 8 8
21 18 28 17 3 16 16 7
21 4 28 17 15 15 5 7
24 4 11 11 1 1 5 12
24 14 14 23 23 13 13 12
26 26 22 22 9 9 10 10
There are 1 solution(s) for layout #1.
Layout #2:
4 2 5 2 6 3 5 4
5 0 4 3 1 4 1 1
1 2 3 0 2 2 2 2
1 4 0 1 3 5 6 5
4 0 6 0 3 6 6 5
4 0 1 6 4 0 3 0
6 5 3 6 2 1 5 3
Maps resulting from layout #2 are:
16 16 24 18 18 20 12 11
6 6 24 10 10 20 12 11
8 15 15 3 3 17 14 14
8 5 5 2 19 17 28 26
23 1 13 2 19 7 28 26
23 1 13 25 25 7 4 4
27 27 22 22 9 9 21 21
16 16 24 18 18 20 12 11
6 6 24 10 10 20 12 11
8 15 15 3 3 17 14 14
8 5 5 2 19 17 28 26
23 1 13 2 19 7 28 26
23 1 13 25 25 7 21 4
27 27 22 22 9 9 21 4
There are 2 solution(s) for layout #2.
題目描述：
雙六骨牌，總共 28 枚骨牌，在 7x8 盤面上精準覆蓋。也就是說盤面上有 56 個數字，每個骨牌可以覆蓋相鄰 2 個數字。並且每個數字只用 1 次，並且輸出全部可能。
題目解法：
看到這個什麼雙六骨牌，完全不知是何物！很明顯地是一道搜索題目，
看到精準覆蓋便可以直接套用 Dancing Links + Algorithm X。
不這麼做也行，如果採用嘗試依序放入某個數字，搜索可以藉由 bitmask 壓在 64-bits 進行快速匹配。
如果是按照盤面從上而下從左而右窮舉，依序填入也行。
DLX rank 6。
總共 56 格 + 28 個數字要精準覆蓋。
#include <stdio.h>
#include <algorithm>
using namespace std;
struct DancingLinks {
int left, right, up, down, ch;
int x0, x1, y0, y1, bone; // extra data
} DL[1000 + 256];
int s[256], o[256], head, size;
int n; // this problem need n for output process.
void remove(int c) {
DL[DL[c].right].left = DL[c].left;
DL[DL[c].left].right = DL[c].right;
int i, j;
for(i = DL[c].down; i != c; i = DL[i].down) {
for(j = DL[i].right; j != i; j = DL[j].right) {
DL[DL[j].down].up = DL[j].up;
DL[DL[j].up].down = DL[j].down;
s[DL[j].ch]--;
}
}
}
void resume(int c) {
int i, j;
for(i = DL[c].down; i != c; i = DL[i].down) {
for(j = DL[i].left; j != i; j = DL[j].left) {
DL[DL[j].down].up = j;
DL[DL[j].up].down = j;
s[DL[j].ch]++;
}
}
DL[DL[c].right].left = c;
DL[DL[c].left].right = c;
}
int found;
int print(int dep) {
int i, j;
static int g[10][10];
for(i = 0; i < dep; i++) {
g[DL[o[i]].x0][DL[o[i]].y0] = DL[o[i]].bone;
g[DL[o[i]].x1][DL[o[i]].y1] = DL[o[i]].bone;
}
puts("");
for(i = 0; i < 7; i++) {
for(j = 0; j < 8; j++)
printf("%4d", g[i][j]);
puts("");
}
}
void dfs(int dep) {
if(DL[head].right == head) {
print(dep);
found++;
return;
}
int tmp = 0xffff, c, i, j;
for(i = DL[head].right; i != head; i = DL[i].right)
if(s[i] < tmp)
tmp = s[i], c = i;
remove(c);
for(i = DL[c].down; i != c; i = DL[i].down) {
o[dep] = i;
for(j = DL[i].right; j != i; j = DL[j].right)
remove(DL[j].ch);
dfs(dep+1);
for(j = DL[i].left; j != i; j = DL[j].left)
resume(DL[j].ch);
}
resume(c);
}
int getnode(int u, int d, int l, int r) {
DL[size].up = u, DL[size].down = d;
DL[size].left = l, DL[size].right = r;
DL[u].down = DL[d].up = DL[l].right = DL[r].left = size;
return size++;
}
void newrow(int r[], int rn, int x0, int y0, int x1, int y1, int bone) {
int i, j, h;
for(i = 0; i < rn; i++) {
DL[size].ch = r[i], s[r[i]]++;
DL[size].x0 = x0; // extra data
DL[size].x1 = x1; // extra data
DL[size].y0 = y0; // extra data
DL[size].y1 = y1; // extra data
DL[size].bone = bone; // extra data
if(i) {
j = getnode(DL[DL[r[i]].ch].up, DL[r[i]].ch, DL[h].left, h);
} else {
h = getnode(DL[DL[r[i]].ch].up, DL[r[i]].ch, size, size);
}
}
}
void init(int c) {// total column
size = 0;
head = getnode(0,0,0,0);
int i;
for(i = 1; i <= c; i++) {
getnode(i, i, DL[head].left, head);
DL[i].ch = i, s[i] = 0;
}
}
int main() {
int i, j, k;
int g[10][10];
int cases = 0;
while(true) {
for(i = 0; i < 7; i++) {
for(j = 0; j < 8; j++) {
if(scanf("%d", &g[i][j]) != 1)
return 0;
}
}
init(7*8 + 28);
int a, b, bone;
int bused[] = {0,7,13,18,22,25,27};
int row[10], ridx;
for(i = 0; i < 7; i++) {
for(j = 0; j < 8; j++) {
a = g[i][j], b = g[i][j+1];
if(a > b) swap(a, b);
if(j+1 < 8) {
bone = bused[a]+b-a+1;
ridx = 0;
row[ridx++] = i*8+j+1;
row[ridx++] = i*8+(j+1)+1;
row[ridx++] = 56 + bone;
newrow(row, ridx, i, j, i, j+1, bone);
}
a = g[i][j], b = g[i+1][j];
if(a > b) swap(a, b);
if(i+1 < 7) {
bone = bused[a]+b-a+1;
ridx = 0;
row[ridx++] = i*8+j+1;
row[ridx++] = (i+1)*8+j+1;
row[ridx++] = 56 + bone;
newrow(row, ridx, i, j, i+1, j, bone);
}
}
}
if(cases) puts("\n\n");
printf("Layout #%d:\n\n", ++cases);
for(i = 0; i < 7; i++) {
for(j = 0; j < 8; j++)
printf("%4d", g[i][j]);
puts("");
}
printf("\nMaps resulting from layout #%d are:\n", cases);
found = 0;
dfs(0);
printf("\nThere are %d solution(s) for layout #%d.\n", found, cases);
}
return 0;
}