Vamos a ver juntos cómo escribir un programa para encontrar la solución a un sudoku. Repase las reglas del juego. Se juega en una cuadrícula de 9x9 dividida en cuadrículas de 3x3 que vamos a llamar a otras regiones o cajas. 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) siguiendo esta regla: El mismo número puede aparecer sólo una vez para cada fila, columna y región.

¿Cómo?

Aquí está mi solución al juego, no necesariamente el único, y no necesariamente ser el mejor. Es sólo mi solución, si alguno de ustedes los lectores encontrarán algunas de ellas con menos complejidad, más potente, o que ocupe menos memoria no me escribe.

Necesitamos una matriz para contener el resultado de sudoku, modelo, tamaño y otra de 9x9 m de la matriz de tres dimensiones de 9 × 9 × 9, donde cada elemento se enfrentará a los valores establecidos o desarmado. La matriz M para cada celda indica si se puede introducir un número. Por ejemplo, si hay un valor establecido en las cajas (x, y, 5) y (x, y, 6) significa que en la posición (x, y) de la infraestructura que puede introducir el número 5 y número 6. En este caso no podíamos entrar en cualquiera de ellos porque no tienen ni siquiera seguro de cuál es la correcta.

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

• Sólo hay un valor para el conjunto en el vector (x, y, z) para todo z en [0, 9], entonces si (x, y, z1) es el valor de SET (x, y) puede entrar en el valor z1 + 1
• Sólo hay un valor para el conjunto en el vector (x, y, z) para todo y en [0, 9], entonces si (x, y1, z) es el valor de SET (x, y1) puede entrar en el valor de z + 1
• Sólo hay un valor para el conjunto en el vector (x, y, z) para todo x en [0, 9], entonces si (x1, y, z) es el valor de SET (x1, y) puede entrar en el valor de z + 1
• No es sólo un valor para poner en una caja, si (x, y, z) es el valor al conjunto de entonces (x, y) se puede introducir el valor de z + 1

Cada vez que usted inserta un número en el diagrama que necesitamos para establecer el valor de la métrica unset fila m, columna, la profundidad y la posición del valor añadido de la caja. Esto, por supuesto, significa que si ha introducido un número en el esquema, entonces no puede entrar en el mismo número en la misma fila, columna, caja (y en la celda.)

shematizzazione matriz m

Por dónde empezar

Comienza con una esquema vacío, y la matriz M inicia en septiembre en todos los Se procede mediante la introducción de los números en la inicial y desarmar Tando las células como consecuencia de la m en cada inserción de un nuevo número. Atrás han quedado los números del esquema inicial se analiza en busca de m, de acuerdo con las condiciones visto anteriormente, si se puede introducir un número. Encontrar el número que se inserta, actualiza y está escrito en el patrón de m tal como lo hicimos anteriormente.

Un poco de código

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

 / * * Sudoku - Versión 0.1 * * Copyright (C) 2009 Daniel Abbasciano * Este programa es software libre, puede redistribuirlo y / o modificarlo * bajo los términos de la Licencia Pública General de GNU según es publicada por la Free Software * Fundación, ya sea la versión 2 de la Licencia, o (a su elección) cualquier versión posterior.  * * Este programa se distribuye con la esperanza de que se * útil, pero SIN NINGUNA GARANTÍA, ni siquiera la garantía implícita de COMERCIALIZACIÓN * o IDONEIDAD PARA UN PROPÓSITO PARTICULAR.  * Consulte 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 <stdio.h> <ctype.h> -1 # define # define ABAJO 0 # define SUMA RESET # 1 definir los grupos 1 # define unset 0 # define DIM  argv [ 0 ] ) ; return 1 ; } rig = col = 3 ; if ( ( f = fopen ( argv [ 1 ] , "r" ) ) == NULL ) return 1 ; /* inizzializzazione % S [esquema] \ n ", argv [0]) return 1;} plataforma = col = 3; if ((f = fopen (argv [1]," r ")) == NULL) return 1; / * inizzializzazione  posición (% d,% d) no puede ser el número  caja  ; printf ( " %d" , schema [ x ] [ y ] ) ; } if ( x % rig == 2 ) printf ( " \n " ) ; printf ( " \n " ) ; } } ") Printf ("% d ", el patrón de [x] [y]);} if (x == 2 plataforma%) printf (" \ n ") printf (" \ n ");}} 

Las funciones son pocos y muy claro. Hay ins_number () inserta un número de actualización de dos matrices, la red () nos ayuda operaizoni de la matriz M, resolver () es la solución del Sudoku, y, finalmente, print () muestra en pantalla el patrón de la matriz.

El programa acepta como entrada un archivo con el esquema inicial en este formato. Donde hay un número del plan inicial. Para las cajas vacías que introducir cualquier carácter que no sea un dígito.
########6
76##9###8
##5#8#17#
####13###
#412#983#
###76####
#26#3#5##
9###4##1#
8######4#

y solución de impresión

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

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

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

Sudoku bueno en absoluto.