1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
| #include <stdio.h>
#include <string.h>
/* Final state of the problema */
int sol[] = {0,3,4,3,0,5,6,5,0,1,2,1,0,7,8,7,0,9,10,9,0,1,2,1};
/* Actual state */
int v[24];
/* Rotates the vector */
void Rotar(int rotacion) {
int vtmp[24];
int i;
/* Get a copy of the actual state */
memcpy(vtmp, v, sizeof(v));
/* 1 Left Wheel Clockwise rotation */
if(rotacion == 1) {
for(i=0;i<12;i++) {
v[(i+2)%12] = vtmp[i%12];
}
v[21] = v[9];
v[22] = v[10];
v[23] = v[11];
}
/* 2 Right Wheel Clockwise rotation */
else if(rotacion == 2) {
for(i=2;i<12;i++) {
v[i-2+12] = vtmp[i+12];
}
v[22] = vtmp[12];
v[23] = vtmp[13];
v[9] = v[21];
v[10] = v[22];
v[11] = v[23];
}
/* 3 Left Wheel Counter-Clockwise rotation */
else if(rotacion == 3) {
for(i=2;i<12;i++) {
v[i-2] = vtmp[i];
}
v[21] = v[9] = vtmp[11];
v[22] = v[10] = vtmp[0];
v[23] = v[11] = vtmp[1];
}
/* 4 Right Wheel Counter-Clockwise rotation */
else if(rotacion == 4) {
for(i=0;i<12;i++) {
v[((i+2)%12)+12] = vtmp[(i%12)+12];
}
v[12] = vtmp[22];
v[13] = vtmp[23];
v[9] = v[21];
v[10] = v[22];
v[11] = v[23];
}
}
/* returns 1 if we've found the solution */
int Solucion(int *s) {
int i;
for(i=0;i<24;i++) {
if(s[i] != sol[i]) return 0;
}
return 1;
}
/* Generates another level */
void Generar(int nivel, int *s) {
/* Undo previous rotation */
if(s[nivel] == 1) Rotar(3);
if(s[nivel] == 2) Rotar(4);
if(s[nivel] == 3) Rotar(1);
if(s[nivel] == 4) Rotar(2);
s[nivel]++;
if(nivel>0) {
if((s[nivel-1] == 1) && (s[nivel] == 3)) s[nivel]++;
else if((s[nivel-1] == 2) && (s[nivel] == 4)) s[nivel]++;
else if((s[nivel-1] == 3) && (s[nivel] == 1)) s[nivel]++;
else if((s[nivel-1] == 4) && (s[nivel] == 2)) s[nivel]++;
}
if(s[nivel] <= 4)
{
Rotar(s[nivel]);
}
}
/* returns 1 if there's no more brothers */
int NoMasHermanos(int nivel, int *s) {
if(s[nivel] == 4) return 1;
else return 0;
}
/* Backtracking */
void buscar(int *s) {
int i, j, nivel = 0, fin = 0;
/* s = initial solution */
for(i=0;i<16;i++) s[i] = 0;
while(nivel>=0) {
Generar(nivel, s);
if(s[nivel] > 4) {
s[nivel] = 0;
nivel--;
continue;
}
if(Solucion(v)) {
for(j=0;j<=nivel;j++) printf("%d", s[j]);
printf("\n");
return;
}
else if(nivel<15) {
nivel++;
}
else {
while(NoMasHermanos(nivel, s) && nivel >= 0 ) {
Rotar(2);
s[nivel] = 0;
nivel--;
}
}
}
printf("NO SOLUTION WAS FOUND IN 16 STEPS\n");
}
/* Start */
int main() {
int s[16];
int i, j, casos;
scanf("%d", &casos);
for(i=0;i<casos;i++) {
for(j=0;j<24;j++) {
scanf("%d", &v[j]);
}
if(Solucion(v)) printf("PUZZLE ALREADY SOLVED\n");
else buscar(s);
}
return 0;
} |
(
