Programa que soluciona Sudokus en Python

Ahora que ya sabemos utilizar el IDLE podemos crear aplicaciones de un modo más fácil y sencillo, de modo que no haga falta utilizar el import ni tengamos que usar el nombre del archivo y un punto antes del nombre de la función.

Si abrimos un archivo nuevo y lo salvamos con la extensión *.py podemos hacer que su contenido se ejecute en el intérprete de Python. En esta ocasión vamos a crear un archivo en el cual generaremos un elevado número de funciones. Una vez que tengamos el archivo de funciones lo haremos correr mediante el RUN, de este modo todas las definiciones de las funciones estarán en memoria y las podremos usar directamente desde el intérprete.

Objetivo: Solucionar Sudokus

El principal objetivo de esta aplicación es desarrollar un software capaz de resolver Sudokus.  Un pasatiempos matemático que consiste en introducir los números que faltan de modo que la suma de las filas sea igual a la suma de las columnas e igual a la suma de los números de cada cuadrante. En otras palabras podríamos decir que cada fila, cada columna y cada cuadrante tiene todos los números entre el 1 y  el 9 sin que se repita ninguno de ellos.

F5.1

 En la Figura 5.1 podemos observar un sudoku antes y después de ser resuelto.

Para trabajar con python vamos a crear una tabla para almacenar los valores en su interior. Como las tablas en python no existen, vamos a tener que crear una lista de listas, es decir, una lista de nueve elementos y en cada uno de ellos habrá una lista de 9 elementos más. En la figura 5.1 podemos ver que un sudoku tiene 9 filas y 9 columnas, pero el primer elemento de una lista es el 0, por lo que a la hora de gerenar rangos para usar un bucle for vamos a usar los números del 0 al 8. Para dirigirnos a un elemento de la tabla tenemos que indicar la fila y la columna mediante los indices tal y como se aprecia a continuación tabla[fila][columna]. Vamos a definir los rangos como cada uno de los conjuntos formados por un total de 9 casillas contiguas . Cada rango se encuentra separado de los otros por las líneas negras. Para hacer este programa he numerado los rangos de izquierda a derecha y de arriba abajo empezando desde el número 1, de este modo la casilla de la cruz verde tabla[2][3] se encuentra en el rango número 2

Razonamiento para solucionar el sudoku.

Para solucionar el dusoku el programa deberá seguir los mismos pasos que usamos para solucionarlo nosotros mentalmente. Veamos los razonamientos que hacemos para ver los númeos que pueden existir en una casilla. Supongamos que nos encontramos en la casilla con la cruz verde tabla[2][3] y hacemos los siguientes razonamientos:

Imposibles Verticales: observando la columna en la que se encuentra vemos que no podremos usar los números  3, 2, 7, 9 ni 4.

Imposiblres Horizontales: Observando la fila en la que se encuentra vemos que no podremos usar los números 5, 7, 8, 3, 4, 9 ni 6.

Imposibles Rango: En el rango 2 ya esxisten los números 3, 4 y 8.

Imposibles Casilla: los números que no pueden ir en esta casilla es la suma de los imposibles verticales más los posibles horizontales y los imposibles rango. dando como resultado = [2,3,4,5,6,7,8,9]

Posibles Casilla: Los valores posibles para la casilla objeto de estudo los obtenemos de invertir los valores imposibles, en este caso valores posibles = [1]. Hemos tenido suerte y hemos encontrado una casilla con un único valor posible, ya lo podemos copiar en la tabla y seguir buscando candidatos para otras casillas.

Ahora que ya sabemos los pasos necesarios que debe realizar el programa podemos empezar a crear un número de funciones que se encarguen de trabajos concretos. Al atacar el problema principal como muchos problemas pequeños y más simles iremos resolviéndolo sin esfuerzo.

Funciones necesarias.
CreaTablaBlanco(): Crea una tabla (o lista de listas) llena de ceros.

IntroducirValoresTabla(tabla): Solicita al usuario que introduzca los valores del sudoku para poder cargarlos en la tabla, es necesario indicar el nombre de la tabla que queremos que nos llene.. La tabla debe ser una variable global.
VisualizaTabla(tabla): Se encarga de presentar la información contenida en la tabla de un modo similar al que se dibujan los sudokus.
CuentaCeros(tabla): Nos devuelve el numero de ceros que se encuentran en la tabla especifica. cuando no exista ningún cero, significará que no hay ninguna casilla vacía.
RetornaMinifilas(tabla,cuadrante): Devuelve una lista con los índices correspondientes a las filas del cuadrante que le pasamos por parámetro. Si la ejecutamos para el cuarto cuadrante devolverá el siguiente valor: [3,4,5]
RetornaMinicolumnas(tabla,cuadrante): Devuelve una lista con los índices correspondientes a las columnas del cuadrante que le pasamos por parámetro. Si la ejecutamos para el cuarto cuadrante devolverá el siguiente valor: [0,1,2]
RetornaCuadrante(fila,columna): Al pasarle los índices de una casilla del sudoku nos devuelve el número del cuadrante en la que se encuentra.
RetornaPosiblesVertical(tabla,fila,columna): Al indicarle una casilla de una tabla nos devuelve una lista con los posibles valores que puede tener esa casilla, es decir, los valores que no ha encontrado en la columna.

RetornaPosiblesHorizontal(tabla,fila,columna): Al indicarle una casilla de una tabla nos devuelve una lista con los posibles valores que puede tener esa casilla, es decir, los valores que no ha encontrado en la fila objeto de estudio.

RetornaPosiblesCuadrante(tabla,fila,columna): Al indicarle una casilla de una tabla nos devuelve una lista con los posibles valores que puede tener esa casilla, es decir, los valores que no ha encontrado en el cuadrante objeto de estudio.

RetornaInvertidos(posibles): Si le pasamos una lista de valores, devuelve una lista con los valores que faltaban y elimina los valores iniciales. Del 1 al 9

RetornaTotalPosibles(tabla,fila,columna): Esta función utiliza las tres funciones anteriores para conocer la lista definitiva de valores que podrían ocupar la casilla.

CompruebaTerminado(tabla): Una función que presenta por pantalla la suma de las filas y la suma de las columnas de una tabla, útil para comprobar que todas las casillas estén llenas y que , en un principio, el sudoku está bien hecho.

RellenaInmediatos(tabla): Se encarga de hacer una pasada por todas las casillas de una tabla especificada y siempre que encuentre una casilla con un único valor posible la llena con dicho valor.

SolucionaSudoku(tabla): Se encarga de llamar a la función RellenaInmediatos() hasta que la tabla ya no contenga ningún cero o hasta que el numero de ceros existentes en casa pasada deje de decrecer.

MenuPrincipal(): Se encarga de interrogar al usuario para saber si quieres solucionar un sudoku. Si la respuesta es afirmativa llama secuencialmente a estas tres funciones:

                sudoku=CreaTablaBlanco()
                IntroducirValoresTabla(sudoku)
                SolucionaSudoku(sudoku)

Programa propuesto (solucionar sudokus)

Copie este código en un archivo.py y ejecute el RUN del IDLE para probarlo:

# -*- coding: cp1252 -*-

def CreaTablaBlanco():
    return [[0,0,0,0,0,0,0,0,0],
          [0,0,0,0,0,0,0,0,0],
          [0,0,0,0,0,0,0,0,0],
          [0,0,0,0,0,0,0,0,0],
          [0,0,0,0,0,0,0,0,0],
          [0,0,0,0,0,0,0,0,0],
          [0,0,0,0,0,0,0,0,0],
          [0,0,0,0,0,0,0,0,0],
          [0,0,0,0,0,0,0,0,0]]
   

def IntroducirValoresTabla(tabla):
    filas=len(tabla)
    columnas=len(tabla[0])
    print "Vamos a introducir los valores del sudoku para llenar la tabla"
    print "Indtroduzca los valores de izquierda a derecha y de arriba a bajo"
    print "En las casillas sin valor introduzca un 0"
    filasentrada=[[],[],[],[],[],[],[],[],[]]
    for i in range(9):
        while len(filasentrada[i])!=9:
            print "Introduzca los valores de la fila",i+1,
            filasentrada[i] = raw_input()
    for i in range(filas):
        for j in range(columnas):       
            tabla[i][j]=int(filasentrada[i][j])
   
   

def VisualizaTabla(tabla):
    filas=len(tabla)
    columnas=len(tabla[0])
    for i in range(filas):
        if i==0 or i==3 or i==6: print"- - - - - - - - - - - - -"
        for j in range(columnas):
            if j==0 or j==3 or j==6: print"|",
            print tabla[i][j],
            if j==8: print "|"
        if i==8: print"- - - - - - - - - - - - -"
        #print "\n"

def CuentaCeros(tabla):
    filas=len(tabla)
    columnas=len(tabla[0])
    ceros=0
    for i in range(filas):
        for j in range(columnas):
            if tabla[i][j]==0:
                ceros+=1
    return ceros      

   
def RetornaMinifilas(tabla,cuadrante):
    if cuadrante==1 or cuadrante==2 or cuadrante==3 :
        return [0,1,2]
    elif cuadrante==4 or cuadrante==5 or cuadrante==6:
        return [3,4,5]
    elif cuadrante==7 or cuadrante ==8 or cuadrante ==9:
        return [6,7,8]

def RetornaMinicolumnas(tabla,cuadrante):
    if cuadrante==1 or cuadrante==4 or cuadrante==7 :
        return [0,1,2]
    elif cuadrante==2 or cuadrante==5 or cuadrante==8:
        return [3,4,5]
    elif cuadrante==3 or cuadrante ==6 or cuadrante ==9:
        return [6,7,8]


def RetornaCuadrante(fila,columna):
    if fila <=2 and columna<=2:
        return 1
    elif fila <=5 and columna<=2:
        return 4
    elif fila <=8 and columna<=2:
        return 7
    elif fila <=2 and columna<=5:
        return 2
    elif fila <=5 and columna<=5:
        return 5
    elif fila <=8 and columna<=5:
        return 8
    elif fila <=2 and columna<=8:
        return 3
    elif fila <=5 and columna<=8:
        return 6
    elif fila <=8 and columna<=8:
        return 9


def RetornaPosiblesVertical(tabla,fila,columna):
    disponibles =[1,2,3,4,5,6,7,8,9]
    filas =len(tabla)
    for i in range(filas):
        if i!=fila:
            valor=tabla[i][columna] #valor que hay asignado
            if valor in disponibles: #si el valor que hemos leido esta en la lista
                disponibles.remove(valor) #lo borramos de la lista ya que no disponible
    return disponibles
   

   
def RetornaPosiblesHorizontal(tabla,fila,columna):
    disponibles =[1,2,3,4,5,6,7,8,9]
    columnas =len(tabla[0])
    for i in range(columnas):
        if i!=columna:
            valor=tabla[fila][i] #valor que hay asignado
            if valor in disponibles: #si el valor que hemos leido esta en la lista
                disponibles.remove(valor) #lo borramos de la lista ya que no disponible
    return disponibles

def RetornaPosiblesCuadrante(tabla,fila,columna):
    disponibles =[1,2,3,4,5,6,7,8,9]
    cuadrante = RetornaCuadrante(fila,columna)
    minifilas = RetornaMinifilas(tabla,cuadrante)
    minicolumnas = RetornaMinicolumnas(tabla,cuadrante)
    valorinicialenpuntoestudio=tabla[fila][columna]
    tabla[fila][columna]='estudio'
    for i in minifilas:
        for j in minicolumnas:
            if tabla[i][j]!='estudio':
                valor=tabla[i][j]
                if valor in disponibles:
                    disponibles.remove(valor)
    tabla[fila][columna]=valorinicialenpuntoestudio #volvemos a poner el valor inicial
    return disponibles

def RetornaInvertidos(posibles):
    imposibles=[]
    if not(1 in posibles):
        imposibles.append(1)
    if not(2 in posibles):
        imposibles.append(2)
    if not(3 in posibles):
        imposibles.append(3)
    if not(4 in posibles):
        imposibles.append(4)
    if not(5 in posibles):
        imposibles.append(5)
    if not(6 in posibles):
        imposibles.append(6)
    if not(7 in posibles):
        imposibles.append(7)
    if not(8 in posibles):
        imposibles.append(8)
    if not(9 in posibles):
        imposibles.append(9)
    return imposibles

def RetornaTotalPosibles(tabla,fila,columna):
    lista1 =RetornaPosiblesVertical(tabla,fila,columna)
    lista2 =RetornaPosiblesHorizontal(tabla,fila,columna)
    lista3 =RetornaPosiblesCuadrante(tabla,fila,columna)
    lista1 =RetornaInvertidos(lista1)
    lista2 =RetornaInvertidos(lista2)
    lista3 =RetornaInvertidos(lista3)
    listatotal=lista1+lista2+lista3
    listaimposibles=[]
    if 1 in listatotal:
        listaimposibles.append(1)
    if 2 in listatotal:
        listaimposibles.append(2)      
    if 3 in listatotal:
        listaimposibles.append(3)
    if 4 in listatotal:
        listaimposibles.append(4)
    if 5 in listatotal:
        listaimposibles.append(5)
    if 6 in listatotal:
        listaimposibles.append(6)       
    if 7 in listatotal:
        listaimposibles.append(7)
    if 8 in listatotal:
        listaimposibles.append(8)   
    if 9 in listatotal:
        listaimposibles.append(9)
    listaposibles = RetornaInvertidos(listaimposibles)
    return listaposibles

def CompruebaTerminado(tabla):
    filas=len(tabla)
    columnas=len(tabla[0])
    for i in range(filas):
        valor=0
        for j in range(columnas):
            valor+=tabla[i][j]
        print "La suma de columna=",i,"es de",valor
    for j in range(columnas):
        valor=0
        for i in range(filas):
            valor+=tabla[i][j]
        print "La suma de fila=",i,"es de",valor


def RellenaInmediatos(tabla):
    filas=len(tabla)
    columnas=len(tabla[0])
    for i in range(filas):
        for j in range(columnas):
            if tabla[i][j]==0:
                posibles = RetornaTotalPosibles(tabla,i,j)
                if len(posibles)==1:
                    tabla[i][j]=posibles[0]


def SolucionaSudoku(tabla):
    ceros = CuentaCeros(tabla)
    bajando = 1
    contador =0
    print"\nEstado inicial de la tabla"
    VisualizaTabla(tabla)
    print "\nInicialmente hay",ceros,"ceros."
    while ceros>0 and bajando==1:
        RellenaInmediatos(tabla)
        if ceros > CuentaCeros(tabla):
            ceros = CuentaCeros(tabla)
            bajando = 1
        else:
            bajando = 0
        contador+=1
        print "En",contador,"pasada quedan",ceros,"ceros"
    print"\nEstado final de la tabla"
    VisualizaTabla(tabla)
    if bajando==0:
            print "No se pudo solucionar, compruebe que los valores introducidos son correctos"
def Funciones():
        print""              
        print"FUNCIONES CARGADAS:"
        print""
        print"  CreaTablaBlanco():"
        print"  IntroducirValoresTabla(tabla)"
        print"  VisualizaTabla(tabla)"
        print"  CuentaCeros(tabla)"
        print"  RetornaMinifilas(tabla,cuadrante)"
        print"  RetornaMinicolumnas(tabla,cuadrante)"
        print"  RetornaCuadrante(fila,columna)"
        print"  RetornaPosiblesVertical(tabla,fila,columna)"
        print"  RetornaPosiblesHorizontal(tabla,fila,columna)"
        print"  RetornaPosiblesCuadrante(tabla,fila,columna)"
        print"  RetornaInvertidos(posibles)"
        print"  RetornaTotalPosibles(tabla,fila,columna)"
        print"  CompruebaTerminado(tabla)"
        print"  RellenaInmediatos(tabla)"
        print"  SolucionaSudoku(tabla)"
        print"  MenuPrincipal()\n"

def MenuPrincipal():   
        print "Bienvenido a este aplicación creada por Luis Villamil 26/11/2010"
        print "Desea solucionar un Sudoku? (S/N):"
        deseo = raw_input()
        if deseo.lower()=='s':
                sudoku=CreaTablaBlanco()
                IntroducirValoresTabla(sudoku)
                SolucionaSudoku(sudoku)
        else:
                print "Deacuerdo, recuerde que se han cargado las funciones"
                print"y que puede utilizarlas a su antojo"
        print""              
        print "Realizado por:   Luis VH el 26/11/2010"
        print "Gracias por visitar www.pythonenubuntu.blogspot.com"
        print "Teclee MenuPrincipal() paga solucionar Sudokus"
        print "Teclee Funciones() paga lista de funciones usadas"

MenuPrincipal()
#fin del archivo


Aspecto de una partida


Python 2.6.5 (r265:79063, Apr 16 2010, 13:09:56)
[GCC 4.4.3] on linux2
Type "copyright", "credits" or "license()" for more information.

    ****************************************************************
    Personal firewall software may warn about the connection IDLE
    makes to its subprocess using this computer's internal loopback
    interface.  This connection is not visible on any external
    interface and no data is sent to or received from the Internet.
    ****************************************************************
   
IDLE 2.6.5      ==== No Subprocess ====
>>>
Bienvenido a este aplicación creada por Luis Villamil 26/11/2010
Desea solucionar un Sudoku? (S/N):
s
Vamos a introducir los valores del sudoku para llenar la tabla
Indtroduzca los valores de izquierda a derecha y de arriba a bajo
En las casillas sin valor introduzca un 0
Introduzca los valores de la fila 1 000400178
Introduzca los valores de la fila 2 008931000
Introduzca los valores de la fila 3 126080000
Introduzca los valores de la fila 4 360248000
Introduzca los valores de la fila 5 410000023
Introduzca los valores de la fila 6 000317056
Introduzca los valores de la fila 7 000050694
Introduzca los valores de la fila 8 000129700
Introduzca los valores de la fila 9 859004000

Estado inicial de la tabla
- - - - - - - - - - - - -
| 0 0 0 | 4 0 0 | 1 7 8 |
| 0 0 8 | 9 3 1 | 0 0 0 |
| 1 2 6 | 0 8 0 | 0 0 0 |
- - - - - - - - - - - - -
| 3 6 0 | 2 4 8 | 0 0 0 |
| 4 1 0 | 0 0 0 | 0 2 3 |
| 0 0 0 | 3 1 7 | 0 5 6 |
- - - - - - - - - - - - -
| 0 0 0 | 0 5 0 | 6 9 4 |
| 0 0 0 | 1 2 9 | 7 0 0 |
| 8 5 9 | 0 0 4 | 0 0 0 |
- - - - - - - - - - - - -

Inicialmente hay 43 ceros.
En 1 pasada quedan 27 ceros
En 2 pasada quedan 10 ceros
En 3 pasada quedan 1 ceros
En 4 pasada quedan 0 ceros

Estado final de la tabla
- - - - - - - - - - - - -
| 5 9 3 | 4 6 2 | 1 7 8 |
| 7 4 8 | 9 3 1 | 5 6 2 |
| 1 2 6 | 7 8 5 | 3 4 9 |
- - - - - - - - - - - - -
| 3 6 5 | 2 4 8 | 9 1 7 |
| 4 1 7 | 5 9 6 | 8 2 3 |
| 9 8 2 | 3 1 7 | 4 5 6 |
- - - - - - - - - - - - -
| 2 7 1 | 8 5 3 | 6 9 4 |
| 6 3 4 | 1 2 9 | 7 8 5 |
| 8 5 9 | 6 7 4 | 2 3 1 |
- - - - - - - - - - - - -

Realizado por:   Luis VH el 26/11/2010
Gracias por visitar www.pythonenubuntu.blogspot.com
Teclee MenuPrincipal() paga solucionar Sudokus
Teclee Funciones() paga lista de funciones usadas