Ayuda con un programa en C

Tengo un programa que va de sudokus... si kieres te lo paso, a lo mejor te sirve para algo.
Mañana analizo el problema, que ahora no me da tiempo.

Mi msn (el malo) elit.darkknights AT gmail PUNTO com

yasta agregado pero sa tenido que ir!!

Alguien más por ahi con ganas de lanzar un cable?? :S

clona matrices en las vueltas recursivas, no machaques cosas por referencia a lo burro en backtracking, corres riesgos de cargarte algo, en cada llamada recursiva debes trabajar con copias de las originales, y en vez de pasar indices de la matriz, hazte un metodo que te de la primera casilla vacia, ahorra bastantes quebraderos de cabeza, yo tengo uno en java asi y va muy majo.

demnim escribió:clona matrices en las vueltas recursivas, no machaques cosas por referencia a lo burro en backtracking, corres riesgos de cargarte algo, en cada llamada recursiva debes trabajar con copias de las originales

No sé si te he entendido bien, ¿pero no es muy ineficiente clonar la matriz en cada llamada recursiva?

kNo escribió:No sé si te he entendido bien, ¿pero no es muy ineficiente clonar la matriz en cada llamada recursiva?

si, pero si no lo haces estas tocando una matriz de pasos anteriores y jodes el algoritmo porque matas la vuelta atras.

demnim escribió:
si, pero si no lo haces estas tocando una matriz de pasos anteriores y jodes el algoritmo porque matas la vuelta atras.

Yo lo tengo hecho con Java también y no he necesitado eso. Cada vez que vas a hacer una llamada recursiva, añades el número y lo vuelves a quitar si vuelves de la llamada (lo que se llama marcar y desmarcar), para poder añadir el siguiente en la siguiente vuelta del bucle, no sé si me explico, pero si no se entiende puedo buscar el código.
Solo he necesitado clonar la matriz cuando quiero saber si tiene solución, pero sin que lo resuelva.

es otra forma, yo me he ajustado a un esquema de backtracking puro.
me resulta menos complicado hacer eso que marcar/desmarcar.
ademas al tener tamaños acotados la complejidad no varia, ya es exponencial por si misma aunque algo acotada.

Bueno, es mejor empezar a manejarse con estas cosas con los problemas fáciles que esperar a que se presente uno difícil.
De todas formas tampoco tiene ninguna complejidad en este caso, con una función que añada un número al sudoku (que viene muy bien para muchas funciones), metes el que sea antes de las llamadas y después le metes un 0 en la misma posición (o lo que tengas por defecto para las casillas vacías).
Y lo de que no varía la complejidad pues según como lo mires, también puedes decir que en vez de exponencial es constante (9^81), que no es mentira, pero... xD.

No asignas la variable finAux a false en el inicio de la función Sudoku_VA.
De hecho no se ni para qué necesitas finAux, si fin cumple la función perfectamente al pasarla por referencia.

Por cierto, ese algoritmo no "resuelve" un sudoku (que se hace basándose en reglas) sino en resolver asignando números al azar. Básicamente estás resolviendo un cuadrádo mágico.