Foro de elhacker.net

Buenas a todos, me interesaría alguna idea para desarrollar un algoritmo de resolución de sudokus usando algún tipo de heurística que mejore por ejemplo algún método de backtracking.

Un saludo, si queréis mas info preguntad.

Mira si lo implementas en Prolog, que es programación lógica, el problema esta muy sencillo de resolver, si lo hacemos en otro paradigma es mas complicado.

.
Investiga METODOS de resolucion, mi padre me enseño un metodo de resolucion vertical, por falta de tiempo no te lo puedo poner (ya es media noche por aquí), pero te dejo uno que estaba creando con BackTracking esta en vb6.

http://foro.elhacker.net/programacion_visual_basic/reto_sudoku-t339671.0.html;msg1666771#msg1666771


No lo creo, si lo puedes programar en un lenguaje seguro se puede transladar a otro, ya que TODOS los lenguajes nesesitan de LOGICA para programar. Tengo en claro de donde reside el nombre de Prolog y para que se usa es por ello que realizo este comentario.

Dulces Lunas!¡.

Se me olvidó comentar que debo hacerlo en Java, así que lenguajes de tipo declarativo como prolog no me sirven.

Aprovecho para recalcar, no necesito el algoritmo, ya que si no no aprendería nada, lo que me gustaría es tener alguna idea para agregar una heurística al método de backtracking, para que de esta forma tome menos tiempo en resolverlo.

Muchas gracias, pero esto es backtracking pelado, es decir, no usa ninguna heurística para guiar la búsqueda de la solución.

Por ejemplo, una heurística mala sería, mantener en memoria un vector, en el que se almacene el número de veces que se han asignado todos los números, es decir:

1 -> 2 veces
2 -> 4 veces
.
.
.


etc, y en una casilla, cuando obtengamos los números posibles para asignar, por ejemplo:

5 -> 3 veces
8 -> 9 veces

elegiremos el 5, ya que estadísticamente, es mas probable que este número sea el correcto, en lugar del 8.

No se si me explico.

Gracias a todos por contestar, un saludo.

Yo nunca dije que no se pudiera programar en otro paradigma, y si cualquier lenguaje de programación que cuente con control de flujo podrá resolver cualquier problema ya antes resuelto en otro paradigma.

.
Entonces usa el metodo de Ramificación y poda.

Dulces Lunas!¡.