Evidencia1progra


Universidad Politécnica del Valle de México

Ingeniería en informática

Evidencia 1: Desarrollo de practica de algoritmo Backtracking


Integrantes: José Antonio BlasCampos

Grupo: 851

Matrícula: 1311120021

Asignatura: Programación Avanzada


Tultitlan Estado De México a 12 de Febrero de 2015




1. Elaborar la solución de los siguientes problemas

1.1Problema del salto del caballo
Problema: El salto del caballo consiste en que dada una posición inicial en un tablero de ajedrez, se debe recorrer todas las casillas del tablero únicamente con losmovimientos del caballo sin repetir ninguna casilla. Partiendo de la idea de que el caballo puede mover como máximo a 8 posiciones diferentes Si una posición se queda sin posibles siguientes movimientos,volver a la anterior posición y probar la siguiente posible.
Para solucionar este problema se han diseñado numerosos Algoritmos como lo son genéticos, búsqueda local con resolución de conflictos,programación entera, matriz nxn, resolución paralela, resolución secuencial (backtraking)




Un recorrido del caballo es una secuencia de saltos , sin repetir casillas, desde una casillainicial hasta otra final, desde la cual no se puede avanzar, sin pasar por una casilla ya visitada, llamamos tamaño al numero de casillas que visita y longitud al numero de saltos que da


1.2. Codigodel salto del caballo
import java.io.*;
import java.io.BufferedReader;
import java.io.InputStream;

public class Caballo {
public static void main(String[] ar) {
int x, y;
booleansolucion;
BufferedReader entrada = new BufferedReader
(new InputStreamReader(System.in));
try {
System.out.println("Posicion inicial del caballo. ");System.out.print(" x = ");
x = Integer.parseInt(entrada.readLine());
System.out.print(" y = ");
y = Integer.parseInt(entrada.readLine());

CaballoSaltador miCaballo = new...