NADA QUE VER CON LO ANTERIOR

Juegos Gratis

DEMOSTRACION DE QUE SUDOKU ES NP-COMPLETO

El Sudoku se crea a partir de los trabajos del matematico suizo Leonhard Euler (1707-1783) cuando se encontraba trabajando en la demostracion de un conjunto de teoremas acerca del calculo de probabilidades.

Sin embargo, el Sudoku visto como un juego, tiene su origen en Indianapolis en 1979. Para entonces
no se llamaba Sudoku sino simplemente Number Place (el lugar de los numeros), siendo publicado en la revista Math Puzzles and Logic Problems de la empresa especializada en puzzles Dell.

En el ambito de las matemiaticas es visto como un problema de satisfaccion de restricciones1. Los juegos de puzzle como el Sudoku son muy populares debido a que se caracterizan por la simplicidad de
sus reglas, simplicidad que necesariamente no significa no complejo, pues por el contrario se necesita de un razonamiento metodico para llegar a una solucion. Cada instancia de puzzle tiene una solucion unica.
En el presente documento nos enfocaremos en la demostracion formal de que Sudoku es un problema del tipo NP-completo. Sin embargo, para demostrar que Sudoku es un problema NP-completo bastara con codificar una instancia de Sudoku de manera tal que pueda ser expresada en una Formula Normal Conjuntiva, lo que significaria que Sudoku es equivalente a SAT. En el presente documento presentaremos un m˜netodo formal para lograr esto.

Definicion. Un Sudoku es representado por un tablero de 9x9 casillas, a su vez, este tablero esta
formado por 9 subtableros de 3x3 casillas cada uno (llamados regiones). Inicialmente se llenan algunas
casillas del tablero con n´umeros del 1 al 9 mientras que otras casillas se dejan en blanco.

Demostracion

Sudoku ∈ NP
Para demostrar que Sudoku es un problema NP-completo debemos empezar por demostrar que
SuDoku ∈ NP, para esto de debe de encontrar un algoritmo que verifique en tiempo polinomial si un
determinado tablero de Sudoku es v´alido. A continuacion se presenta el algoritmo requerido.

Sudoku ∈ NP-Hard
Esto significa que debemos demostrar que existe una formula SAT que sea equivalente a cualquier
instancia de Sudoku (cualquier tablerto T).

Un problema SAT es representado mediante el uso de variables proposicionales x1, x2, x3, . . . , xn, sobre las cuales puede asignarse un valor de verdad: 0 (falso) o 1(verdadero). Un literal l es una variable xi o su complemento −xi, es decir, un literal positivo o negativo respectivamente. Una cl´ausula w es una disyuncion de literales y una formula llamada Formula Normal Conjuntiva (CNF), es una conjuncion de clausulas.
Cuando a un literal lj de una clausula wa se le asigna el valor de verdad 1 satisfaciendo la clausula, entonces esta sera llamada clausula satisfecha. Si a dicho literal se le asigna el valor de verdad 0, entonces la clausula no se satisfacera. Una clausula con un solo literal es llamada clausula unitaria y el valor de verdad de dicho literal debe ser 1 para hacer que la cl´ausula sea satisfecha. La derivacion en una clausula vacia indica que la clausula no se satisfacera. Todo esto significa que, una formula sera satisfecha si todas sus clausulas son satisfechas. Por lo tanto, el problema SAT consiste en decidir si la asignacion de los valores de verdad de las variables hace que la formula sea satisfecha.

Ahora, generaremos una formula booleana que represente las instancias de un tablero T de SuDoku,
es decir:



equivale a:


Sin embargo, se debe cumplir que en cada fila, columna y region, ningun elemento debe repetirse.



Llegamos a obtener una formula booleana satisfacible, es decir que SAT ≤P Sudoku (SAT es reducible en tiempo polinomico en Sudoku), por lo tanto Sudoku ∈ NP-Hard.
Por otro lado, como previamente el tablero T ha sido verificado por el Algoritmo 1 se tendra siempre
que cada clausula de tendra el valor de verdad 1 (de lo contrario Sudoku /∈ NP).

Por consiguiente ∈ SAT y siendo la representacion booleana de una instancia de SuDoku y habiendose demostrado que Sudoku ∈ NP y que SuDoku ∈ NP-Hard,por lo tanto queda demostrado
que SuDoku ∈ NP-completo.

-Bibliografia
http://seccperu.org/files/sudoku%20is%20NP.pdf