Estructura y Reglas

Estructura de un Sudoku

Un Sudoku se juega en una cuadrícula de 9x9 celdas dividida en subcuadrículas de 3x3. El objetivo es rellenar las celdas de manera que en cada fila, columna y región se encuentren los números del 1 al 9, sin repetir ninguno de ellos. Un Sudoku bien planteado tiene una solución única y debe tener al menos 17 pistas iniciales para garantizar esta unicidad (Demostración hecha por Gary McGuire, Bastian Tugemann y Gilles Civario en 2012). La solución siempre es un “cuadrado latino,” donde cada número aparece solo una vez en cada fila y columna, con la restricción adicional de no repetir el mismo número en una subcuadrícula.

Técnicas de Solución

Resolver un Sudoku requiere una combinación de técnicas lógicas y deductivas, que incluyen procesos de rastreo, marcado y análisis. Los programas informáticos que resuelven Sudokus pueden estimar la dificultad de un Sudoku basándose en la complejidad de las técnicas de resolución necesarias, lo que permite ofrecer Sudokus de diferentes niveles de dificultad.

Algoritmos de solución.

Los algoritmos de resolución de Sudokus son utilizados tanto por humanos como por programas informáticos. Los métodos computacionales pueden estimar la dificultad de un Sudoku, y existen varios algoritmos, como el Backtracking y la programación lineal de enteros, que utilizan enfoques diferentes para encontrar soluciones. La investigación continua en busca de mejores algoritmos y técnicas de resolución, incluyendo métodos heurísticos y estrategias basadas en deducciones lógicas.

Objetivos de la Programación Lineal

En esencia, un problema de programación lineal busca optimizar una función objetivo, sujeta a restricciones representadas por igualdades y desigualdades lineales. El conjunto de soluciones posibles, conocido como la “región factible,” se describe mediante un polytopo convexo, que es la intersección de espacios finitos, cada uno definido por una desigualdad lineal. La función objetivo es lineal y toma valores reales sobre este polyhedro. Un algoritmo de programación lineal tiene como objetivo encontrar un punto dentro de este polyhedro donde la función objetivo alcance su valor más pequeño o más grande, según el caso.

Estructura de un problema LP

Un problema de programación lineal se formula comunmente de la siguiente manera:

\[\begin{equation} \begin{aligned} \text{Maximizar } \quad & \mathbf{c}^\intercal \mathbf{x} \\ \text{Sujeto a }\quad & \begin{array}{c} \mathbf{A} \mathbf{x} \leq b \\ \mathbf{x} \geq 0 \end{array} \end{aligned} \end{equation}\]

Nota: Aquí el problema dice “Maximizar”, si el objetivo fuese minimizar deberá decir “Minimizar” en su lugar.

Esta formulación tiene 3 componentes principales:

• \(\mathbf{c}^\intercal \mathbf{x}\) es la función objetivo cuyo valor se busca minimizar o maximizar segun el problema que se desea resolver. Aquí \(\mathbf{x}\) y \(\mathbf{c}\) son vectores tal que \(\mathbf{c}\) es dado.
• \(\mathbf{x}\) es el vector que contiene las variables de decisión, aquellas que indican cuanto se debe producir, transportar, comprar, vender etc. Estas son las que indican el resultado final.
• \(\mathbf{A} \mathbf{x} \leq b\) son las restricciones o limitaciones puestas sobre las variables de decisión. Aqui \(\mathbf{A}\) y \(b\) son una matriz y un vector dados respectivamente. Estas restricciones delimitan el resultado del problema.
• Finalmente la restriccion \(\mathbf{x} \geq 0\) es la restricción de no negatividad, la cual se agrega puesto que generalmente estos problemas trabajan con objetos reales.

Tipos de soluciones.

Como ya se habia mencionado, el objetivo de la programacion lineal es encontrar el conjunto óptimo de variables de decision para la función objetivo dada con todas las restricciones aplicadas. Estas soluciones pueden ser factibles u óptimas.

• Una solución factible es una solución que satisface todas las restricciones. Si una solución factible es además uno de los vertices de la región delimitada por las restricciones entonces se dice que es solución básica factible (sbf).
• Una solución factible óptima es aquella que además de satisfacer todas las restricciones da el mejor valor para la función objetivo (ya sea el minimo en caso de minimizar, o el maximo en caso de maximizar).

Teorema Fundamental de la Programación Lineal.

El teorema de fundamental de la PL indica lo siguiente:

Para un problema de programación lineal en su forma estándar con una matriz que satisface hipótesis de rango completo se tiene:

• Si el problema no tiene solución optima \(\implies\) el problema es no acotado o infactible.
• Si hay una solución factible \(\implies\) hay una solución básica factible (sbf).
• Si hay una solución factible óptima \(\implies\) hay una sbf óptima.

El primer enunciado implica que un problema PL que este acotado y sea factible siempre va a tener solución óptima. Por otro lado los enunciados 2 y 3 implican que, si hay una solución factible, es decir si existe una región factible delimitada por las restricciones, entonces va a existir una solución factible que esté ubicada en alguno de los vertices de la región y que si alguna solución es además optima, entonces esa solución también será uno de estos vertices.

Aplicaciones de la Programación lineal.

La programación lineal tiene una amplia gama de aplicaciones en diversas disciplinas, que van desde las matemáticas puras hasta los campos de negocios, economía e ingeniería. Es ampliamente utilizada para resolver problemas de asignación de recursos, planificación logística, optimización de costos y muchos otros escenarios donde se busca optimizar una función sujeta a restricciones lineales.

Aplicaciones de modelos ILP y BILP.

Los problemas de ILP y BILP tienen aplicaciones en una amplia variedad de campos, como la planificación logística, el diseño de redes, la programación de horarios y la asignación de recursos. La naturaleza discreta de estas variables hace que sean adecuadas para modelar decisiones discretas, como la asignación de personal, la programación de máquinas y la selección de ubicaciones óptimas.

En el caso del proyecto, se usa un modelo BILP ya que, como se verá más adelante, se pueden definir las variables de decisión de forma binaria tal que sean 1 si existe un número en una casilla y 0 si no existe ningún número. Además, es un problema ILP pues es necesario que la solución al sudoku sean números enteros.

Metodos para resolver ILPs

Resolver un problema de ILP o BILP es computacionalmente más desafiante que resolver un problema de PL, ya que la integralidad o la restricción binaria agrega complejidad. Los métodos clásicos para resolver problemas ILP incluyen el Método de Ramificación y Acotamiento, que divide el espacio de soluciones en subconjuntos, y el Método de Planos de Corte, que agregan restricciones para mejorar la búsqueda. Ambos métodos consisten en la “relajación” del problema ILP, es decir, primero se soluciona el problema PL ignorando la restricción de que las variables de decisión sean enteros y luego se resuelve el problema usando esa solución. A continuación se ilustran ambos métodos.

Variables de Decisión.

Como ya se mencionó anteriormente, se definen las variables de decisión como \[\begin{equation*} x_{i, j, k}=\begin{cases} 1 \quad &\text{Si} \, \text{el numero } k \text{ está en la fila } i \text{, columna } j\\ 0 \quad &\text{} \, \text{de otro modo} \\ \end{cases} \end{equation*}\]

Asi pues, se tienen un total de \(9^3 = 729\) variables de decisión que indican si la existencia del valor o número en la casilla es verdadero o falso. Por ejemplo, \(x_{5, 4, 6} = 1\) indicaría que el valor \(5\) está presente en el cuadro situado en la fila \(4\), columna \(6\). Similarmente si \(x_{5, 4, 6} = 0\), entonces no hay un \(5\) en esa casilla.

Restricciones.

Las restricciones son simplemente las reglas del Sudoku traducidas a lenguaje matemático. La primera regla indica que “cada casilla debe contener un numero” entonces podemos escribir:

\[\sum_{k=1}^{9} x_{i, j, k} = 1 \text{ para } i = 1\text{, ..., }9\text{, } j = 1\text{, ..., }9\]

Es claro que para cada cuadro debe haber solo uno de los nueve valores como verdadero (\(1\)) y los otros ocho deben ser falsos (\(0\)).

La segunda regla indica que “cada fila debe contener cada numero del \(1\) al \(9\) una sola vez”, lo cual se puede modelar como

\[\sum_{j=1}^{9} x_{i, j, k} = 1 \text{ para } i = 1\text{, ..., }9\text{, } k = 1\text{, ..., }9\]

Similarmente la tercera regla que dice “Cada columna debe contener cada numero del \(1\) al \(9\) una sola vez se puede modelar asi

\[\sum_{i=1}^{9} x_{i, j, k} = 1 \text{ para } k = 1\text{, ..., }9\text{, } j = 1\text{, ..., }9\]

Para la cuarta regla se tiene que “Cada region de \(3\)x\(3\) debe contener los numeros del \(1\) al \(9\) una sola vez” se puede sumar \(3\) o \(6\) a cada sub indice \(j\) y \(i\), asi se tiene la restricción

\[\sum_{i=1}^{3}\sum_{j=1}^{3} x_{i + U, j + V, k} = 1 \text{ donde } U, V\in\{0, 3, 6\}\]

Finalmente, cada valor inicial (pista) puede ser expresado como una restricción. Suponga que la pista \((i, j)\) es \(m\) para algún \(1\leq m \leq 9\). Entonces \(x_{i, j, m} = 1\). La primera restricción asegura que todos los demás \(x_{i, j, k} = 0\) para \(k \neq m\).

Modelo.

Así pues, el modelo final quedaría como

\[\begin{equation} \begin{aligned} \text{Maximizar } \quad & z = 0 \\ \text{Sujeto a }\quad & \begin{array}{c} \sum_{k=1}^{9} x_{i, j, k} = 1 \text{ para } i = 1\text{, ..., }9\text{, } j = 1\text{, ..., }9 \\ \sum_{j=1}^{9} x_{i, j, k} = 1 \text{ para } i = 1\text{, ..., }9\text{, } k = 1\text{, ..., }9 \\ \sum_{i=1}^{9} x_{i, j, k} = 1 \text{ para } k = 1\text{, ..., }9\text{, } j = 1\text{, ..., }9 \\ \sum_{i=1}^{3}\sum_{j=1}^{3} x_{i + U, j + V, k} = 1 \text{ donde } U, V\in\{0, 3, 6\} \\ x_{i, j, m} = 1 \textbf{ (Todas las pistas) } \\ x_{i, j, k} \in \{0, 1\} \textbf{ (Binarios)} \end{array} \end{aligned} \end{equation}\]

Instalación de PuLP

Nota: Para instalar PuLP se requiere tener una instalación funcional de Python. Información de cómo instalar Python correctamente se puede encontrar en esta guía. PuLP requiere una version de Python mayor o igual a \(2.7\) o \(3.4\).

La version más reciente de PuLP se puede obtener de github.

Instalación usando pip y PyPi

La forma más fácil de instalar PuLP es usando pip.

• En windows (asegurarse de que pip está en el PATH)
  • c:\Python34\Scripts\> pip install pulp
• En Linux
  • $ sudo pip install pulp
  • $ sudo pupltest esto se necesita para que el solver funcione.

Para otros metodos de instalación revisar esta guía.

Una vez instalado la libreria se puede importar desde cualquier linea de comando de python. En algun IDLE o PyDev se puede escribir

import pulp as plp

Ejemplo de LP usando PuLP y Python.

Considerese el siguiente problema de Maximización:

\[\begin{equation} \begin{aligned} \text{Maximizar } \quad & z = 2x + 3y \\ \text{Sujeto a }\quad & \begin{array}{c} x + 2y \leq 8 \\ 3x - y \geq 3 \\ x, y \geq 0 \end{array} \end{aligned} \end{equation}\]

A continuación mostramos como se traduce a Python con PuLP y como se resuelve.

# Crear un problema LP
problema = plp.LpProblem("Ejemplo1", plp.LpMaximize)

# Definir las variables de decision (x, y)
x = plp.LpVariable('x', lowBound=0)
y = plp.LpVariable('y', lowBound=0)

# Definir la función objetivo
problema += 2 * x + 3 * y, "Función Objetivo"

# Definir las restricciones
problema += x + 2 * y <= 8, "Restriccion_1"
problema += 3 * x - y >= 3, "Restriccion_2"

# Resolver el problema
print(problema.solve())

# Mostrar los resultados

## 1

print("Estado:", plp.LpStatus[problema.status])

## Estado: Optimal

print(f"(x, y, z) = {(x.varValue, y.varValue, plp.value(problema.objective))}")

## (x, y, z) = (8.0, 0.0, 16.0)

De igual forma podemos graficar el problema usando matplotlib y numpy.

import matplotlib.pyplot as plt
import numpy as np

# Recuperar los valores de las variables de decisión
x_value = x.varValue
y_value = y.varValue

# Definir rangos para graficar
x_range = np.linspace(0, 10, 400)  # Crear un rango de valores para x
y_range_1 = (8 - x_range) / 2  # Restricción 1: y = (8 - x) / 2
y_range_2 = 3 * x_range - 3  # Restricción 2: y = 3x - 3
y3 = np.minimum(y_range_1, y_range_2)

# Graficar la solución
plt.plot(x_range, y_range_1, label='Restricción 1: x + 2y <= 8', linestyle='--')
plt.plot(x_range, y_range_2, label='Restricción 2: 3x - y >= 3', linestyle='--')
plt.fill_between(x_range, y3, alpha=0.3, label='Conjunto Factible', color='gray')
plt.scatter(x_value, y_value, color='red', label='Solución Óptima', marker='o')

# Establecer límites y etiquetas del gráfico
plt.xlim(0, 10)

## (0.0, 10.0)

plt.ylim(0, 10)

## (0.0, 10.0)

plt.xlabel('x')
plt.ylabel('y')
plt.legend()
plt.grid(True)
plt.title('Grafico de la Solución Óptima y Restricciones')

# Mostrar el gráfico
plt.show()