Solución de Sudoku

sudoku

Vamos a ver juntos cómo escribir un programa para encontrar la solución a un Sudoku.

Resumen de las reglas del juego. Se juega en una cuadrícula de 9 × 9 dividido en 3 × 3 rejillas que llaman a otras cajas o regiones. El sudoku se inicia con una cuadrícula que contiene los números ya, el objetivo del juego es rellenar las celdas vacías con números del 1 al 9 (el número uno por celda) a raíz de esta regla: El mismo número sólo puede aparecer una vez para cada fila, columna y región.

¿Cómo?

Aquí está mi solución al juego, se dice que el único y que no se dice es el mejor. Es sólo mi solución, si alguno de ustedes los lectores encontrarán a alguien con menos complejidad y mejorar el rendimiento o la memoria que ocupan menos escribirme.

Necesitamos una matriz para que contenga el resultado de sudoku, el patrón, el tamaño de 9 × 9 m, y otro 3-dimensional de la matriz de 9 × 9 × 9, donde cada elemento tendrá en el conjunto de valores o de desconexión. Matriz M indica para cada celda o no se puede introducir un número. Por ejemplo, si el valor se establece en las casillas (x, y, 5) y (x, y, 6) significa que la posición (x, y) de la infraestructura que puede introducir el número 5 y número 6. En este caso no hemos podido insertar, ya sea porque todavía no hemos seguro de cuál es la correcta.

Podemos poner un número en el sudoku en la posición (x, y) cuando m se produce en la matriz de las siguientes condiciones:

Siempre que introduzca un número en la clave que debe establecer el valor en el unset m métricas de la fila, columna y actual posición de la profundidad del valor añadido. Esto, por supuesto, también significa que si pongo un número de la clave entonces no puede entrar en el mismo número en la misma fila, columna, caja (y en la celda.)

shema sudoku

matriz m shematizzazione


La figura puede ver qué células están implicadas en la matriz m si inserta el número en el cuadro blanco.

Primeros pasos

Se inicia con una diagrama de vacío, y la matriz m inicializado a todos en septiembre Continúe introduciendo números en la fuente de esquema y unset-ción como resultado de las células m cada inserción de un nuevo número. Finito números de la tecla, estoy buscando es analizada bajo las condiciones mencionadas anteriormente, si entramos en un número. Encontrado el número que se incluirán, está escrito en sus líneas y actualizada m tal como lo hicimos antes.

Parte del código

El lenguaje que he elegido para este tipo de programas es "ANSI C. Vamos a ver el código. 

 / * * Sudoku - Versión 0.1 * * Copyright (C) 2009 Danilo Abbasciano * * Este programa es software libre puede redistribuirlo y / o modificarlo * bajo los términos de la GNU General Public License publicada por la Free Software * Fundación; versión O 2 de la Licencia, o * (a su elección) cualquier versión posterior. * * Este programa se distribuye con la esperanza de que sea útil, * pero sin garantía alguna, ni siquiera la garantía implícita de COMERCIALIZACIÓN o * IDONEIDAD PARA UN PROPÓSITO PARTICULAR.  int rig , col ; char m [ 9 ] [ 9 ] [ 9 ] ; char schema [ 9 ] [ 9 ] ; int ins_number ( int x , int y , int n , int inseriti ) ; int griglia ( int x , int y , int z , int mode ) ; int solve ( int inseriti ) ; void stampa ( ) ; int main ( int argc , char * argv [ ] ) { int x , y , z , ins = 0 ; FILE * f ; char s [ 10 ] ; if ( argc != 2 ) { printf ( "Usare: %s [schema] \n " , argv [ 0 ] ) ; return 1 ; } rig = col = 3 ; if ( ( f = fopen ( argv [ 1 ] , "r" ) ) == NULL ) return 1 ; /* inizzializzazione */ for ( x = 0 ; x < DIM ; x ++ ) for ( y = 0 ; y < DIM ; y ++ ) for ( z = 0 ; z < DIM ; z ++ ) m [ x ] [ y ] [ z ] = SET ; x = 0 ; while ( fscanf ( f , "%s \n " , s ) && x < DIM ) { for ( y = 0 ; s [ y ] != ' \0 ' ; y ++ ) { if ( s [ y ] >= '1' && s [ y ] <= '9' ) ins = ins_number ( x , y , s [ y ] - '0' , ins ) ; } x ++; } fclose ( f ) ; if ( ! solve ( ins ) ) { printf ( "Impossibile risolvere \" %s \" . \n " , argv [ 1 ] ) ; return 1 ; } stampa ( ) ; return 0 ; } int ins_number ( int x , int y , int n , int inseriti ) { if ( m [ x ] [ y ] [ n - 1 ] == UNSET ) { printf ( "error: nella posizione (%d,%d) non puo` esserci il numero %d \n " , x , y , n ) ; stampa ( ) ; exit ( 1 ) ; } schema [ x ] [ y ] = n ; griglia ( x , y , n - 1 , AZZERA ) ; griglia ( ALL , y , n - 1 , AZZERA ) ; griglia ( x , ALL , n - 1 , AZZERA ) ; griglia ( x , y , ALL , AZZERA ) ; return inseriti + 1 ; } int solve ( int inseriti ) { int x , y , z , i ; int trace ; while ( inseriti < DIM * DIM ) { trace = inseriti ; for ( x = 0 ; x < DIM ; x ++ ) for ( y = 0 ; y < DIM ; y ++ ) if ( ( z = griglia ( x , y , ALL , SOMMA ) ) != - 1 ) inseriti = ins_number ( x , y , z + 1 , inseriti ) ; for ( x = 0 ; x < DIM ; x ++ ) for ( z = 0 ; z < DIM ; z ++ ) if ( ( y = griglia ( x , ALL , z , SOMMA ) ) != - 1 ) inseriti = ins_number ( x , y , z + 1 , inseriti ) ; for ( y = 0 ; y < DIM ; y ++ ) for ( z = 0 ; z < DIM ; z ++ ) if ( ( x = griglia ( ALL , y , z , SOMMA ) ) != - 1 ) inseriti = ins_number ( x , y , z + 1 , inseriti ) ; for ( z = 0 ; z < DIM ; z ++ ) for ( x = 0 ; x < DIM ; x += rig ) for ( y = 0 ; y < DIM ; y += col ) if ( ( i = griglia ( x , y , z , SOMMA ) ) != - 1 ) inseriti = ins_number ( x + ( i / rig ) , y + ( i % col ) , z + 1 , inseriti ) ; if ( trace == inseriti ) return 0 ; } return 1 ; } int griglia ( int x , int y , int z , int mode ) { int somma = 0 ; int index = 0 ; int a , b ; if ( x != ALL && y != ALL && z != ALL ) { /* riquadro */ x = ( x / col ) * col ; y = ( y / rig ) * rig ; for ( a = 0 ; a < col ; a ++ ) for ( b = 0 ; b < rig ; b ++ ) if ( mode == SOMMA && m [ a + x ] [ b + y ] [ z ] == SET ) { somma ++; index = a * rig + b ; } else if ( mode == AZZERA ) m [ a + x ] [ b + y ] [ z ] = UNSET ; } else { for ( a = 0 ; a < DIM ; a ++ ) switch ( mode ) { case AZZERA : if ( x == ALL ) m [ a ] [ y ] [ z ] = UNSET ; else if ( y == ALL ) m [ x ] [ a ] [ z ] = UNSET ; else if ( z == ALL ) m [ x ] [ y ] [ a ] = UNSET ; break ; case SOMMA : if ( x == ALL && m [ a ] [ y ] [ z ] == SET ) { somma ++; index = a ; } else if ( y == ALL && m [ x ] [ a ] [ z ] == SET ) { somma ++; index = a ; } else if ( z == ALL && m [ x ] [ y ] [ a ] == SET ) { somma ++; index = a ; } } } return ( somma == 1 ) ? index : - 1 ; } void stampa ( ) { int x , y ; printf ( " \n " ) ; for ( x = 0 ; x < DIM ; x ++ ) { for ( y = 0 ; y < DIM ; y ++ ) { if ( y % col == 0 ) printf ( " " ) ; printf ( "  %d" , schema [ x ] [ y ] ) ; } if ( x % rig == 2 ) printf ( " \n " ) ; printf ( " \n " ) ; } } * Vea la GNU General Public License para más detalles. * * Debería haber recibido una copia de la Licencia Pública General GNU * junto con este programa, si no, escriba a la Free Software * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 EE.UU. * * Informe de errores: * * <danilo.abbasciano@gmail.com> / # include # include # include # <stdlib.h> <stdio.h> <ctype.h> definir todos -1 # define RESET 0 # define SUMA 1 # define conjunto unset 0 1 # define # define DIM (aparejo * col) La torre de int con; m char [9] [9] [9] patrón char [9] [9 ins_number int] (int x, int y, int w, int entrada) rejilla (int x, int y, int z, int modo); resolver int (int entrada) print vacío (); int main (int argc, char * argv []) (int x, y, z, ins = 0; FILE * f, char s [10] if (argc! = 2) (printf ("Uso:% s [patrón] \ n ", argv [0]) return 1;) La torre de col = = 3; if ((f = fopen (argv [1]," r ")) == NULL) return 1; / * * inizzializzazione / for (x = 0, x <DIM; x + +) para (y = 0, y <DIM; y + +) para (z = 0 z <DIM; z + +) [m] [y] x [z] = SET, x = 0 while (fscanf (f, "% s \ n", s) & & x <size) (para (y = 0, s [y]! = '\ 0', y + +) (si (s [y]> = "1" & & s [y] <= "9") = ins_number ins (x, y, s [y] - '0 ', pulgadas)) x + +;) fclose (f ) si (resolver (ins)) (printf ("No se puede resolver \"% s \ ". \ n", argv [1]) return 1;) print () return 0;) ins_number int (int x , int y, int w, int entrada) (if (m [x] [y] [n - 1] == Anular) (printf ("error: la posición (% d,% d) no puede ser el número % d \ n ", x, y, n), print (), salida (1);) [esquema x] [y] = n; cuadrícula (x, y, n - 1, RESET); cuadrícula (ALL, y, n - 1, RESET); cuadrícula (x, TODOS, n - 1, RESET); cuadrícula (x, y, CLEAR ALL) la devolución de entrada + 1;) int resolver (entrada int) (int x, y , z, i; int traza, mientras que (<input * DIM DIM) (= trazas de entrada; for (x = 0 x <DIM; x + +) para (y = 0, y <DIM; y + +) si ((z = red (x, y, TODOS, SUM))! = - 1) = ins_number equipada (x, y, z + 1, de entrada) para (x = 0 x <DIM; x + +) para (z = 0 z <DIM; z + +) if ((y la red = (x, TODOS, Z, SUM))! = - 1) = ins_number equipada (x, y, z + 1, entrada) para (y = 0, y <DIM; y + +) para (z = 0 z <DIM; z + +) if ((x = rejilla (ALL, y, z, SUM))! = - 1) = entrada ins_number (x, y, z + 1, de entrada) para (z = 0 z <DIM; z + +) para (x = 0 x <DIM; x + = torre) para (y = 0, y < DIM, + y = col) si (i = red ((x, y, z, SUM))! = - 1) de entrada ins_number = (x + (i / plataforma), y + (i col%), z + 1, de entrada) si (== traza de entrada) return 0;) return 1;) rejilla (int x, int y, int z, int modo) (int suma = 0; int index = 0; int a, b if (x! = ALL & & y! = ALL & & z! = ALL) (/ * * caja / x = (x / col) col *, y = (y / plataforma) La torre de *, porque (a = 0; una col <; A + +) para (b = 0, b plataforma <b + +) if (modo == SUM & & m [a + x] [b + y] [z] == Set) (+ suma +, el índice de plataforma = + a * b;) else if (modo == BORRAR) m [a + x b] [+ y] [z] = borrar;) persona (por (a = 0; a <DIM; a + +) interruptor (modo) (RESET caso: if (x == TODOS) m [a] [y] [z] = borrar; else if (y == TODOS) [m x] [a] [z] = unset; else if (z == TODOS) [m x] [y] [a] = borrar; break; SUM hogares: if (x == TODOS & & m [a] [y] [z] == SET) ( + + suma, el índice = a;) else if (y == TODOS & & m [x] [a] [z] == SET) (suma + +, índice = a;) else if (z == m & & TODOS [x] [y] [a] == SET) (suma + +, índice = a;))) de retorno (suma == 1)? índice - 1;) print vacío () (int x, y; printf ("\ n") for (x = 0 x <DIM; x + +) (for (y = 0, y <DIM; y + +) (if (% y con == 0) printf ("" ) printf ("% d", la tecla [x] [y]);) si (x% aparejo == 2) printf ("\ n") printf ("");)) \ n

Las funciones son pocas y bastante claro. Hay ins_number () inserta un número de la actualización de las dos matrices, de la red () nos ayuda operaizoni para la matriz m, resolver () es la solución al Sudoku, y finalmente la liberación () visualiza el patrón de matriz.

El programa acepta como entrada un archivo con la clave inicial en este formato. ¿Dónde están los números de la clave. Para las cajas vacías ponemos cualquier carácter no-dígito.
########6
76##9###8
##5#8#17#
####13###
#412#983#
###76####
#26#3#5##
9###4##1#
8######4#

y la impresión de solución 

    1 8 2 5 7 4 3 9 6
    7 6 4 3 9 1 2 5 8
    3 5 9 6 8 2 1 7 4

    2 7 8 4 1 3 9 6 5
    6 4 1 2 5 9 8 3 7
    9 8 7 6 5 4 3 2 1

    4 2 6 1 3 5 7 8 9
    9 5 3 8 4 6 7 1 2
    1 9 8 7 6 5 4 3 2

Sudoku bueno en absoluto.

3 Respuestas a "Solución de Sudoku"

  1. Duckerized - 15 de enero 2009

    Brrrr.
    De programación dinámica brrrr ... ... .. pero sirve y es más eficiente que el algoritmo

  2. admin - 15 de enero 2009

    Gracias por tu sugerencia. Una vez más esta es mi solución es que es el único y que es el mejor.

    Si usted tiene uno mejor, que utiliza la programación dinámica o alguna otra técnica, lo remitirá a mí también. Escribir un post a cuatro manos, y la publicidad.

    He encontrado otras maneras de resolver el Sudoku a esta dirección http://en.wikipedia.org/wiki/Algorithmics_of_sudoku pero nadie habla de la programación dinámica.

  3. Flavio - 01 de febrero 2009

    La pluma es la derecha ...
    Sudoku es NP-hard, por lo que si P! = NP, cualquier enfoque requiere tiempo> n ^ c para cada c, donde n es la longitud del lado de la plaza del sudoku.

Deja una respuesta