Retos programación

LOc0

Me explico. Al leer el sudoku y al imprimirlo estaba poniendo los valores de la x en la y, y los valores de la y en la x (sudoku[casilla/9][casilla%9] debería haber sido sudoku[casilla%9][casilla/9]) Funcionaba todo bien, pero las filas se consideraban columnas y al revés. Ahora tarda la mitad por fuerza bruta porque da la casualidad de que llega antes a la solución de ese sudoku haciendo la fuerza bruta columna por columna, y al estar ahora el sudoku bien guardado en memoria, empieza columna por columna (Antes sólo parecía que iba por columnas, pero en realidad iba por filas al estar volteado el sudoku en memoria.)

Como estamos buscando todas las soluciones realmente da igual, porque aunque encuentre la única antes seguirá probando hasta que no encuentre más.

Ya te echaba de menos en este hilo Soleil :P

Salu2 ;)

elkaoD

Humm, ¿Entonces por qué un mismo sudoku en formas simétricas tiene tiempos diferentes de resolución aún aplicando sólo fuerza bruta?

Soleil

#31 no podía faltar : -P

grivcon

la practica que han mandado este cuatrimestre en progI:
http://www.infor.uva.es/cvaca/WebPrI/docs/prprog0809.pdf

Yo la hice sin fuerza bruta, haciendo arboles.

elkaoD

Si generas un árbol usando recursividad, al fin y al cabo es fuerza bruta.

grivcon

no asigné a cada celda todos los valores y comprobé si cumplian las reglas, sino que celda a celda ponia un valor que por construccíon las respeta, por lo tanto no tiene que hacer miles y miles de combinaciones y me tarda en resolverlo menos de un segundo. A un compañero que lo hizo por fuerza bruta, le tardaba en algunos casos unos 5 minutos.

Poisonous

#36 Pues eso, backtracking con una funcion "es_factible"

LOc0

#32

Pues no tiene sentido. Explícate mejor porque he mirado tu código y no veo que leas el sudoku cambiando filas por columnas. Las filas se saca dividiendo casillas/9 y la columna con el resto, es decir casillas%9 tal y como tienes en tu código. Por otro lado, ¿a qué te refieres con sudoku simétrico? ¿Cambiar filas por columnas? (Eso en realidad sería sudoku traspuesto, pero es igual). Lo dicho, explícate para poder ver qué pasa.

#36
Al final, si quieres sacar todas las soluciones y tienes un sudoku "cabrón" no te queda más remedio que usar prueba/error (es decir, backtracking). Por ejemplo, imagina que tienes un sudoku con 3 huecos y en cada hueco los candidatos factibles son (1,2,3,4), (1,2, 4, 5) y (3, 1,5) respectivamente (me lo he inventado así que es probable que este ejemplo sea imposible). Todos los candidatos de cada hueco son factibles, es decir que elijas el que elijas respeta las normas, pero no está garantizado que puedas elegir cualquiera de los tres grupos en cada casilla al mismo tiempo. Es decir, no te queda otra que elegir uno para la primera casilla, otro para la segunda (si puedes, porque al poner uno en la casilla anterior automáticamente has cambiado los candidatos factibles de esta casilla) y el último (si puedes por lo mismo que antes). Podrías optar por elegir un candidato de entre los factibles al azar y así puede que a veces, de potra encuentres una solución antes, pero como las necesitas todas no te queda más huevos que probar con todos para estar seguro.

Salu2 ;)

grivcon

#38 bueno, pero esa entrada tambien la suple este método, el algoritmo recursivo funciona así:
un bucle de 1 a 9, el actual se prueba si esta disponible (respeta las reglas), si lo esta se llama a la misma funciona con la siguiente celda; si no (ninguna iteración está permitida) por recursividad volverá a la celda anterior en la iteración en la que estaba:

1
2
3
4-------1
2
3
4
5----------1
2
3
4
5
6
7
8
--------- 9
6.......

elkaoD

#38, sí, aunque me refería en ese caso a simetría axial por la diagonal principal (Matriz traspuesta), puedes comprobar que con cualquier simetría que hagas al sudoku cambia el tiempo de resolución, tanto con tu programa como por el mío. Creo que es por el tema de los factibles, que aunque los pruebe todos, hay ciertas posiciones del sudoku que eliminan los factibles de otras casillas antes, de forma que casualmente hay menos comprobaciones.

#39, que sí, que nosotros usamos el mismo método, y es fuerza bruta (Aunque compruebe si es factible.) Lo único que no es fuerza bruta es sí aplicas heurística.

LOc0

#40

Pues tienes toda la razón. Y para muestra:

http://pastebin.es/15944

Efectivamente el orden de prueba de las casillas vacías importa ya que los factibles de cada casilla se van bloqueando/desbloqueando a medida que avanzas. (Curioso porque pensé en ello de primeras para optimizar el algoritmo de backtracking pero luego lo deseché). De todas formas, el gusanillo de hacer un sudoku-solver está más que superado. Así que a otra cosa mariposa.

Salu2 ;)

Gnos1s

#36 Lo que tú usaste se llama algoritmo voraz, y consiste en que evalúa la posibles y pone una. Nunca quita. Es justo la filosofía inversa al backtracking.

Y una cosa sobre los sudokus: un sudoku tiene sólo una solución. Evidentemente, no existen 81 sudokus, ya que están todos los simétricos, que son bastantes más.

Por cierto el elKaoD, coincido en la opinión de que muchos estudiantes de ingeniería informática quisieran tener tu nivel de programación (realmente, tu capacidad de saber como resolver un problema). Escribirlo en un código es lo de menos, ya que lo único que varía es saber los pormenores: memoria, punteros, sintaxis, etc...

Ahora estás aprendiendo a "lo bruto" por lo que he leído. Si estudias Informática, aprenderás a pulir esas cosas con técnicas y le sacarás más partido a tu cabeza. El cálculo de complejidad, por ejemplo, te permitirá resolver cuestiones como de qué manera es más efectivo hacer cierta cosa (como lo de las filas y columnas del sudoku, por ejemplo); el análisis del problema te ayudará a reducir todo un problema en la esencia (muchas veces, problemas difíciles se resuelven parándote a pensar realmente qué necesitas buscar), y muchas cosas más.

Siempre he dicho que la programación consiste en "sacar patrones" de las cosas. Si sabes sacar la "fórmula" general, sabrás resolver un problema.

Personalmente, a pesar de estudiar Informática, nunca he sido muy de hacer cosas fuera de prácticas en cuanto a programación, y mi gusto por la programación va a rachas. La verdad, no me gustaría acabar picando código, como se suele decir, pero tampoco se me da mal :P. Ahora miro hacia atrás y de pensar que empecé en la carrera... ya podría haberme dedicado a aprender C/C++ en bachillerato, en vez de tanto tirito... pero bueno, al final uno aprende sí o sí :D.

Soleil

Ya que estamos propongo el siguiente ejercicio...

Crear un algoritmo que calcule el punto fijo para una función dada, f(x) con un valor máximo
de error, por ejemplo 0.0001.

Me explico, si al programa se le pasase la función cos(2), deberá ir haciendo:
cos(2)
cos(cos(2))
cos(cos(cos(2))
cos(cos(cos(cos(2)))
...

hasta que el resultado de aplicar f(x) (en este caso cos(x)) no varíe en más de 0.0001.

Esta es la salida que el programa debería dar para sqrt(64) (siendo sqrt la función que calcula
raíces cuadradas):

64
8
2,82842712474619
1,68179283050743
1,29683955465101
1,13878863475669
1,06714040067682
1,03302487902123
1,01637831491095
1,00815589811842
1,00406966796055
1,00203276790759
1,00101586795994
1,00050780504699
1,00025387029843
1,00012692709397
1,0000634615333

A partir de este punto, seguir aplicando sqrt(x) al resultado, es decir sqrt(1,0000634615333) no lo hace cambiar en más de 0.0001 (da 1,00003173026325), por tanto se detiene su ejecución.

El programa debe recibir los dos parámetros (sqrt y 64), es decir
una función cualquiera y un valor con el que empezar a aplicarla hasta hallar ese punto fijo.

Ayuda:
http://mathworld.wolfram.com/FixedPoint.html

Saludos! :-)

Poisonous

#43 yo le veo lagunas a eso, una funcion cualquiera? o una funcion cualquiera implementada en el lenguaje que vas a usar?

si es lo primero una funcion valida puede ser

f(x) = ex * (x - log(x))

otra puede ser

g(x) = tag(x + sen(x))

si fuese en lenguajes mas orientados al contexto matematico (matlab, octave, etc) si tienen handlers a funciones, pero en lenguajes como c pierdes un MONTON de tiempo con la entrada/salida...

Soleil

Para C serviría con una función cualquiera que únicamente reciba un parámetro,
tipo sqrt(), cos(), sin()... a la que se puede llamar mediante un puntero a función.

Obviamente lo ideal es poder especificar cualquier función con cualquier número de parámetros, pero en C es demasiado complicado; para ello sería mejor Lisp, Ruby, Matlab... cualquier lenguaje con funciones de primer orden.

LOc0

Para probar el C++Builder que me instalé el otro día le he hecho una GUI al sudoku

http://www.megaupload.com/es/?d=6IQV558N

Salu2 ;)

PD: Me gusta más la versión de consola :P.