/*
+-------------------+
| 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 ("\n\nVUELTA 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 ("\n\n");
  ensayar (2, x0, y0);

  if (movimiento_acertado)
    for (printf ("\n\nLA SOLUCION ES:\n  "), i = 1; i <= n; i++)
      {
        for (j = 1; j <= n; j++)
          printf ("%2d ", tab (i, j));
        printf ("\n  ");
      }
  else
    printf ("\n\nNO 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): "
              "%ld\r", ++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);
}