SandovalPadillaReporteActividad 8 - Fernando Cesar Sandoval Padilla

Vista previa del material en texto

UNIVERSIDAD DE GUADALAJARA
Centro Universitario de Ciencias Exactas e Ingenierías
Algoritmia
Actividad 8: Tablero de ajedrez 
Alumno: Sandoval Padilla Fernando Cesar
Docente: Ibarra Chávez Salomón Eduardo
Código: 215685409
Sección: D02
	
22 de Abril de 2020
Se dispone de un tablero rectangular, por ejemplo, el tablero de ajedrez, y de un caballo, que se mueve según las reglas de este juego. El objetivo es encontrar una manera de recorrer todo el tablero partiendo de una casilla determinada, de tal forma que el caballo pase una sola vez por cada casilla. Posteriormente implementar la solución a dicho problema para hacer una animación 2D.…en modo texto o gráfico. Puedes apoyarte para solucionar este problema, en el principio de L. Euler…como el de los puentes de Königsberg. Archivo binario ejecutable se coloca adjunto al reporte...aunque la animación se presenta en clase.
Para poder resolver un problema siempre ayuda el poder dividir dicho problema en pequeñas partes. En este caso, seria dividir en pequeñas partes el tablero. Debemos tener en claro cuantos recorridos existen y asi, poder enlazarlos hasta llenar todo el tablero.
Aunque Euler planteo principalmente recorridos cerrados, que son más elegantes y además permiten dar solución al problema desde cualquier casilla inicial, para obtener el cuadrado mágico estableció algunas pautas para la resolución general de este problema.
· En este enigmático problema, Euler “dividió” el tablero en cuatro partes, en cuadrados de 16 casillas (4x4) y utilizando la búsqueda de patrones, la simetría y su enorme genialidad, pudo resolver el problema.
1 #include <iostream>
2 #include <cstdlib>
3 #include <ctime>
4
5 using namespace::std;
6 const int Tamano_Arreglo = 8;
7 int Valores (int);
8 void Mueve(int A[Tamano_Arreglo][Tamano_Arreglo], int);
9 int x= 0;
10 int y = 0;
11 int contador = 1;
12 int main()
13 {
14 srand(time(NULL));
15 int Tabla[Tamano_Arreglo][Tamano_Arreglo] = {{0}, {0}};
16 int i;
17 int centinela = 1;
18 int casillas_a_llenar;
19 int Puedo_Mover_Aqui[Tamano_Arreglo] = {0};
20 int Valores_Accesibilidad[Tamano_Arreglo] = {0, 0};
21 cout <<"\nCuantas casillas quiere que recorra el caballo por lo menos?"<<endl;
22 cin>> casillas_a_llenar;
23 for ( int j = 0; j < Tamano_Arreglo; j++)
24 {
25 for ( int k = 0; j < Tamano_Arreglo; k++)
26 {
27 Tabla[j][k] = 0;
28 }
29 Puedo_Mover_Aqui[j] = 0;
30 Valores_Accesibilidad[j] = 10;
31 }
32 Tabla[y][x] = 1;
33 while ( casillas_a_llenar > contador && 1 == centinela )
34 {
35 centinela = 0;
36 for( int k = 0; k < Tamano_Arreglo; k++ )
37 {
38 Puedo_Mover_Aqui[k] = 0;
39 Valores_Accesibilidad[k] = 10;
40 }
41 for( i = 0; i < Tamano_Arreglo; i++ )
42 {
43 switch (i)
44 {
45 case 0:
46 if ( x + 2 < Tamano_Arreglo && y - 1>= 0 )
47 {
48 if ( Tabla[y - 1][x + 2] == 0 )
49 {
50 Puedo_Mover_Aqui[i] = 1;
51 }
52 }
53 break;
54 case 1:
55 if (x + 1 < Tamano_Arreglo && y - 2 >= 0 )
56 {
57 Puedo_Mover_Aqui[i] = 1;
58 }
59 break;
60 case 2:
61 if ( x - 1 >= 0 && y - 2 >=0 )
62 {
63 if ( Tabla[y-2][x-1] == 0)
64 {
65 Puedo_Mover_Aqui[i] = 1;
66 }
67 }
68 break;
69 case 3:
70 if ( x - 2 >= 0 && y - 1 >=0 )
71 {
72 if ( Tabla[y-1][x-2] == 0)
73 {
74 Puedo_Mover_Aqui[i] = 1;
75 }
76 }
77 break;
78 case 4:
79 if ( x - 2 >= 0 && y + 1 < Tamano_Arreglo )
80 {
81 if ( Tabla[y+1][x-2] == 0)
82 {
83 Puedo_Mover_Aqui[i] = 1;
84 }
85 }
86 break;
87 case 5:
88 if ( x - 1 >= 0 && y + 2 < Tamano_Arreglo )
89 {
90 if ( Tabla[y+2][x-1] == 0)
91 {
92 Puedo_Mover_Aqui[i] = 1;
93 }
94 }
95 break;
96 case 6:
97 if ( x + 1 < Tamano_Arreglo && y + 2 < Tamano_Arreglo )
98 {
99 if ( Tabla[y+2][x+1] == 0)
100 {
101 Puedo_Mover_Aqui[i] = 1;
102 }
103 }
104 break;
105 case 7:
106 if ( x + 2 < Tamano_Arreglo && y + 1 < Tamano_Arreglo )
107 {
108 if ( Tabla[y+1][x+2] == 0)
109 {
110 Puedo_Mover_Aqui[i] = 1;
111 }
112 }
113 break;
114 default:
115 {
116 cout <<"El contador i no esta dando los números correctos"<<endl
117 <<"El contador es: "<< i <<endl;
118 break;
119 }
120 }
121 }
122 for ( i = 0; i < Tamano_Arreglo; i++ )
123 {
124 if ( 1 == Puedo_Mover_Aqui[i] )
125 {
126 centinela = 1;
127 }
128 }
129 if ( 1 == centinela )
130 {
131 for ( i = 0; i < Tamano_Arreglo; i++ )
132 {
133 if ( 1 == Puedo_Mover_Aqui[i])
134 {
135 Valores_Accesibilidad[i] = Valores(i);
136 }
137 }
138 int menor = Valores_Accesibilidad[0];
139 int movimiento_a_hacer = 0;
140 for ( i = 1; i < Tamano_Arreglo; i++ )
141 {
142 if ( Valores_Accesibilidad[i] < menor )
143 {
144 menor = Valores_Accesibilidad[i];
145 movimiento_a_hacer = i;
146 }
147 if ( Valores_Accesibilidad[i] == menor )
148 {
149 int aguila_o_sol = rand() % 2;
150 movimiento_a_hacer = i;
151 }
152 }
153 ++contador;
154 Mueve( Tabla, movimiento_a_hacer);
155 }
156 }
157 cout <<"El contador es: "<<contador<<endl;
158 for (int d = 0; d < Tamano_Arreglo; d++ )
159 {
160 for (int k = 0; k < Tamano_Arreglo; k++ )
161 {
162 if ( 0 == Tabla[d][k] && 0 == Tabla[d][k] / 10)
163 cout<<" ";
164 cout<<Tabla[d][k]<<" ";
165 }
166 cout<<endl<<endl;
167 }
168 return 0;
169 }
170 int Valores(int movimiento){
171 int Accesibilidad[Tamano_Arreglo + 1][Tamano_Arreglo + 1] =
172 {
173 {2, 3, 4, 4, 4, 4, 3, 2},
174 {3, 4, 6, 6, 6, 6, 4, 3},
175 {4, 6, 8, 8, 8, 8, 6, 4},
176 {4, 6, 8, 8, 8, 8, 6, 4},
177 {4, 6, 8, 8, 8, 8, 6, 4},
178 {4, 6, 8, 8, 8, 8, 6, 4},
179 {3, 4, 6, 6, 6, 6, 4, 3},
180 {2, 3, 4, 4, 4, 4, 3, 2}
181 };
182 switch (movimiento) {
183 case 0:
184 return Accesibilidad[y - 1] [x + 2];
185 break;
186 case 1:
187 return Accesibilidad[y - 2] [x + 1];
188 break;
189 case 2:
190 return Accesibilidad[y - 2] [x - 1];
191 break;
192 case 3:
193 return Accesibilidad[y - 1] [x - 2];
194 break;
195 case 4:
196 return Accesibilidad[y + 1] [x - 2];
197 break;
198 case 5:
199 return Accesibilidad[y + 2] [x - 1];
200 break;
201 case 6:
202 return Accesibilidad[y + 2] [x + 1];
203 break;
204 case 7:
205 return Accesibilidad[y + 1] [x + 2];
206 break;
207 default:
208 cout<<"El movimiento es ilegal"<<endl
209 <<"El movimiento es: "<<movimiento<<endl;
210 return -1;
211 break;
212 }
213 }
214 void Mueve(int A[Tamano_Arreglo][Tamano_Arreglo], int movimientos) {
215 switch (movimientos) {
216 case 0:
217 y -= 1;
218 x += 2;
219 A[y][x] = contador;
220 break;
221 case 1:
222 y -= 2;
223 x += 1;
224 A[y][x] = contador;
225 break;
226 case 2:
227 y -= 2;
228 x -= 1;
229 A[y][x] = contador;
230 break;
231 case 3:
232 y -= 1;
233 x -= 2;
234 A[y][x] = contador;
235 break;
236 case 4:
237 y += 1;
238 x -= 2;
239 A[y][x] = contador;
240 break;
241 case 5:
242 y += 2;
243 x -= 1;
244 A[y][x] = contador;
245 break;
246 case 6:
247 y += 2;
248 x += 1;
249 A[y][x] = contador;
250 break;
251 case 7:
252 y += 1;
253 x += 2;
254 A[y][x] = contador;
255 break;
256 default:
257 cout<<"El movimiento es ilegal"<<endl
258 <<"El movimiento es: "<<movimientos<<endl;
259 break;
260 }
261 return ;
262 }