Retos programación

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

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.

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.

#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

#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.

#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 . 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í .

#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) = e^x * (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...

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 .