Tareasss

La vuelta del caballo
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. Una variante es obligar al caballo a volver a la posición de partida en elúltimo movimiento.
Por último se estudiará como encontrar todas las soluciones posibles partiendo de una misma casilla.
Para resolver el problema hay que realizar todos los movimientos posibles hasta que ya no se pueda avanzar, en cuyo caso hay que dar marcha atrás, o bien hasta que se cubra el tablero. Además, es necesario determinar la organización de los datos para implementar el algoritmo.
-¿Cómo se mueve un caballo?. Para aquellos que no sepan jugar al ajedrez se muestra un gráfico con los ocho movimientos que puede realizar. Estos movimientos serán los ocho candidatos.

Con las coordenadas en las que se encuentre el caballo y las ocho coordenadas relativas se determina el siguiente movimiento. Las coordenas relativas se guardan en dos arrays:
ejex = [2, 1, -1, -2, -2, -1,   1, 2]
ejey = [1, 2,  2,  1,  -1, -2, -2, -1]
El tablero, del tamaño que sea, se representará mediante un array bidimensional de números enteros. A continuación se muestra un gráfico con un tablero de tamaño 5x5 con todo el recorrido partiendo de la esquina superior izquierda.

 
Cuando se encuentra una solución, una variable que se pasa por referencia es puesta a 1 (cierto). Puede hacerse unavariable de alcance global y simplificar un poco el código, pero esto no siempre es recomendable.
Para codificar el programa, es necesario considerar algunos aspectos más, entre otras cosas no salirse de los límites del tablero y no pisar una casilla ya cubierta (selección del candidato). Se determina que hay solución cuando ya no hay más casillas que recorrer.
A continuación se expone un códigocompleto en C, que recubre un tablero cuadrado de lado N partiendo de la posición (0,0).
#include <stdio.h>

#define N 5
#define ncuad N*N

void mover(int tablero[][N], int i, int pos_x, int pos_y, int *q);

const int ejex[8] = { -1,-2,-2,-1, 1, 2, 2, 1 },ejey[8] = { -2,-1, 1, 2, 2, 1,-1,-2 };

int main(void)
{
int tablero[N][N]; /* tablero del caballo. */
int i,j,q;

/* inicializa el tablero a cero */
for (i = 0; i < N; i++)
for (j = 0; j < N; j++)tablero[i][j] = 0;

/* pone el primer movimiento */
tablero[0][0] = 1;
mover(tablero,2,0,0,&q);

if (q) { /* hay solucion: la muestra. */
for (i = 0; i < N; i++) {
for (j = 0; j < N; j++)printf("%3d ", tablero[i][j]);
putchar('\n');
}
}
else
printf("\nNo existe solucion\n");

return 0;
}

void mover(int tablero[][N],int i, int pos_x, int pos_y, int *q)
{
int k, u,v;

k = 0;
*q = 0;
do {
u = pos_x + ejex[k]; v = pos_y + ejey[k]; /* seleccionar candidato */
if (u >= 0 && u < N && v >= 0 && v < N) { /* esta dentro de los limites? */
if (tablero[u][v] == 0) { /* es valido? */...