Caballo.c

  1. /*
  2. Fichero CABALLO. Francisco José Cascales Rueda. 12 de Abril de 1990.
  3.  
  4.  
  5. Método del BACKTRACKING ( Prueba y error).
  6. -------------------------------------------
  7.  
  8. Tenemos un tablero de N x M y un caballo de ajedrez en una
  9. posición (x,y). Se trata de que el caballo sin saltar dos
  10. veces por el mismo sitio cubra todo el tablero. Para ello
  11. se utiliza un árbol de búsqueda en profundidad.
  12.  
  13.  
  14. Algoritmo
  15. ---------
  16. inicializar los movimientos posibles
  17.  
  18. procedimiento PRUEBA Y ERROR
  19. inicio
  20. repetir
  21. seleccionar siguiente movimiento
  22. si movimiento ACEPTABLE entonces inicio
  23. anotar la solución
  24. si SOLUCION NO COMPLETA entonces inicio
  25. PRUEBA Y ERROR
  26. si NO ACERTADO entonces inicio
  27. borrar solucion
  28. fin
  29. fin
  30. fin
  31. hasta movimiento acertado o no hayan más movimientos posibles
  32. fin.
  33.  
  34. */
  35. /*-----------------------------------------------------------------------------
  36.  
  37. L I B R E R I A S
  38.  
  39. -----------------------------------------------------------------------------*/
  40.  
  41. #include <stdlib.h> /* exit, malloc */
  42. #include <stdarg.h> /* va_start, va_arg, va_end */
  43. #include <string.h> /* strlen */
  44. #include <stdio.h> /* vsprintf, printf, fprintf, puts, fopen, fclose */
  45. #include <conio.h> /* putch, clrscr, gotoxy, textattr */
  46. #include <dos.h> /* geninterrupt, outportb */
  47.  
  48. /*-----------------------------------------------------------------------------
  49.  
  50. V A R I A B L E S G L O B A L E S
  51.  
  52. -----------------------------------------------------------------------------*/
  53.  
  54. const AZUL = 113;
  55. const GRIS = 23;
  56.  
  57. char *tabla; /* Tablero */
  58.  
  59. int n, m, /* Filas y columnas; dimensión del tablero */
  60. solucion, /* Indica el camino de la solución */
  61. no_soluciones, /* Número de soluciones halladas */
  62. screen; /* Indica si la solución va a pantalla o a fichero */
  63.  
  64. int _X, _Y; /* Posición del cursor para la función crtprintf */
  65.  
  66.  
  67. /* Movimientos posibles del caballo: */
  68.  
  69. int a[] = {-2, -2, -1, -1, +1, +1, +2, +2}; /* Filas */
  70. int b[] = {-1, +1, -2, +2, -2, +2, -1, +1}; /* Columnas */
  71.  
  72.  
  73. /*-----------------------------------------------------------------------------
  74.  
  75. F U N C I O N E S D E L P R O G R A M A
  76.  
  77. -----------------------------------------------------------------------------*/
  78.  
  79. void pintar_tablero(void)
  80. {
  81. /* Pintar tablero */
  82. _X = 1;
  83. _Y = 1;
  84. crtprintf(" 0 1 2 3 4 5 6 7 ");
  85. crtprintf(" ███████ ███████ ███████ ███████ ");
  86. crtprintf(" 0███████ ███████ ███████ ███████ ");
  87. crtprintf(" ███████ ███████ ███████ ███████ ");
  88. crtprintf(" ███████ ███████ ███████ ███████ ");
  89. crtprintf(" 1 ███████ ███████ ███████ ███████ ");
  90. crtprintf(" ███████ ███████ ███████ ███████ ");
  91. crtprintf(" ███████ ███████ ███████ ███████ ");
  92. crtprintf(" 2███████ ███████ ███████ ███████ ");
  93. crtprintf(" ███████ ███████ ███████ ███████ ");
  94. crtprintf(" ███████ ███████ ███████ ███████ ");
  95. crtprintf(" 3 ███████ ███████ ███████ ███████ ");
  96. crtprintf(" ███████ ███████ ███████ ███████ ");
  97. crtprintf(" ███████ ███████ ███████ ███████ ");
  98. crtprintf(" 4███████ ███████ ███████ ███████ ");
  99. crtprintf(" ███████ ███████ ███████ ███████ ");
  100. crtprintf(" ███████ ███████ ███████ ███████ ");
  101. crtprintf(" 5 ███████ ███████ ███████ ███████ ");
  102. crtprintf(" ███████ ███████ ███████ ███████ ");
  103. crtprintf(" ███████ ███████ ███████ ███████ ");
  104. crtprintf(" 6███████ ███████ ███████ ███████ ");
  105. crtprintf(" ███████ ███████ ███████ ███████ ");
  106. crtprintf(" ███████ ███████ ███████ ███████ ");
  107. crtprintf(" 7 ███████ ███████ ███████ ███████ ");
  108. crtprintf(" ███████ ███████ ███████ ███████ ");
  109.  
  110. } /* end pintar_tablero */
  111.  
  112. void escribir_solucion( int blink )
  113. {
  114. int i,j;
  115.  
  116. for ( j = 0; j< n; j++ ) for (i= 0; i< m; i++) {
  117.  
  118. _crtprintf(i*7+16, j*3+3, ((i+j) % 2 ? AZUL:GRIS) + blink ,
  119.  
  120. "%d%s", *(tabla+j*m+i), *(tabla+j*m+i)/10 ? "":" " );
  121. }
  122. }
  123.  
  124. void tecla_pulsada(void)
  125. { int car;
  126.  
  127. car = getch(); if (car == 0) getch();
  128. else if (car == 27) {
  129. outportb( 0x3D9, 0 );
  130. textattr(7);
  131. clrscr();
  132. exit(0);
  133. }
  134. pintar_tablero();
  135. escribir_solucion( 0 );
  136.  
  137. } /* end tecla_pulsada */
  138.  
  139. void guardar_solucion(void)
  140. /*
  141. Añade al contenido de un fichero, el tablero
  142. con la solución actual.
  143. */
  144. {
  145. FILE *f; /* Fichero donde se guardan las soluciones */
  146. int i, j;
  147.  
  148. if ( (f = fopen("CABALLO.TXT", "a+t")) == NULL)
  149. f = fopen("CABALLO.TXT", "w+t");
  150.  
  151. for (j= 0; j< n; j++) {
  152. for (i= 0; i< m; i++) {
  153. fprintf(f, "%d %s", *(tabla+j*m+i),
  154. (*(tabla+j*m+i) > 9)? "":" " );
  155. }
  156. fprintf(f, "\n");
  157. }
  158. fprintf(f, "\n\n");
  159.  
  160. fclose(f);
  161.  
  162. } /* end guardar_solucion */
  163.  
  164.  
  165. /*-----------------------------------------------------------------------------
  166.  
  167. F U N C I O N P R I N C I P A L
  168.  
  169. -----------------------------------------------------------------------------*/
  170.  
  171. int prueba_y_error(int y, int x) /* fila y columna */
  172. /*
  173. Implementación del BACKTRACKING para el caballo.
  174. */
  175. {
  176. int i,j,k = -1, acertado = 0;
  177. char car;
  178.  
  179. do {
  180. /* Seleccionar siguiente movimiento */
  181. k++;
  182.  
  183. /* Si movimiento aceptable */
  184. if ( x+a[k]>=0 && x+a[k]<m && y+b[k]>=0 && y+b[k]<n && !*(tabla+(y+b[k])*m+x+a[k]) ) {
  185.  
  186. /* Anotar solución */
  187. *(tabla + (y+b[k])*m + x+a[k] ) = ++solucion;
  188.  
  189. /* Si solución no completa */
  190. if ( solucion < m*n) {
  191. acertado = prueba_y_error (y+b[k], x+a[k]);
  192.  
  193. /* Si movimiento no acertado */
  194. if (!acertado) {
  195.  
  196. /* Borrar solución */
  197. *(tabla + (y+b[k])*m + x+a[k] ) = 0;
  198. --solucion;
  199. }
  200. }
  201. else { /* Se ha encontrado una solución */
  202. no_soluciones++;
  203.  
  204. if (screen) {
  205. escribir_solucion( BLINK );
  206. if (getch() == 0) getch();
  207. escribir_solucion( 0 );
  208. }
  209. else guardar_solucion();
  210.  
  211. /* Borrar solución para hallar más */
  212. *(tabla + (y+b[k])*m + x+a[k] ) = 0;
  213. --solucion;
  214. }
  215. }
  216.  
  217. /* Escribir actual estado de la búsqueda */
  218. if (kbhit()) tecla_pulsada();
  219. }
  220. while (k < 8); /* Mientras no se examinen todas las posibilidades */
  221.  
  222. return(acertado);
  223.  
  224. } /* end prueba_y_error */
  225.  
  226.  
  227. /*-----------------------------------------------------------------------------
  228.  
  229. P R O G R A M A P R I N C I P A L
  230.  
  231. -----------------------------------------------------------------------------*/
  232.  
  233. main()
  234. {
  235. char car;
  236. int x, y, i, j;
  237.  
  238. do {
  239.  
  240. /* Presentación */
  241. textattr(AZUL); clrscr();
  242. outportb(0x3D9, GRIS); /* Pinta el borde de la pantalla */
  243. puts("Método del BACKTRACKING ( Prueba y error).");
  244. puts("-------------------------------------------"); puts("");
  245. puts("Tenemos un tablero de N x M y un caballo de ajedrez en una");
  246. puts("posición (x,y). Se trata de que el caballo sin saltar dos");
  247. puts("veces por el mismo sitio cubra todo el tablero. Para ello");
  248. puts("se utiliza un árbol de búsqueda en profundidad."); puts("");
  249. puts("-> Para terminar al programa durante su ejecución pulsar ESC.");
  250. puts("-> Este programa está pensado para adaptador de vídeo CGA.");
  251.  
  252.  
  253. /* Entrar dimensión del tablero */
  254. printf("\nEntrar dimensión del tablero:\n");
  255. printf("\nNúmero de filas [1..%d] = ", 8);
  256. do car = getch(); while ( car < '1' || car > '8' );
  257. putch(car);
  258. n= car - '0';
  259. printf("\nNúmero de columnas [1..%d] = ", 8);
  260. do car = getch(); while ( car < '1' || car > '8' );
  261. putch(car);
  262. m= car - '0';
  263. tabla = (char *)malloc((n * m + 1) * sizeof(char));
  264.  
  265.  
  266. /* Entrar posición inicial del caballo */
  267. printf("\n\nEntrar posición inicial del caballo en el tablero:\n");
  268. printf("\nFila [0..%d] = ", n-1);
  269. do car = getch(); while ( car < '0' || car >= '0'+n );
  270. putch(car);
  271. y= car - '0';
  272. printf("\nColumna [0..%d] = ", m-1);
  273. do car = getch(); while ( car < '0' || car >= '0'+m );
  274. putch(car);
  275. x= car - '0';
  276.  
  277. /* Mostrar las soluciones en pantalla o guardarlas en un fichero */
  278. printf("\n\n ¿ Guardar las soluciones en un fichero (S/N) ? ");
  279. do car = getch(); while (car != 'S' && car != 'N' && car != 's' && car != 'n');
  280. if (car == 's' || car == 'S') {
  281. screen = 0; puts("Sí");
  282. }
  283. else { screen = 1; gotoxy(1,wherey());
  284. printf("La solución se mostrará en pantalla."); clreol();
  285. delay( 1500 );
  286. pintar_tablero();
  287. }
  288. gotoxy( 80, 25 );
  289.  
  290.  
  291. /* Inicializar los movimientos posibles. */
  292. for (j= 0; j< n; j++) for (i= 0; i< m; i++) *(tabla+j*m+i)= 0;
  293.  
  294.  
  295. /* Anotar primera posición y hallar la solución. */
  296. solucion = no_soluciones = 0;
  297. *(tabla + y*m + x) = ++solucion;
  298. prueba_y_error( y, x );
  299.  
  300. /* Escribir el número de soluciones halladas */
  301. clrscr();
  302. switch(no_soluciones) {
  303. case 0: printf("==> No se ha encontrado ninguna solución."); break;
  304. case 1: printf("==> Sólo se halló una solución correcta."); break;
  305. default: printf("==> Se han hallado %d soluciones distintas.", no_soluciones );
  306. }
  307.  
  308. } while (getch() != 27); /* ESC */
  309.  
  310. outportb( 0x3D9, 0 );
  311. textattr(7);
  312. clrscr();
  313.  
  314. } /* end main */
  315.  
  316.  
  317. /*-----------------------------------------------------------------------------
  318.  
  319.   I M P L E M E N T A C I O N D E F U N C I O N E S A U X I L I A R E S
  320.  
  321. -----------------------------------------------------------------------------*/
  322.  
  323.  
  324. unsigned char gettextmode(void) /* devuelve actual modo de pantalla */
  325.  
  326. { _AH = 15; geninterrupt(0x10); return(_AL);
  327. }
  328.  
  329. void activarpagina( char pag ) /* activa súbitamente una página */
  330.  
  331. { _AH = 5; _AL = pag; geninterrupt(16);
  332. }
  333.  
  334. unsigned char charforline(void) /* carácteres por línea de pantalla */
  335.  
  336. { _AH = 15; geninterrupt(0x10); return(_AH);
  337. }
  338.  
  339. int getpagina(void) /* Devuelve actual página de visualización */
  340.  
  341. { _AH = 15; geninterrupt(0x10); return(_BH);
  342. }
  343.  
  344. unsigned int pagina(unsigned char pag) /* gettextmode, charforline */
  345. /*
  346. Retorna dirección de memoria de cierta página.
  347. No se contemplan los modos gráficos.
  348.  
  349. */
  350. { unsigned int mem, cte;
  351.  
  352. /* Distancia de una página a su consecutiva: */
  353.  
  354. if ( charforline() == 80) /* 80 ó 40 columnas */
  355. { cte = 0x100; /* Próxima dirección de página */
  356. pag %= 4; /* Hay cuatro páginas cómo máximo */
  357. } else
  358. { cte = 0x80;
  359. pag %= 8; /* Hay ocho páginas como máximo */
  360. }
  361.  
  362. /* Comienzo de memoria de pantalla: */
  363.  
  364. if ( gettextmode() == 7)
  365. mem = 0xB000; /* Adaptador monocromo */
  366. else
  367. mem = 0xB800; /* Adaptador CGA */
  368. return(mem + pag * cte);
  369.  
  370. } /* fin pagina */
  371.  
  372.  
  373. void crtputs(int x, int y, char *s, int color)
  374. /*
  375. Imprime una cadena escribiendo en memoria de vídeo.
  376. Si el color es negativo entonces no lo escribe.
  377. Funciones utilizadas: charforline, pagina, getpagina
  378. */
  379. { register int i;
  380. unsigned int k, segmento;
  381.  
  382. k = --y*2*charforline();
  383. x--;
  384. segmento = pagina( getpagina());
  385.  
  386. for (i = x; *s; i++) {
  387. pokeb( segmento,i*2 + k, *s++ );
  388.  
  389. if ( color >= 0 )
  390. pokeb( segmento,i*2 + k+1, color );
  391. }
  392. } /* end crtputs */
  393.  
  394.  
  395. int crtprintf ( char *fmt, ... )
  396. /*
  397. Salida formateada, escribiendo directamente en
  398. memoria de vídeo.
  399. No altera el cursor actual. No altera el color de fondo.
  400.  
  401. _X , _Y son variables globales.
  402. */
  403. {
  404. va_list argptr;
  405. char str[256];
  406. int cnt;
  407.  
  408. va_start( argptr, format );
  409.  
  410. cnt = vsprintf( str, fmt, argptr );
  411.  
  412. crtputs ( _X, _Y, str, -1);
  413.  
  414. /* _X = _X + strlen( str );
  415. */
  416. ++_Y;
  417.  
  418. va_end( argptr );
  419.  
  420. return( cnt );
  421.  
  422. } /* end crtprintf */
  423.  
  424. int _crtprintf ( int x, int y, int color, char *fmt, ... )
  425. /*
  426. Salida formateada, escribiendo directamente en
  427. memoria de vídeo.
  428. No altera el cursor actual. No altera el color de fondo.
  429. */
  430. {
  431. va_list argptr;
  432. char str[256];
  433. int cnt;
  434.  
  435. va_start( argptr, format );
  436.  
  437. cnt = vsprintf( str, fmt, argptr );
  438.  
  439. crtputs ( x, y, str, color);
  440.  
  441. va_end( argptr );
  442.  
  443. return( cnt );
  444.  
  445. } /* end _crtprintf */
  446.  
  447.  
  448. /* FIN DEL FICHERO FUENTE */
  449.  

Proinf.net