Programación General > C/C++
Re: TABLERO DE AJEDREZ
(1/1)
Juan Pablo:
AYUDA!!!!!!!!!!!
NESECITO HACER UN PROGRAMA PARA TURBO C, SOBRE UN TABLERO DE AJEDREZ EN DONDE SE MUEVA EL CABALLO (MOVIMIENTO EN L) POR TODOS LOS CASILLEROS SIN PASAR POR EL MISMO CASILLERO.
SI NO ME AYUDAN ME ECHO EL RAMO....AYUDA!!!!!!!!!!!!!!:(
adocrates:
Espero que te sirva...
--- Código: Text ---/*+-------------------+| SALTO DEL CABALLO |+-------------------+ Este programa realiza lo siguiente: Se da un tablero de nxncon n*n cuadros. Un caballo -que puede moverse según las reglas delajedrez- se sitúa en el cuadro de coordenadas (x0,y0). Se pideencontrar, si existe, un recubrimiento del tablero completo, o sea,calcular un circuito de n*n-1 movimientos de forma que cada cuadrodel tablero sea visitado exactamente una vez. La solución a este problema está basado en el método detanteo sistemático (intento y error). La función más importante es ensayar() cuyo pseudocódigo esel 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 dediferencias. Los vectores de diferencia dif_x y dif_y contienen ladiferencia de la coordenada x e y respectivamente desde la posiciónactual 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 8respresentan los 8 posibles movimientos. El primer movimiento seobtiene: x2 = x1 + 2; y2 = y1 + 1; 3) La macro tab() se utiliza para trabajar con los índices de 1a n en la matriz del tablero en vez de con los índices reales 0 an-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 ladimensión del tablero. 5) El significado de las asignaciones a los elementos de lamatriz 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 deencontrar la solución es muy lento. Por eso se ha puesto el límiteen 8 aunque ya con este número el proceso es superlento (en términosde media, ya que puede dar la casualidad de que se encuentre lasolució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);}
adocrates:
--- Código: Text ---#include <stdio.h> #define N_CUADROS 8#define N_SALTOS 8#define CIERTO 1#define FALSO 0 static int tablero_virtual[N_CUADROS+4][N_CUADROS+4];static int dx[N_SALTOS]={ 2, 1,-1,-2,-2,-1, 1, 2};static int dy[N_SALTOS]={ 1, 2, 2, 1,-1,-2,-2,-1}; static void inicia_tablero(void);void presenta_tablero(void);static int ensaya_movimiento(int n,int x,int y); int main(void){ inicia_tablero(); printf("ncalculando, espere por favorn"); if(ensaya_movimiento(1,2,2)) printf("Resultado:"); else printf("No hay soluci¢n"); presenta_tablero(); return 0;} static void inicia_tablero(void){ int i,j; for(i=0;i<N_CUADROS+4;i++) { for(j=0;j<N_CUADROS+4;j++) { if(i>1 && i<N_CUADROS+2 && j>1 && j<N_CUADROS+2 ) tablero_virtual[i][j]=0; else tablero_virtual[i][j]=-1; } } } void presenta_tablero(void){ int i,j; for(i=0;i<N_CUADROS+4;i++) { printf("n"); for(j=0;j<N_CUADROS+4;j++) { if(tablero_virtual[i][j]!=-1) printf("%4d",tablero_virtual[i][j]); } } return;} static int ensaya_movimiento(int n,int x,int y){ int i,u,v; tablero_virtual[x][y]=n; if(n==(N_CUADROS*N_CUADROS)) return CIERTO; else { for(i=0;i<N_SALTOS;i++) { u=x+dx[i]; v=y+dy[i]; if(tablero_virtual[u][v]==0) { if(ensaya_movimiento(n+1,u,v)) return CIERTO; } } } tablero_virtual[x][y]=0; return FALSO;}
Navegación
Ir a la versión completa