Credit image

¿Te gusta el diseño web? ¡Echa un vistazo a la documentación de LenguajeCSS.com!

Backtracking: Volviendo atrás

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:

  • Insertar números uno a uno (comprobando si es posible insertar el número según las reglas)
  • Cargar y salvar en un fichero de tipo propio los sudokus creados
  • Intentar resolver el sudoku mediante backtracking indicandote si tiene varias, única o ninguna solución y calculando el tiempo que tarda en resolverlo.
  • Borrar el sudoku actual del panel
  • Insertar un sudoku predefinido por coordenadas (ojo! este no comprueba si los números son válidos).

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.

Escrito por Manz, el , en programacion. Comentarios recibidos: 13.

13 comentarios de lectores
Driadan
Driadan
1

[...]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.

Ruyk
Ruyk
2

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)

Geekdraz
Geekdraz
3

Sí, el backtracking, dado lo que consume debería llamarse "backtranking" ;)

Kenji
Kenji
4

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!!!

pashanguita
pashanguita
5

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

pashanguita
pashanguita
6

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

chimichorro
chimichorro
7

ser o n o ser ?

dark soul
dark soul
8

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

car105
car105
9

se puede usar el backtraking en prolog?? y cual es la sintaxis?? alguien me podria or favor contestar :)=

rexodor
rexodor
10

por supuesto que se puede utilizar el backtraking en prolog.

Damian
Damian
11

He encontrado una web que para mi es sin duda la mejor en cuanto a información, articulos y ejemplos de backtracking, aqui os dejo la referencia: http://amigosdeloajeno.mihost.eu/category/programacion/c/mis-codigos/

L u L o
L u L o
12

@Geekdraz: hola MZ, gracias por todo, soy de argentina. pero no entiendo nada.. no se si pegarme un tiro.. estoy preocupado.. no se si cortarme una mano. (la mano de dios) saludos

  • 1
Kurai
Kurai
13

Odio el backtraking y programar (época de exámenes, lo odio todo...). Muchas gracias por tu web, me está siendo de bastante utilidad. Por cierto, te sigo en twitter. Un saludo!

Publica tu opinión

Si lo deseas, puedes utilizar el siguiente formulario para publicar tu opinión o responder a alguna de las existentes:

Previsualización

Aquí se previsualizará su comentario. Revise que sea correcto antes de publicarlo.