¡Envia tu foto al Fotomaton!
Volviendo hacia atrás en el blog algunas semanas -haciendo backtracking-, comentaba el uso de la recursividad en la programación y lo interesante que resultaba definir algo contenido en la misma definición.
El Backtracking es una técnica de programación de la que se puede partir de la definición de Recursividad (vease definición de recursividad) con la diferencia que, en el backtracking, al existir varios caminos diferentes a elegir, una vez llegado al final y no cumplirse la condición establecida, volvemos atrás para seguir buscando caminos diferentes o alternativos y posiblemente correctos.
La idea del backtracking, si aún no la has entendido, se ve bastante bien en estos ejemplos del Laberinto y las n-Damas (en Java).
Finalmente, como lo prometido es deuda, subo la práctica comentada en el anterior artículo sobre recursividad que resuelve sudokus planteados por medio de la técnica del backtracking. Recordar que no es la mejor técnica ni mucho menos para resolver Sudokus, sino prácticamente usar la fuerza bruta para resolverlos con la posibilidad de volver atrás y buscar más caminos.
El programa está realizado para Free Pascal y permite:
Hay bastante cosas que son mejorables, como por ejemplo quitar algunas variables globales o la inclusión de eliminar algunos números insertando un cero (por ejemplo), pero eso lo dejo para el que quiera modificarlo, asi como el que se anime y lo «traduzca» a otro lenguaje de programación estaré encantado en incorporarlo al artículo.
Programa para resolver sudokus en Free Pascal con algunos ficheros de ejemplo.
10 Comentarios
[...]una vez llegado al final y no cumplirse la condición establecida, volvemos atrás para seguir buscando caminos diferentes o alternativos y posiblemente correctos[...]
Ojo! que no se cumpla la condicion establecida no quiere decir que no haya encontrado una posible solucion. Existen varios tipos de backtracking, por ejemplo para encontrar la solucion óptima, asi que puede haber llegado a una solucion pero aun asi seguir buscando para ver si hay otra mejor.
Lo cierto es que el backtracking por sí sólo no es una técnica muy querida por los programadores, ya que es bastante ineficiente, en el peor de los casos es tan ineficiente como un procedimiento recursivo normal. Sin embargo, se utiliza en algunos algoritmos, por ejemplo, utilizando la técnica de ramificación y poda de árboles de soluciones, en la que se va acotando una posible solución según se va realizando la recursividad. El bactracking se aplica en este caso cuando nuestra cota superior o inferior no mejoraría un resultado anterior, con lo que nos ahorramos bastantes llamadas recursivas ;) (Véase MTP2 o Xtreme Loonies xD)
Sí, el backtracking, dado lo que consume debería llamarse "backtranking" ;)
Me acabas de salvar el culo amigo!!
Estoy con pascal y para mi es impresionante que no tenga ni idea de programación y me manden hacer un "resuelve sudokus por bactraking". Si te conociera te invitaría a una cerveza y unas bravas.
XD!
GRACIAS!!!
La pregunta es cual seria la funcion de estimacion del algoritmo del tipo de ramificacion y poda para poder evitarme unas cuantas llamadas recursivas?
como podria seleccionar que jugadas me llevarian antes a la solución?
gracias
La pregunta es cual seria la funcion de estimacion del algoritmo del tipo de ramificacion y poda para poder evitarme unas cuantas llamadas recursivas?
como podria seleccionar que jugadas me llevarian antes a la solución?
gracias
Ser o n o ser ?
La verdad es que lo de la solucion de sudokus, es una cuestion que se acaba de poner de moda para los profesores de informatica, llevo ya dos años que no me dejan tranquilo con los benditos sudokus, ya los odio mucho.
Cada algoritmo tiene sus ventajas, asta lo que tengo mirado hasta ahora(backtraking, ramificacion y poda, y dancing links), backtraking es el que todos entendemos, ramificacion y poda no esta mal pero lo veo que para un sudoku gasta demasiada memoria, y dancing links lo veo demasiado jodido de implementar, tengo que hacer un sudoku en C++ y dos imlementaciones graficas en qt y gtkmm y me voy a volver loco , asi que si veis una buena documentacion porfavor os agradeceria que me la pasarais a mi blog
Se puede usar el backtraking en prolog?? y cual es la sintaxis?? alguien me podria or favor contestar :)=
Por supuesto que se puede utilizar el backtraking en prolog.
en Internet.
Envia tu fotografía al fotomatón de Emezeta. Puedes enviar varias y saldrás en la portada de Emezeta.
Suscripción gratuita
Sigue los artículos de Emezeta blog.
Me llamo José Román, aka Manz. Soy estudiante
de ingeniería informática en la ULL y vivo en Santa
Cruz de Tenerife. Emezeta blog es mi rincón de la red, en él escribo artículos acerca de
tecnología, curiosidades, informática y todo ello sin olvidar el humor.
Si quieres saber más sobre mi, haz clic en ¿Quién es Manz?. Si lo deseas, también puedes ver mi CV o enviarme un mensaje para contactar conmigo.
Si te interesa el contenido de Emezeta blog, puedes suscribirte en Bloglines, Google o cualquier otro sindicador de contenidos.
Puedes recibir los artículos directamente en tu e-mail si lo deseas:
Si quieres dejar un comentario acerca del artículo, pulsa aquí. Mediante este formulario enviarás un e-mail privado al autor del blog (tu mensaje no será publicado en este sitio). Asegurate de escribir tu e-mail para poder responderte:
¡OJO! Me encanta recibir emails pero no me da tiempo de contestarlos todos. ¡Paciencia! Aunque tarde, siempre los contesto.
Jesús MéndezBuenas tardes desde Tenerife Sur (Los Cristianos). La verdad que me metí en este b...
phynetNah, la cosa es Febrero 19 de 2008 xD Pero visto así, impresiona......
JavierSaludos a todos. Si se dan cuenta la fecha es 19 de febrero de 2008, utilizaron 2 ...
Nacho 001Madre mia.......
dayaniKiero poenr mi foto en photoshop y no puedo ayudenme porfavor :( ...
¿Quieres anunciar un producto? Sé analizado en Emezeta blog mediante la red Zync. Emezeta blog tiene más de 650.000 páginas vistas al mes.
Muestra fotos o webcam.
Tus fotos en la portada de una revista:
Si te gusta este sitio, puedes colocar un enlace a Emezeta blog en tu página web o blog, pegando el siguiente código:
Alojado en MediaTemple.
10 consultas efectuadas / Página generada en 0.047 segundos
Programado íntegramente por José Román (Manz) en XHTML y CSS estándar.
Sindicado bajo Feed RSS. Contenido bajo licencia Creative Commons
Estadísticas de visitas · Términos y condiciones · Contacto · Publicidad · Preguntas frecuentes (FAQ)
