SuDoku: un problema NP-completoValverde Rebaza Jorge CarlosEscuela de Informtica a Universidad Nacional de Trujillo Per u

Resumen En el presente trabajo se muestra una manera de realizar la demostracin de que el popular juego de o tipo puzzle llamado SuDoku es un problema de tipo NP-completo, cuya demostracin se realizar a o a travs de pruebas formales. Para cumplir con el objetivo se realiza una codicacin de una instancia e o de Sudoku de manera tal que pueda ser expresada en una Frmula Normal Conjuntiva y por tanto sea o equivalente a un problema SAT, a partir de esto ser posible la demostracin de que SuDoku NP y que a o SuDoku NP-Hard, las cuales son las condiciones sucientes y necesarias para que quede demostrado de que SuDoku NP-completo.

1.

Introduccin o

El SuDoku se crea a partir de los trabajos del matemtico suizo Leonhard Euler (1707-1783) cuando se a encontraba trabajando en la demostracin de un conjunto de teoremas acerca del clculo de probabilidao a des. 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 nmeros), siendo publicado en la u revista Math Puzzles and Logic Problems de la empresa especializada en puzzles Dell. Posteriormente Nikoli, una empresa japonesa especializada en pasatiempos para prensa, lo export a o Japn publicndolo en el peridico Monthly Nikolist en abril de 1984 bajo el t o a o tulo Suji wa dokushin ni kagiru, que se puede traducir como los nmeros deben estar solos, y que posteriormente se abreviar u a a Sudoku (su=nmero, doku=solo) [7]. u En el mbito de las matemticas es visto como un problema de satisfaccin de restricciones 1 . Los a a o juegos de puzzle como el SuDoku son muy populares debido a que se caracterizan por la simplicidad de sus reglas, simplicidad que necesariamente no signica no complejo, pues por el contrario se necesita de un razonamiento metdico para llegar a una solucin. Cada instancia de puzzle tiene una solucin unica. o o o En el presente documento nos enfocaremos en la demostracin formal de que SuDoku es un problema o del tipo NP-completo. El anlisis de la complejidad del SuDoku ya ha sido revisada por muchos autores, entre ellos [4] a quien postula que el SuDoku es un problema puzzle de tipo ASP-completo (Another Solution Problem) a partir del cual, mediante inferencias formales, demuestra que un SuDoku de NxN casillas, es tambin NPe completo. El autor de [3] presenta el problema del SuDoku como un Problema de Satisfaccin Restringida o1 Este tipo de problemas vienen denidos por un conjunto de variables con un conjunto de dominios asociados. Adems a existen una serie de restricciones. La solucin es encontrar una asignacin de las variables a un valor de su dominio equivalente o o de tal forma que se satisfagan las restricciones.

1

- Constraint Satisfaction Problem (CSP ), donde se comparan los diferentes regimenes de propagacin o para resolver el SuDoku y ademas sugiere nuevas tcnicas para resolver el problema sin la necesidad de e realizar bsquedas. u Sin embargo, para demostrar que SuDoku es un problema NP-completo bastar con codicar una a instancia de SuDoku de manera tal que pueda ser expresada en una Frmula Normal Conjuntiva, lo o que signicar que SuDoku es equivalente a SAT. En el presente documento presentaremos un metodo a n formal para lograr esto. El documento queda estructurado de la siguiente manera: en la seccin 2 presentamos el problema o del SuDoku deniendo las reglas que caracterizan al juego; en la seccin 3 se realiza la codicacin de o o una instancia de SuDoku en una representacin booleana que nos permita continuar con la demostracon o deseada de manera formal; en el cap tulo 4 realizamos la demostracin formal en s de que SuDoku es un o problema NP-completo siguiendo los pasos mostrados en [5]; en la seccin 5 presentamos las conclusiones o y nalmente las referencias.

2.

El problema del SuDokuSegn [1] se tiene que: u

Denicin 2.1. Un SuDoku es representado por un tablero de 9x9 casillas, a su vez, ste tablero esta o e formado por 9 subtableros de 3x3 casillas cada uno (llamados regiones). Inicialmente se llenan algunas casillas del tablero con nmeros del 1 al 9 mientras que otras casillas se dejan en blanco. u Denicin 2.2. Un SuDoku es resuelto mediante la asignacin de nmeros del 1 al 9 en las casillas en o o u blanco de cada la, cada columna y de cada regin de 3x3 . o En la gura 1 se muestra un ejemplo de como se inicia un tablero de SuDoku. El nivel de complejidad de los puzzles depende de la cantidad de casillas llenas provistas al inicio del juego. Generalmente se llenan 17 casillas al iniciar el juego, sin embargo podr llenarse ms casillas. Una de las caracter an a sticas de ste juego es que los nmeros del 1 al 9 solamente son usados segn nos convenga, pues las relaciones e u u aritmticas existentes entre ellas son totalmente irrelevantes. e Propiedad 2.3. Una instancia de SuDoku tiene una solucin unica. o Propiedad 2.4. Una instancia de SuDoku ser resuelta siguiendo un unico razonamiento. a Sabiendo que tan slo existe una unica solucin para cada puzzle, entonces se utilizarn todos los o o a nmeros del 1 al 9 para ser asignados en las casillas en blanco del tablero. La segunda propiedad indica u que en cualquier etapa de solucin del SuDoku siempre deber existir por lo menos una casilla del tablero o a en blanco en la que se pueda asignar un determinado nmero. Por lo tanto, el razonamiento cosniste en u la utilizacin de reglas de inferencia de manera tal que todas las casillas del tablero sean llenadas. o

3.

Codicacin de SuDoku o

Para poder realizar un proceso de demostracin adecuado, primero nos encargaremos de codicar un o SuDoku de una manera formal que nos permita una fcil representacin del tablero. Para realizar esta a o

2

Figura 1: Un tablero de SuDoku.codicacin, segn [1] y [2] haremos uso de la implementacin Isabelle/Hol 2 la cual nos permitir una o u o a representacin sencilla e interactiva de las reglas del SuDoku. o Deniendo formalmente mediante Isabelle/Hol tenemos que los digitos que forman parte del tablero sern modelados por un tipo de dato de 9 elementos: 1, 2, 3, . . . 9. Entonces decimos que 9 casillas a x1 , x2 , x3 , . . . , x9 , son vlidas (aceptadas en el tablero del SuDoku) si y solo si contienen todos los elea mentos 1, 2, 3, . . . 9. De sta manera tenemos: e Denicin 3.1. valido(x1 , x2 , x3 , x4 , x5 , x6 , x7 , x8 , x9 ) o

9 9 xi = d d=1 i=1

Ahora basandonos en la Denicion 3.1 podemos codicar cualquier tablero de SuDoku validando cada la, cada columna y cada regin. o

9 valido(x1j , x2j , x3j , x4j , x5j , x6j , x7j , x8j , x9j ) j=1 i,j{1,4,7} valido(xij , xi(j+1) , xi(j+2) , x(i+1)j , x(i+1)(j+1) , x(i+1)(j+2) , x(i+2)j , x(i+2)(j+1) , x(i+2)(j+2) )Ntese que podemos codicar un SuDoku con 9 variables booleanas para cada casilla de un tablero o de 9x9, lo que signica que tendremos 93 = 729 variables en total. Cada variable booleana pd (donde i,j 1 i, j, d 9) representa el valor de verdad de la ecuacin xi,j = d (ver gura 2). o

Denicin 3.2. sudoku({xi,j }i,j{1,2,3,...9} ) o

9 valido(xi1 , xi2 , xi3 , xi4 , xi5 , xi6 , xi7 , xi8 , xi9 ) i=1

9 pd d=1 i,j

(1)

La siguiente clausula nos asegura que cada casilla xi,j denota solamente uno de los nueve digitos posibles y que estos no se repiten en una misma la, columna o regin. o2 Es un conocido demostrador de teoremas que, mediante la denicin de frmulas matemticas en un lenguaje formal permite o o a la vericacin y prueba de un sistema. Fue desarrollado en la Universidad de Cambridge (Larry Paulson) y en la Universidad o Tcnica de Mnich (Tobias Nipkow). e u

3

1d