Resolvendo Sudoku por meio de programação linear.

Sudoku é um problema de lógica baseado na alocação de números em quebra-cabeça na forma de matriz.
O objetivo é preencher uma matriz $9 \times 9$ com números de 1 a 9 de modo que cada coluna, cada linha, e cada uma das nove $3\times3$ sub-matrizes que compõem a matriz maior contenha todos os dígitos de 1 a 9.

A resolução desse problema por meio de programação linear binária foi proposto por Bartlett, Chartier, Langville e Rankin (2008)

Considere um problema Sudoku de dimensão $4\times 4$, nesse caso temos para cada sub-matriz 2 linhas e 2 colunas representadas por $m=2$. O grau do problema é dado por a $n=m^2$, aqui temos então $n=4$. Visualmente, temos:

Nesse problema temos que preencher os quadrados faltantes com números de 1 a 4, de modo que em nenhuma linha ou coluna da matriz superior contenha números repetidos, além do mais, cada sub-matriz também não deve possuir números repetidos.

Claramente essas condições formam as restrições do nosso problema de programação linear binária, podemos sintetizá-las da seguinte forma:

1. Cada coluna contém somente uma entrada $k$ onde $1\le k\le n$.
2. Cada linha contém somente uma entrada $k$ onde $1\le k\le n$.
3. Todos os espaços vazios devem ser completados.
4. Algumas entradas do quebra-cabeça são conhecidas desde o início. Isto pode ser indicado como uma sequência de valores $x_{ijk}=1$, onde $1\le i,j,k \le n$.
5. Cada sub-matriz deve conter exatamente um dos $n$ possíveis dígitos.

Matematicamente podemos representar o problema da seguinte forma:

$ $$\begin{array}{rl} \mathbf{Minimize}\mbox{ } Z= & 0x_{111}+0x_{112}+\dots+0x_{nnn} \\ \mathbf{Sujeito}\mbox{ } \mathbf{a: } &\\ \displaystyle\sum_{i=1}^{n}x_{ijk}=&1 \mbox{ para } j=1,\dots,n \mbox{ e } k=1,\dots,n. \\\mbox{ (Apenas um k em cada coluna.) }\\\displaystyle\sum_{j=1}^{n}x_{ijk}=&1, \mbox{ para } i=1,\dots,n\mbox{ e } k=1,\dots,n \\\mbox{ (Apenas um k em cada linha.) } \\ \displaystyle\sum_{j=mq-m+1}^{mq}\displaystyle\sum_{i=mq-m+1}^{mq}x_{ijk}=&1, \mbox{ para } k=1,\dots,n\mbox{ , } p=1,\dots,m \mbox{ e } q=1,\dots,m \\\mbox{ (Somente um k em cada sub-matriz.) }\\ x_{ijk}=&1 \\\mbox{ para todo elemento (i,j,k) já preenchido na tabela.} \\ \displaystyle\sum_{k=1}^{n}x_{ijk}=&1, \mbox{ para } i=1,\dots,n \mbox{ e } j=1,\dots,n \\\mbox{ (Todas as posições da matriz devem ser preenchidas.)}\\x_{ijk} & \mbox{é binário para } 1\le i,j,k \le n\end{array}$$ $

onde $x_{ijk}$ representa o elemento $(i,j)$ da matriz superior assumindo o valor igual a $k$. Para resolver podemos usar o pacote lpSolve.