domingo, octubre 24, 2010

8 reinas con las soluciones singulares y derivadas

Recordad que el problema que se planteaba no es la típica de las 8 damas.
Tiene un extra y es localizar las 12 soluciones originales y sus derivadas que en total son 92.

El autor del programa es Eduardo Prez de Argentina. Este autor ha colaborado también en buenos sitios de programación como el de Elguille. Aquí un ejemplo.


Por cierto, el autor ha elegido QBASIC (novedad del MSDOS 5.0 ) que sustituyó el GWBASIC de 1983 (mi primer lenguaje con el MSDOS 3.3, sniff sniff).

GWBASIC requería numerar las líneas lo cual era un rollo a la hora de toquetear el código. Si además utilizabas el GOTO la interpretación de programas ya era una locura.

QBASIC ya no requiere la numeración, aunque yo se la he añadido sólo para facilitar la lectura.

Enseguida recordaréis el mayor problema del QBASIC. No facilita la programación estructurada con tanto GOSUB sin especificar parámetros, sin declaración previa de funciones, Bloques IF sin delimitadores de bloque, posibilidad de utilizar el GOTO del demonio, etc. etc.

Aclaración:

Cada solución es un string con 8 coordenadas. En el formato empleado cada coordenada está compuesta por 4 caracteres (longitud = 32).

Ejemplo del string con solución no válida: |11||25||38||46||53||67||72||84|

 1 '8DAMAS.BAS-2010.09.11-22:54-2010.09.16-11:46
2 DIM StrSol12$, IntSol92%
3 DIM StrSol92$, IntSol12%
4 DIM StrO$(12), IntO%, StrA$, IntA%
5 DIM StrSo$(12), IntSo%, Hasta%
6 DIM K$, KN$, Dama$, MA$, M$, U$, D$, V$, C$, Z$
7 DIM Li%, Co%, Grabar%, VDis%, Ve%, Ka%, I%, J%, R%, x%, W%
8 '=============================================================================
9 CLS
10 GOSUB InicioDamasTxt
11 Li% = 1
12 Co% = 1
13 IntSol92% = 0
14 IntSol12% = 0
15 IntSo% = 0
16 V$ = "|1 ||2 ||3 ||4 ||5 ||6 ||7 ||8 |"
17 K$ = ""
18 '=============================================================================
19 DO
20 GOSUB VerificarDisponibilidad
21 IF VDis% = 1 THEN 'if-01 comienza dama a tira solucion
22 'K$ = |11||22||33||44||55||66||77||88|
23 Dama$ = MID$(STR$(Li%), 2) + MID$(STR$(Co%), 2)
24 K$ = K$ + "|" + Dama$ + "|"
25 '=============================================================================
26 IF LEN(K$) = 32 THEN 'if-02 comienza completo 32 caracteres
27 '=============================================================================
28 'normalizar solucion
29 KN$ = "": FOR R% = 1 TO 8
30 W% = INSTR(K$, "|" + MID$(STR$(R%), 2))
31 KN$ = KN$ + MID$(K$, W%, 4)
32 NEXT R%
33 '=============================================================================
34 Grabar% = 1 's1 grabar por defecto
35 OPEN "8DAMAS.TXT" FOR INPUT AS #1
36 DO WHILE EOF(1) = False
37 LINE INPUT #1, D$
38 IF KN$ = LEFT$(D$, 32) THEN 'if-03
39 Grabar% = 0 'n0 grabar ya existe en la lista
40 EXIT DO
41 END IF 'if-03
42 LOOP
43 CLOSE #1
44 '=============================================================================
45 IF Grabar% = 1 THEN 'if-04 comienza grabar
46 D$ = KN$
47 '=============================================================================
48 GOSUB GiroYVolteo
49 IntSo% = IntSo% + 1
50 StrSo$(IntSo%) = StrO$(1)
51 FOR R% = 1 TO 8: IntSol92% = IntSol92%
52 + 1
53 Z$ = StrO$(R%)
54 PRINT #1, Z$
55 NEXT R%
56 CLOSE #1
57 IF IntSol92% = 96 THEN 'if-10
58 FOR R% = 1 TO 12
59 StrO$(R%) = StrSo$(R%)
60 NEXT R%
61 Hasta% = 12: GOSUB Ordenar
62 FOR R% = 1 TO 12
63 StrSo$(R%) = StrO$(R%)
64 PRINT StrSo$(R%)
65 NEXT R%
66 GOSUB InicioDamasTxt
67 IntSol92% = 0
68 IntSol12% = 0
69 FOR x% = 1 TO 12
70 D$ = StrSo$(x%): GOSUB GiroYVolteo: GOSUB Imprimir
71 NEXT x%
72 INPUT "PULSAR ENTER PARA SALIR", Z$
73 END'salida FIN
74 END IF
75 '=============================================================================
76 END IF 'if-04 finaliza grabar
77 END IF 'if-02 finaliza completo 32 caracteres
78 END IF 'if-01 finaliza dama a tira solucion
79 GOSUB CambiarCol
80 LOOP
81 END'salida FIN
82 '=============================================================================
83 VerificarDisponibilidad:
84 VDis% = 1 ' disponible s1,
85 '========================================================
86 'verificar si la linea esta ocupada
87 FOR Ka% = 1 TO LEN(K$) STEP 4
88 IF Li% = VAL(MID$(K$, Ka% + 1, 1)) THEN 'if-07
89 VDis% = 0 'disponible n0, linea ocupada 'LINOCU 100976/8=12622
90 RETURN 'no verificar nada mas, salir urgente
91 END IF'if-07
92 NEXT Ka%
93 '========================================================
94 'verificar si la columna esta ocupada
95 FOR Ka% = 1 TO LEN(K$) STEP 4
96 IF Co% = VAL(MID$(K$, Ka% + 2, 1)) THEN 'if-08
97 VDis% = 0 'disponible n0, columna ocupada 'COLOCU 106384/8=13298
98 RETURN 'no verificar nada mas, salir urgente
99 END IF'if-08
100 NEXT Ka%
101 '========================================================
102 'verificar si la diagonal esta ocupada
103 FOR Ka% = 1 TO LEN(K$) STEP 4
104 IF ABS(Li% - VAL(MID$(K$, Ka% + 1, 1))) = ABS(Co% - VAL(MID$(K$, Ka% + 2, 1))
105 ) THEN 'if-09
106 VDis% = 0 'disponible n0, diagonal ocupada 'DIAOCU 33784/8= 4223
107 RETURN 'no verificar nada mas, salir urgente
108 END IF'if-09
109 NEXT Ka%
110 RETURN
111 '=============================================================================
112 formato:
113 IntA% = IntA% + 1
114 StrA$ = MID$(STR$(IntA%), 2)
115 StrA$ = STRING$(2 - LEN(StrA$), 48) + StrA$
116 RETURN
117 '=============================================================================
118 OtraLinea:
119 IntA% = IntSol92%: GOSUB formato
120 IntSol92% = IntA%
121 StrSol92$ = StrA$
122 RETURN
123 '=============================================================================
124 CambiarCol:
125 IF Li% = 8 AND Co% = 8 THEN 'if-11
126 U$ = RIGHT$(K$, 4) 'IF11-- 26072/8= 3259
127 K$ = LEFT$(K$, LEN(K$) - 4) 'quita ultima dama
128 Li% = VAL(MID$(U$, 2, 1))
129 Co% = VAL(MID$(U$, 3, 1))
130 IF Co% < 8 THEN 'if-12
131 Co% = Co% + 1'IF12SI 23832/8= 2979
132 ELSE
133 U$ = RIGHT$(K$, 4) 'IF12NO 2240/8= 280
134 K$ = LEFT$(K$, LEN(K$) - 4) 'quita ultima dama
135 Li% = VAL(MID$(U$, 2, 1))
136 Co% = VAL(MID$(U$, 3, 1)) + 1
137 END IF'if-12
138 RETURN
139 END IF'if-11
140 IF Co% < 8 THEN 'if-13
141 Co% = Co% + 1 'IF13SI 222352/8=27794
142 ELSE
143 GOSUB CambiarLin 'IF13NO 21088/8= 2636
144 Co% = 1
145 END IF'if-13
146 RETURN
147 '=============================================================================
148 CambiarLin:
149 IF Li% < 8 THEN Li% = Li% + 1'if-14
150 RETURN
151 '=============================================================================
152 Imprimir:
153 IntA% = IntSol12%: GOSUB formato
154 IntSol12% = IntA%
155 StrSol12$ = StrA$
156 GOSUB OtraLinea
157 FOR S% = 1 TO 8
158 MA$ = "|": M$ = StrO$(S%)
159 FOR R% = 1 TO 32 STEP 4
160 MA$ = MA$ + MID$(M$, R% + 1, 3)
161 NEXT R%
162 StrO$(S%) = MA$
163 NEXT S%
164
165 Z$ = StrO$(1) + " (" + StrSol92$ + ") SALEN
166 DE: " + StrO$(1) + " (" + StrSol12$ + ")"
167 PRINT #1, Z$
168 PRINT Z$
169 FOR IntO% = 2 TO 8
170 IF StrO$(IntO% - 1) <> StrO$(IntO%) THEN 'if-06
171 GOSUB OtraLinea
172 Z$ = StrO$(IntO%) + " (" + StrSol92$ + ")"
173 PRINT #1, Z$
174 PRINT Z$
175 END IF 'if-06
176 NEXT IntO%
177 Z$ =
178 "============================================
179 ==========================="
180 PRINT #1, Z$
181 PRINT Z$
182 CLOSE #1
183 RETURN
184 '=============================================================================
185 Ordenar:
186 FOR I% = 1 TO Hasta% - 1
187 FOR J% = I% + 1 TO Hasta%
188 IF StrO$(I%) > StrO$(J%) THEN 'if-05
189 SWAP StrO$(I%), StrO$(J%)
190 END IF 'if-05
191 NEXT J%
192 NEXT I%
193 RETURN
194 '=============================================================================
195 GiroYVolteo:
196 'giro 90 grados direccion reloj
197 IntO% = 0
198 FOR Ve% = 1 TO 4
199 K$ = V$
200 FOR R% = 1 TO 32 STEP 4
201 C$ = MID$(STR$((9 - VAL(MID$(D$, R%
202 + 1, 1)))), 2) 'giro 90 grados
203 direccion reloj
204 MID$(K$, VAL(MID$(D$, R% + 2, 1)) * 4 - 1) = C$
205 NEXT R%
206 '=============================================================================
207 IntO% = IntO% + 1
208 StrO$(IntO%) = K$ 'guarda giro 90 grados direccion reloj
209 '=============================================================================
210 'volteo vertical
211 D$ = K$
212 K$ = V$
213 FOR R% = 1 TO 32 STEP 4
214 C$ = MID$(D$, R% + 2, 1) 'volteo vertical
215 MID$(K$, 32 - R%) = C$
216 NEXT R%
217 '=============================================================================
218 D$ = StrO$(IntO%) 'inicializa proxima solucion a girar
219 IntO% = IntO% + 1
220 StrO$(IntO%) = K$ 'guarda volteo vertical
221 NEXT Ve%
222 '=============================================================================
223 'ordenar de menor a mayor
224 Hasta% = 8: GOSUB Ordenar
225 '=============================================================================
226 OPEN "8DAMAS.TXT" FOR APPEND AS #1
227 '=============================================================================
228 RETURN
229 '=============================================================================
230 InicioDamasTxt:
231 OPEN "8DAMAS.TXT" FOR OUTPUT AS #1
232 PRINT #1, "Listado de soluciones Posibles
233 Listado de soluciones Diferentes"
234 PRINT #1,
235 "======================================================
236 ================="
237 CLOSE #1
238 RETURN
239 '=============================================================================
240 'IF12NO 2240/8= 280
241 'IF13NO 21088/8= 2636
242 'IF12SI 23832/8= 2979
243 'IF11-- 26072/8= 3259
244 'DIAOCU 33784/8= 4223
245 'LINOCU 100976/8=12622
246 'COLOCU 106384/8=13298
247 'IF13SI 222352/8=27794
248 ' 67091---> 1.53125/67091=.000022823478559 segundos x if
249 'TIEMPO TOTAL DE EJECUCION 1.53125 SEGUNDOS -2010.09.16-11:51
250

Resultado de la ejecución:

Listado de soluciones Posibles Listado de soluciones Diferentes
=======================================================================
|11|25|38|46|53|67|72|84| (01) SALEN DE: |11|25|38|46|53|67|72|84| (01)
|11|27|35|48|52|64|76|83| (02)
|13|26|34|42|58|65|77|81| (03)
|14|22|37|43|56|68|75|81| (04)
|15|27|32|46|53|61|74|88| (05)
|16|23|35|47|51|64|72|88| (06)
|18|22|34|41|57|65|73|86| (07)
|18|24|31|43|56|62|77|85| (08)
=======================================================================
|11|26|38|43|57|64|72|85| (09) SALEN DE: |11|26|38|43|57|64|72|85| (02)
|11|27|34|46|58|62|75|83| (10)
|13|25|32|48|56|64|77|81| (11)
|14|27|35|42|56|61|73|88| (12)
|15|22|34|47|53|68|76|81| (13)
|16|24|37|41|53|65|72|88| (14)
|18|22|35|43|51|67|74|86| (15)
|18|23|31|46|52|65|77|84| (16)
=======================================================================
|12|24|36|48|53|61|77|85| (17) SALEN DE: |12|24|36|48|53|61|77|85| (03)
|13|28|34|47|51|66|72|85| (18)
|14|22|38|46|51|63|75|87| (19)
|14|27|33|48|52|65|71|86| (20)
|15|22|36|41|57|64|78|83| (21)
|15|27|31|43|58|66|74|82| (22)
|16|21|35|42|58|63|77|84| (23)
|17|25|33|41|56|68|72|84| (24)
=======================================================================
|12|25|37|41|53|68|76|84| (25) SALEN DE: |12|25|37|41|53|68|76|84| (04)
|13|26|32|47|51|64|78|85| (26)
|14|21|35|48|52|67|73|86| (27)
|14|26|38|43|51|67|75|82| (28)
|15|23|31|46|58|62|74|87| (29)
|15|28|34|41|57|62|76|83| (30)
|16|23|37|42|58|65|71|84| (31)
|17|24|32|48|56|61|73|85| (32)
=======================================================================
|12|25|37|44|51|68|76|83| (33) SALEN DE: |12|25|37|44|51|68|76|83| (05)
|13|26|32|47|55|61|78|84| (34)
|13|26|38|41|54|67|75|82| (35)
|14|28|31|45|57|62|76|83| (36)
|15|21|38|44|52|67|73|86| (37)
|16|23|31|48|55|62|74|87| (38)
|16|23|37|42|54|68|71|85| (39)
|17|24|32|45|58|61|73|86| (40)
=======================================================================
|12|26|31|47|54|68|73|85| (41) SALEN DE: |12|26|31|47|54|68|73|85| (06)
|13|21|37|45|58|62|74|86| (42)
|13|25|37|41|54|62|78|86| (43)
|14|26|31|45|52|68|73|87| (44)
|15|23|38|44|57|61|76|82| (45)
|16|24|32|48|55|67|71|83| (46)
|16|28|32|44|51|67|75|83| (47)
|17|23|38|42|55|61|76|84| (48)
=======================================================================
|12|26|38|43|51|64|77|85| (49) SALEN DE: |12|26|38|43|51|64|77|85| (07)
|13|27|32|48|56|64|71|85| (50)
|14|22|35|48|56|61|73|87| (51)
|14|28|35|43|51|67|72|86| (52)
|15|21|34|46|58|62|77|83| (53)
|15|27|34|41|53|68|76|82| (54)
|16|22|37|41|53|65|78|84| (55)
|17|23|31|46|58|65|72|84| (56)
=======================================================================
|12|27|33|46|58|65|71|84| (57) SALEN DE: |12|27|33|46|58|65|71|84| (08)
|12|28|36|41|53|65|77|84| (58)
|14|21|35|48|56|63|77|82| (59)
|14|27|35|43|51|66|78|82| (60)
|15|22|34|46|58|63|71|87| (61)
|15|28|34|41|53|66|72|87| (62)
|17|21|33|48|56|64|72|85| (63)
|17|22|36|43|51|64|78|85| (64)
=======================================================================
|12|27|35|48|51|64|76|83| (65) SALEN DE: |12|27|35|48|51|64|76|83| (09)
|13|26|34|41|58|65|77|82| (66)
|14|22|37|43|56|68|71|85| (67)
|14|28|31|43|56|62|77|85| (68)
|15|21|38|46|53|67|72|84| (69)
|15|27|32|46|53|61|78|84| (70)
|16|23|35|48|51|64|72|87| (71)
|17|22|34|41|58|65|73|86| (72)
=======================================================================
|13|25|32|48|51|67|74|86| (73) SALEN DE: |13|25|32|48|51|67|74|86| (10)
|14|26|38|42|57|61|73|85| (74)
|15|23|31|47|52|68|76|84| (75)
|16|24|37|41|58|62|75|83| (76)
=======================================================================
|13|25|38|44|51|67|72|86| (77) SALEN DE: |13|25|38|44|51|67|72|86| (11)
|13|26|38|42|54|61|77|85| (78)
|13|27|32|48|55|61|74|86| (79)
|14|22|38|45|57|61|73|86| (80)
|15|27|31|44|52|68|76|83| (81)
|16|22|37|41|54|68|75|83| (82)
|16|23|31|47|55|68|72|84| (83)
|16|24|31|45|58|62|77|83| (84)
=======================================================================
|13|26|32|45|58|61|77|84| (85) SALEN DE: |13|26|32|45|58|61|77|84| (12)
|13|26|38|41|55|67|72|84| (86)
|14|22|37|45|51|68|76|83| (87)
|14|27|31|48|55|62|76|83| (88)
|15|22|38|41|54|67|73|86| (89)
|15|27|32|44|58|61|73|86| (90)
|16|23|31|48|54|62|77|85| (91)
|16|23|37|44|51|68|72|85| (92)
=======================================================================

No hay comentarios: