/*
+-------------------+
| SALTO DEL CABALLO |
+-------------------+
Este programa realiza lo siguiente: Se da un tablero de nxn
con n*n cuadros. Un caballo -que puede moverse según las reglas del
ajedrez- se sitúa en el cuadro de coordenadas (x0,y0). Se pide
encontrar, si existe, un recubrimiento del tablero completo, o sea,
calcular un circuito de n*n-1 movimientos de forma que cada cuadro
del tablero sea visitado exactamente una vez.
La solución a este problema está basado en el método de
tanteo sistemático (intento y error).
La función más importante es ensayar() cuyo pseudocódigo es
el siguiente:
<PRINCIPIO ensayar>
REPETIR seleccionar el nuevo candidato de la lista de futuros
movimientos
SI aceptable ENTONCES
SI tablero no lleno ENTONCES
LLAMAR ensayar nuevo movimiento
SI no acertado ENTONCES
borrar la anotación anterior
FINSI
FINSI
FINSI
HASTA movimiento acertado O no hay más posibilidades
<FIN>
Observaciones sobre el código:
1) Estudiar la función ensayar() a partir de este pseudocódigo.
2) El método utilizado para obtener el movimiento del caballo de
(x1,y1) hasta (x2,y2) es sumar a (x1,y1) los vectores de
diferencias.
Los vectores de diferencia dif_x y dif_y contienen la
diferencia de la coordenada x e y respectivamente desde la posición
actual del caballo.
Veáse con el siguiente tablero:
0 6 0 7 0
5 0 0 0 8
0 0 C 0 0
4 0 0 0 1
0 3 0 2 0
C representa la posición del caballo; los números del 1 al 8
respresentan los 8 posibles movimientos. El primer movimiento se
obtiene: x2 = x1 + 2; y2 = y1 + 1;
3) La macro tab() se utiliza para trabajar con los índices de 1
a n en la matriz del tablero en vez de con los índices reales 0 a
n-1.
4) La condición ®tablero no lleno¯ se expresa mediante ®i < n*n¯
donde i es el número de movimiento del caballo actual y n la
dimensión del tablero.
5) El significado de las asignaciones a los elementos de la
matriz es:
tab (x, y) = 0; /* el cuadro <x,y> no ha sido visitado */
tab (x, y) = i; /* el cuador <x,y> ha sido visitado en el
movimiento i-ésimo (1 ó i ó n*n) */
NOTA: Con un dimensión de la matriz superior a 4, el proceso de
encontrar la solución es muy lento. Por eso se ha puesto el límite
en 8 aunque ya con este número el proceso es superlento (en términos
de media, ya que puede dar la casualidad de que se encuentre la
solución en los primeros intentos).
*/
/* Ficheros a incluir: */
#include <stdio.h> /* printf () */
#include <conio.h> /* getch () */
#include <stdlib.h> /* exit () */
/* Macros: */
#define NUM_MOVIMIENTOS_POSIBLES 8
#define NMAXIMO 8
#define BOOLEAN int
#define TRUE 1
#define FALSE 0
#define ESC 27
#define en(x,x1,x2) ((x) >= (x1) && (x) <= (x2))
#define tab(i,j) tablero[(i)-1][(j)-1] /* tab(1,1) es en realidad
tablero[0][0] */
/* Variables globales: */
int n, tablero[NMAXIMO][NMAXIMO];
BOOLEAN movimiento_acertado;
int dif_x [NUM_MOVIMIENTOS_POSIBLES] =
{ 2, 1, -1, -2, -2, -1, 1, 2 },
dif_y [NUM_MOVIMIENTOS_POSIBLES] =
{ 1, 2, 2, 1, -1, -2, -2, -1 };
/* Prototipos de las funciones: */
void proceso (void);
void ensayar (int i, int x, int y);
/* Definiciones de las funciones: */
void main (void)
{
do
{
printf ("nnVUELTA DEL CABALLO:n ");
proceso ();
printf ("nPulsa cualquier tecla para repetir "
"o ESC para salir. ");
} while (getch () != ESC);
}
void proceso (void)
{
register int i, j;
int x0, y0;
for (i = 1; i <= n; i++)
for (j = 1; j <= n; j++)
tab (i, j) = 0;
printf ("nIntroduce dimensión del tablero (1 ó n ó %d, n > 4 es "
"muy lento): ", NMAXIMO);
do
{
n = getch () - '0';
} while (! en (n, 1, NMAXIMO));
putch (n + '0');
printf ("nFila inicial (1 ó x ó %d): ", n);
do
{
x0 = getch () - '0';
} while (! en (x0, 1, n));
putch (x0 + '0');
printf ("nColumna inicial (1 ó y ó %d): ", n);
do
{
y0 = getch () - '0';
} while (! en (y0, 1, n));
putch (y0 + '0');
tab (x0, y0) = 1;
printf ("nn");
ensayar (2, x0, y0);
if (movimiento_acertado)
for (printf ("nnLA SOLUCION ES:n "), i = 1; i <= n; i++)
{
for (j = 1; j <= n; j++)
printf ("%2d ", tab (i, j));
printf ("n ");
}
else
printf ("nnNO HAY SOLUCION.n");
}
void ensayar (int i, int x1, int y1)
{
int movimientos_realizados = 0;
int x2, y2;
const ncuadrado = n * n;
static long unsigned num_movimientos_caballo = 0;
do
{
movimiento_acertado = FALSE;
x2 = x1 + dif_x[movimientos_realizados];
y2 = y1 + dif_y[movimientos_realizados];
movimientos_realizados++;
if (kbhit ())
if (getch () == ESC)
exit (1);
printf ("Número de movimientos del caballo (ESC para salir): "
"%ldr", ++num_movimientos_caballo);
if (en (x2, 1, n) && en (y2, 1, n) && tab (x2, y2) == 0)
{
tab (x2, y2) = i;
if (i < ncuadrado)
{
ensayar (i+1, x2, y2);
if (! movimiento_acertado)
tab (x2, y2) = 0;
}
else
movimiento_acertado = TRUE;
}
} while (! movimiento_acertado &&
movimientos_realizados != NUM_MOVIMIENTOS_POSIBLES);
}
