Breaking

Post Top Ad

Your Ad Spot

miércoles, 14 de agosto de 2019

Resolviendo Sudoku con Backtracking | C, Java y Python

En esta publicación, presentaré un algoritmo de resolución de Sudoku usando backtracking . Si no sabe sobre el retroceso, simplemente revise la publicación anterior .
Sudoku es una matriz de 9x9 llena de números del 1 al 9 de tal manera que cada fila, columna y submatriz (3x3) tiene cada uno de los dígitos del 1 al 9. Se nos proporciona una matriz de 9x9 parcialmente llena y tenemos que llenar cada celda restante en ella. Por ejemplo, a continuación se presenta un problema de Sudoku.
Sudoku no resuelto con retroceso
Y su solución se da a continuación.
Sudoku resuelto usando el seguimiento
Puede ver que cada fila, columna y submatriz (3x3) contiene cada dígito del 1 al 9. Por lo tanto, también podemos concluir que un Sudoku se considera llenado incorrectamente si cumple alguno de estos criterios:
  1. Cualquier fila contiene el mismo número más de una vez.
  2. Cualquier columna contiene el mismo número más de una vez.
  3. Cualquier submatriz 3x3 tiene el mismo número más de una vez.
En el seguimiento , primero comenzamos con una sub-solución y si esta sub-solución no nos da una respuesta final correcta, entonces simplemente regresamos y cambiamos nuestra sub-solución. Vamos a resolver nuestro Sudoku de manera similar. Los pasos que seguiremos son:
  • Si no hay celdas sin asignar, entonces el Sudoku ya está resuelto. Simplemente volveremos cierto.
  • De lo contrario, rellenaremos una celda no asignada con un dígito entre 1 y 9 para que no haya conflictos en ninguna de las filas, columnas o submatrices 3x3.
  • Ahora, intentaremos llenar la siguiente celda no asignada y si esto sucede con éxito, entonces volveremos verdadero.
  • De lo contrario, volveremos y cambiaremos el dígito que usamos para llenar la celda. Si no hay un dígito que satisfaga la necesidad, simplemente devolveremos falso ya que no hay solución para este Sudoku.
Entonces, codifiquemos esto.

do

#include  <stdio.h>

#define TAMAÑO 9

// sudoku problem 
int  matrix [ 9 ] [ 9 ]  =  { 
    { 6 , 5 , 0 , 8 , 7 , 3 , 0 , 9 , 0 }, 
    { 0 , 0 , 3 , 2 , 5 , 0 , 0 , 0 , 8 }, 
    { 9 , 8 , 0 , 1 , 0 ,4 , 3 , 5 , 7 }, 
    { 1 , 0 , 5 , 0 , 0 , 0 , 0 , 0 , 0 }, 
    { 4 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 2 }, 
    { 0 , 0 , 0 , 0 , 0 , 0 , 5 ,0 , 3 }, 
    { 5 , 7 , 8 , 3 , 0 , 1 , 0 , 2 , 6 }, 
    { 2 , 0 , 0 , 0 , 4 , 8 , 9 , 0 , 0 }, 
    { 0 , 9 , 0 , 6 , 2 , 5 , 0 , 8 , 1 }
};

// función para imprimir sudoku 
void  print_sudoku () 
{ 
    int  i , j ; 
    para ( i = 0 ; i < TAMAÑO ; i ++ ) 
    { 
        para ( j = 0 ; j < TAMAÑO ; j ++ ) 
        { 
            printf ( "% d \ t " , matriz [ i ] [ j ]); 
        } 
        printf ( " \ n \ n" ); 
    } 
}

// función para verificar si todas las celdas están asignadas o no 
// si hay alguna celda no asignada 
// entonces esta función cambiará los valores de 
// row y col en consecuencia 
int  number_unassigned ( int  * row ,  int  * col ) 
{ 
    int  num_unassign  =  0 ; 
    int  i , j ; 
    para ( i = 0 ; i < TAMAÑO ; i ++ ) 
    { 
        para ( j = 0 ; j< TAMAÑO ; j ++ ) 
        { 
            // la celda no está asignada 
            if ( matriz [ i ] [ j ]  ==  0 ) 
            { 
                // cambiando los valores de row y col 
                * row  =  i ; 
                * col  =  j ; 
                // hay una o más celdas sin asignar 
                num_unassign  =  1 ; 
                return  num_unassign ; 
            } 
        } 
    } 
    return  num_unassign ; 
}

// función para verificar si podemos poner un 
// valor en una celda en particular o no 
int  is_safe ( int  n ,  int  r ,  int  c ) 
{ 
    int  i , j ; 
    // revisando en la fila 
    para ( i = 0 ; i < TAMAÑO ; i ++ ) 
    { 
        // hay una celda con mismo valor 
        si ( matriz [ r ] [ i ]  ==  n ) 
            de retorno  0 ;
    } 
    // comprobando la columna 
    para ( i = 0 ; i < TAMAÑO ; i ++ ) 
    { 
        // hay una celda con el valor igual a i 
        if ( matriz [ i ] [ c ]  ==  n ) 
            devuelve  0 ; 
    } 
    // comprobación de 
    submatriz int  row_start  =  ( r / 3 ) * 3 ; 
    int  col_start  =  ( c / 3 ) *3 ; 
    for ( i = row_start ; i < row_start + 3 ; i ++ ) 
    { 
        for ( j = col_start ; j < col_start + 3 ; j ++ ) 
        { 
            if ( matrix [ i ] [ j ] == n ) 
                devuelve  0 ; 
        } 
    } 
    retorno  1 ; 
}

// función para resolver sudoku 
// usando backtracking 
int  solve_sudoku () 
{ 
    int  row ; 
    int  col ; 
    // si todas las celdas están asignadas, el sudoku ya está resuelto 
    // pasar por referencia porque number_unassigned cambiará los valores de row y col 
    if ( number_unassigned ( & row ,  & col )  ==  0 ) 
        return  1 ; 
    int  n , i ; 
    // número entre 1 y 9 
    para ( i = 1 ;i <= TAMAÑO ; i ++ ) 
    { 
        // si podemos asignar i a la celda o no 
        // la celda es matriz [fila] [col] 
        if ( es_seguro ( i ,  fila ,  col )) 
        { 
            matriz [ fila ] [ col ]  =  i ; 
            // retroceso 
            if ( solve_sudoku ()) 
                return  1 ; 
            // si no podemos proceder con esta solución 
            // reasignar la 
            matriz de celda [ fila ] [ col ] =0 ; 
        } 
    } 
    devuelve  0 ; 
}

int  main () 
{ 
    if  ( solve_sudoku ()) 
        print_sudoku (); 
    else 
        printf ( "Sin solución \ n " ); 
    devuelve  0 ; 
}

Java

clase  Sudoku 
{

    privado  estático  final  int  TAMAÑO  =  9 ; 
    matriz estática privada  int [] [] = { { 6 , 5 , 0 , 8 , 7 , 3 , 0 , 9 , 0 }, { 0 , 0 , 3 , 2 , 5 , 0 , 0 , 0 , 8 }, { 9 , 8 ,    
        
        
        0 , 1 , 0 , 4 , 3 , 5 , 7 }, 
        { 1 , 0 , 5 , 0 , 0 , 0 , 0 , 0 , 0 }, 
        { 4 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 2 }, 
        { 0 , 0 , 0 , 0 ,0 , 0 , 5 , 0 , 3 }, 
        { 5 , 7 , 8 , 3 , 0 , 1 , 0 , 2 , 6 }, 
        { 2 , 0 , 0 , 0 , 4 , 8 , 9 , 0 , 0 } , 
        { 0 , 9 , 0 , 6 , 2 , 5 ,0 , 8 , 1 } 
    };

    private  static  void  printSudoku () 
    { 
        for ( int  i = 0 ; i < SIZE ; i ++) 
        { 
            for ( int  j = 0 ; j < SIZE ; j ++) 
            { 
                System . a cabo . print ( matriz [ i ] [ j ] + "\ t" ); 
            } 
            Sistema . a cabo . println ("" ); 
        } 
    }

    // función para verificar si todas las celdas están asignadas o no 
    // si hay alguna celda no asignada 
    // entonces esta función cambiará los valores de 
    // fila y col en consecuencia 
    privada  estática  int []  numberUnassigned ( int  row ,  int  col ) 
    { 
        int  numunassign  =  0 ; 
        for ( int  i = 0 ; i < TAMAÑO ; i ++) 
        { 
            for ( int  j = 0 ; j <TAMAÑO ; j ++) 
            { 
                // la celda no está asignada 
                si ( matriz [ i ] [ j ]  ==  0 ) 
                { 
                    // cambiando los valores de row y col 
                    row  =  i ; 
                    col  =  j ; 
                    // hay una o más celdas sin asignar 
                    numunassign  =  1 ; 
                    int []  a  =  { numunassign ,  fila ,  col }; 
                    devolver  a ; 
                } 
            } 
        } 
        int [] a  =  { numunassign ,  - 1 ,  - 1 }; 
        devolver  a ; 
    }

    // función para comprobar si podemos poner un 
    // valor en una celda particular o no 
    estática privada  booleana isSafe ( int n , int r , int c ) { // comprobando en fila para ( int i = 0 ; i < SIZE ; i ++) { // hay una celda con el mismo valor si ( matriz [ r ] [ i ] == n ) devuelve falso ; }       
    
        
         
        
            
              
                 
        
        // comprobando la columna 
        para ( int  i = 0 ; i < TAMAÑO ; i ++) 
        { 
            // hay una celda con el valor igual a i 
            if ( matrix [ i ] [ c ]  ==  n ) 
                return  false ; 
        } 
        // comprobación de 
        submatriz int  row_start  =  ( r / 3 ) * 3 ; 
        int  col_start  =  ( c / 3 ) * 3 ;
        for ( int  i = row_start ; i < row_start + 3 ; i ++) 
        { 
            for ( int  j = col_start ; j < col_start + 3 ; j ++) 
            { 
                if ( matrix [ i ] [ j ] == n ) 
                    return  falsa ; 
            } 
        } 
        return  true ; 
    }

    // función para resolver sudoku 
    // usando backtracking 
    privado  estático  boolean  solveSudoku () 
    { 
        int  row = 0 ; 
        int  col = 0 ; 
        int []  a  =  numberUnassigned ( row ,  col ); 
        // si todas las celdas están asignadas, el sudoku ya está resuelto 
        // pasar por referencia porque number_unassigned cambiará los valores de row y col 
        if ( a [ 0 ]  ==  0 ) 
            return  true ;
        // número entre 1 y 9 
        fila  =  a [ 1 ]; 
        col  =  a [ 2 ]; 
        for ( int  i = 1 ; i <= SIZE ; i ++) 
        { 
            // si podemos asignar i a la celda o no 
            // la celda es matriz [fila] [col] 
            if ( isSafe ( i ,  row ,  col )) 
            { 
                matriz [ fila ] [ col ]  =  i ; 
                // retroceder 
                si( solveSudoku ()) 
                    devuelve  verdadero ; 
                // si no podemos continuar con esta solución 
                // reasignar la 
                matriz de celda [ fila ] [ col ] = 0 ; 
            } 
        } 
        devuelve  falso ; 
    }

    public  static  void  main ( String []  args ) 
    { 
        if  ( solveSudoku ()) 
            printSudoku (); 
        más 
            sistema . a cabo . println ( "Sin solución" ); 
    } 
}

Pytón

TAMAÑO  =  9 
#sudoku problema 
#células con valor 0 son celdas vacantes 
matriz  =  [ 
    [ 6 , 5 , 0 , 8 , 7 , 3 , 0 , 9 , 0 ], 
    [ 0 , 0 , 3 , 2 , 5 , 0 , 0 , 0 , 8 ], 
    [ 9 , 8 , 0 , 1 , 0 ,4 , 3 , 5 , 7 ], 
    [ 1 , 0 , 5 , 0 , 0 , 0 , 0 , 0 , 0 ], 
    [ 4 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 2 ], 
    [ 0 , 0 , 0 , 0 , 0 , 0 , 5 ,0 , 3 ], 
    [ 5 , 7 , 8 , 3 , 0 , 1 , 0 , 2 , 6 ], 
    [ 2 , 0 , 0 , 0 , 4 , 8 , 9 , 0 , 0 ], 
    [ 0 , 9 , 0 , 6 , 2 , 5 , 0 , 8 , 1 ]]

#function para imprimir sudoku 
def  print_sudoku (): 
    para  i  en  matriz : 
        print  ( i )

#función para verificar si todas las celdas están asignadas o no 
#si hay alguna celda no asignada 
# entonces esta función cambiará los valores de 
#row y col en consecuencia 
def  number_unassigned ( row ,  col ): 
    num_unassign  =  0 
    para  i  en el  rango ( 0 , TAMAÑO ): 
        para  j  en el  rango  ( 0 , TAMAÑO ): 
            #cell no está asignado 
            si la  matriz [ i ] [ j ]  ==  0 : 
                fila =  i 
                col  =  j 
                num_unassign  =  1 
                a  =  [ row ,  col ,  num_unassign ] 
                devuelve  a 
    a  =  [ - 1 ,  - 1 ,  num_unassign ] 
    devuelve  una 
# función para verificar si podemos poner un 
#valor en una celda particular o no 
def  is_safe ( n ,  r ,  c ): 
    # comprobación en fila 
    para  i  en  rango ( 0 ,TAMAÑO ): 
        #hay una celda con el mismo valor 
        si la  matriz [ r ] [ i ]  ==  n : 
            devuelve  Falso 
    # comprobación en la columna 
    para  i  en el  rango ( 0 , TAMAÑO ): 
        #hay una celda con el mismo valor 
        si la  matriz [ i ] [ c ]  ==  n : 
            return  False 
    row_start  =  ( r // 3 ) * 3 
    col_start  =  ( c// 3 ) * 3 ; 
    # comprobación de submatriz 
    para  i  en  rango ( row_start , row_start + 3 ): 
        para  j  en  rango ( col_start , col_start + 3 ): 
            si  matriz [ i ] [ j ] == n : 
                return  False 
    return  True

#función para verificar si podemos poner un 
#valor en una celda particular o no 
def  solve_sudoku (): 
    row  =  0 
    col  =  0 
    #si todas las celdas están asignadas, el sudoku ya está resuelto 
    #pass por referencia porque number_unassigned cambiará los valores de fila y col 
    a  =  number_unassigned ( row ,  col ) 
    si  a [ 2 ]  ==  0 : 
        devuelve  True 
    row  =  a [ 0 ] 
    col  =  a [ 1 ]
    # número entre 1 y 9 
    para  i  en el  rango ( 1 , 10 ): 
        # si podemos asignar i a la celda o no 
        #la celda es matriz [fila] [col] 
        si es  seguro ( i ,  fila ,  col ): 
            matriz [ fila ] [ col ]  =  i 
            # retroceso 
            si  solve_sudoku (): 
                devuelve  True 
            #f no podemos proceder con esta solución 
            #asigna la 
            matriz de celda [ fila ] [ col ] = 0
    volver  falso

if  solve_sudoku (): 
    print_sudoku () 
else : 
    print ( "Sin solución" )

Explicación del código.


Inicialmente, solo estamos haciendo una matriz para Sudoku y llenando sus celdas no asignadas con 0. Por lo tanto, la matriz contiene el problema de Sudoku y las celdas con valor 0 son celdas vacías.
print_sudoku() → Esta es solo una función para imprimir la matriz.
number_unassigned → Esta función encuentra una celda vacía y hace que las variables 'fila' y 'col' sean iguales a los índices de esa celda. En C, hemos utilizado punteros para cambiar el valor de las variables (fila, col) pasadas a esta función (pasar por referencia). En Java y Python, estamos devolviendo una matriz (o lista, para Python) que contiene estos valores. Entonces, esta función nos dice si hay alguna celda no asignada o no. Y si hay una celda no asignada, esta función también nos indica los índices de esa celda.
is_safe(int n, int r, int c)→ Esta función verifica si podemos poner el valor 'n' en la celda (r, c) o no. Lo estamos haciendo primero verificando si hay alguna celda en la fila 'r' con el valor 'n' o no - if(matrix[r][i] == n)Luego estamos verificando si hay alguna celda con el valor 'n' en la columna 'c' o no - if(matrix[i][c] == n)Y finalmente, estamos verificando la submatriz. (r/3)*3 nos da el índice inicial de la fila r. Por ejemplo, si el valor de 'r' es 2, entonces está en la submatriz que comienza desde (0, 0). Del mismo modo, estamos obteniendo el valor de comenzar la columna por (c/3)*3Por lo tanto, si una celda es (2,2), entonces esta celda estará en una submatriz que comienza desde (0,0) y estamos obteniendo este valor por (c/3)*3y(r/3)*3Después de obtener los índices iniciales, podemos iterar fácilmente sobre la submatriz para verificar si podemos poner el valor 'n' en esa submatriz o no.
solve_sudoku()→ Esta es la función real que resuelve el Sudoku y utiliza el retroceso. Primero estamos verificando si hay una celda no asignada o no mediante el uso de la  number_unassignedfunción y si no hay una celda no asignada, entonces se resuelve el Sudoku. number_unassigned La función también nos da los índices de la celda vacante. Por lo tanto, si hay una celda vacía, intentaremos llenar esta celda con un valor entre 1 y 9. Y usaremos  is_safe para verificar si podemos llenar un valor particular en esa celda o no. Después de encontrar un valor, intentaremos resolver el resto del Sudoku solve_sudokuSi este valor no resuelve el resto, volveremos e intentaremos otro valor para esta celda matrix[row][col]=0;El bucle intentará otros valores en la celda.

No hay comentarios.:

Publicar un comentario

Dejanos tu comentario para seguir mejorando!

Post Top Ad

Your Ad Spot

Páginas