sift
Un solucionador SAT (DPLL) con un conjunto de herramientas de lógica proposicional y un parser DIMACS, en Haskell. Resuelve instancias reales y traduce fórmulas a CNF (Tseitin).
Un solucionador SAT basado en el algoritmo DPLL, escrito en Haskell, más un kit de herramientas de lógica proposicional: un analizador DIMACS y la traducción de fórmulas a CNF por el método de Tseitin. Resuelve instancias reales.
Descripción general
sift es un solucionador SAT basado en el algoritmo DPLL, escrito en Haskell, junto con un kit de herramientas de lógica proposicional: un analizador del formato DIMACS y la traducción de fórmulas a la forma CNF por el método de Tseitin. No es un ejercicio sobre el papel - resuelve instancias reales.
SAT es uno de esos problemas que unen una simplicidad aparente con una profundidad enorme. La pregunta suena inocente, pero su respuesta puede zanjar problemas de campos totalmente distintos. Este proyecto toca justo ese núcleo, y desde un ángulo que obliga a entender por qué funciona un solucionador.
SAT pregunta algo en apariencia banal: ¿se pueden elegir valores de verdad para que toda la fórmula sea verdadera? Banal hasta el momento en que hay cientos de variables y de la respuesta dependen la planificación, la verificación de circuitos o la solución de un rompecabezas. Un solucionador SAT está bajo muchos problemas difíciles que primero se traducen a su lenguaje.
La entrada estándar es el formato DIMACS - cada línea es una cláusula, los números son variables, un menos es una negación, un cero cierra una cláusula. Texto simple que sabe codificar preguntas sorprendentemente difíciles.
Cómo funciona DPLL
DPLL es una búsqueda inteligente con retroceso. En lugar de probar todas las combinaciones, en cada paso elige una variable, supone su valor y vigila dos atajos: si una cláusula tiene un solo literal aún indeciso, su valor está forzado; si una variable aparece siempre en la misma forma, se puede fijar de inmediato.
Son justo esos dos atajos los que marcan la diferencia entre un segundo y una eternidad. Sin ellos el solucionador vaga por el árbol de todas las posibilidades; con ellos subárboles enteros caen antes siquiera de ser visitados. Implementarlos correctamente es el corazón de todo el solucionador.
Tseitin: por qué la CNF no explota
DPLL exige una fórmula en CNF, pero no toda fórmula ya lo está. Una conversión ingenua puede hacer estallar su tamaño de forma exponencial, convirtiendo un problema pequeño en uno gigantesco antes siquiera del arranque del solucionador. El método de Tseitin introduce variables auxiliares y mantiene el crecimiento lineal.
Tamaño de la fórmula tras la conversión (orientativo)
El método de Tseitin es uno de esos trucos que parecen magia hasta que entiendes por qué funcionan. Añade variables auxiliares que en apariencia complican la fórmula, pero que en realidad salvan su tamaño - sin ellas una conversión ingenua puede crecer de forma exponencial.
El resultado: un solucionador que de verdad resuelve
Lo que sale es un solucionador que funciona, que toma instancias reales en formato DIMACS y devuelve una respuesta, y por el camino traduce cualquier fórmula a CNF sin hacer estallar su tamaño. Escrito en Haskell, porque el ajuste de patrones y los tipos que velan por la corrección hacen que la lógica se lea casi como matemáticas. Un proyecto pequeño que toca una parte muy profunda de la informática - y la resuelve de verdad.
Más proyectos
Más trabajos de la misma categoría - mira cómo abordamos retos parecidos.
¿Tiene un proyecto similar?
Escríbenos - el presupuesto es gratuito y llega en una hora.