Me encanta leer estas cosas, apruebo este hilo con todas mis fuerzas. Dan ganas de compartir con todos vosotros dos o tres días completos de cháchara, cerveceo, ratos en el laboratorio/pc revisando vuestros trabajos y hablando de ellos... Seguid contando avances!
En mi caso, es una tontería que tengo ahí aparcadilla desde hace un par de meses, pero que tengo pendiente de terminar. Se trata de un intento de resolución de P = NP, sí, bastante ambiciosa la cosa xD, pero es desde una perspectiva que no tengo claro si resolverá completamente esta incógnita.
La idea es conseguir un algoritmo de resolución de un problema NP-completo, como es el sudoku, en un tiempo P. Dicho de otra forma, en lugar de hacer el típico prueba y error, hacerlo de forma directa, como si de una ecuación se tratara.
Se supone que es imposible, pero tras bastante analítica, se encuentran razones por las que podría no serlo. Relaciones entre cosas que no creías que estaban relacionadas, y ciertas características de las que no te dabas cuenta aunque los resolvieras fácilmente. Incluso averigüe una estructura de relaciones entre celdas, que representaba el mínimo de pistas para resolver un sudoku válido (con menos de 17, siempre hay varias soluciones).
El mejor momento de esta investigacioncilla fue cuando me di cuenta de esta característica, y busqué a ver si había alguna explicación matemática para ello. Y nada, que me encontré esta demostración de por qué ese número es 17, y vi que les tiró 7 millones de horas de computación sacar esto a fuerza bruta. Y claro, al haberlo sacado tan fácilmente y ver que coincidía, pues me quedé un poco p'allá.
Fue el momento en el que me tomó algo de importancia el proyecto, por lo que seguí adelante y terminé encontrando una posible estructura virtual (que contiene todas las posibles relaciones entre las casillas) que nos da acceso instantáneo a una solución en base a esas 17 pistas, o a una serie de soluciones con menos. Con 0 pistas, simplemente aparecen todos los sudokus posibles.
Ahora tengo que terminar la parte más jodida de la algoritmia en un pequeño programita que simula el problema, y va a ser sin duda la parte más chunga. Probablemente al final todo se haya quedado en un jueguecillo para ejercitar un poco la parte analítica de la mente, sin más, pero le guardo algo de esperanza a esto ya que parece cuadrar perfectamente. Lo que falta ahora es hacer un método que relacione a todas las casillas, y tengo que probar dos valores: profundidad (por cuantos niveles de celdas se propaga dicha relación), y el enfoque (desde el valor central, desde la línea horizontal y vertical que convergen en ella, o si desde las diagonales.
Llegue a salir guay o no, ya me pasaré por aquí para rallaros un poco con lo que haya sacado xD, por ejemplo creo que si sacara todo ahora, alguien con unas pocas ganas y buenos conocimientos de matemáticas/lógica, es posible que pueda terminar de implementar la solución. Así que oye, si no soy yo, pues al menos intentar que le sirva de algo a otro xD.
Aunque bueno, incluso si llegase a funcionar, no tengo los conocimientos para decir si podrá dar una solución final a P = NP, pero en un principio, resolver un NP-completo en tiempo P demostraría ese teorema.
Bueno, a ver qué más se lee por el hilo, que pinta interesante!
pues sí, tengo algo por el estilo xD, ya cuando lo haya resuelto o me haya rendido con la algoritmia del final (no creo xD) pasaré todo lo analizado hasta ahora! Piensa que por ahora no es más que un ejercicio mental, aunque exista una posibilidad generosa de que termine sirviendo para algo.
pero lo tengo en github asique sin problema)
