Sudoku

sudoku

Nous allons voir ensemble comment écrire un programme pour trouver la solution d'un Sudoku.

Revoir les règles du jeu. Il se joue sur une grille de 9 × 9 divisé en 3 × 3 grilles que d'autres régions ou des boîtes d'appel. Le Sudoku commence avec une grille contient déjà le nombre, le but du jeu est de remplir les cellules vides avec des chiffres de 1 à 9 (un seul numéro par cellule) en suivant cette règle: Le même numéro peut apparaître qu'une seule fois pour chaque ligne, colonne et région.

Comment?

Voici ma solution pour le jeu, il est dit que le seul et n'a pas dit qu'il est le meilleur. C'est juste ma solution, si quelqu'un d'entre vous lecteurs trouver quelqu'un avec moins de complexité, de meilleures performances ou occupant moins de mémoire m'écrire.

Nous avons besoin d'un tableau pour contenir le résultat de sudoku, modèle, taille 9 × 9 m et un autre 3-dimensions matrice 9 × 9 × 9, où chaque élément aura sur l'ensemble des valeurs ou désactivé. M matrice indique pour chaque cellule si oui ou non vous pouvez entrer un numéro. Par exemple, si la valeur est définie dans des boîtes (x, y, 5) et (x, y, 6) signifie que la position (x, y) du cadre, vous pouvez entrer le numéro 5 et numéro 6. Dans ce cas, nous n'avons pas pu insérer soit parce que nous n'avons pas encore sûr de ce qui est le bon.

Nous pouvons mettre un certain nombre dans le sudoku dans la position (x, y) lorsque m se trouve dans la matrice de ces conditions:

Chaque fois que vous entrez un numéro dans la clé, nous devons définir la valeur dans le unset m métriques de la ligne, colonne, et la position actuelle de profondeur de la valeur ajoutée. Ceci, bien sûr, signifie également que si je mets un nombre dans la clé, vous ne pouvez pas entrer le même numéro dans la même rangée, colonne, la boîte (et dans la cellule.)

shema sudoku

shematizzazione matrice M


Figure vous pouvez voir quelles cellules sont impliquées dans la m tableau si vous insérez le numéro dans la case blanche.

Mise en route

Il commence par une diagramme vide, et la matrice M initialisé à tous en Septembre Continuer la saisie des numéros dans le schéma source et unset-ment à la suite de cellules m chaque insertion d'un nouveau numéro. nombre fini de la clé, la recherche de m sont analysées sous les conditions ci-dessus, si nous entrons dans un certain nombre. Trouver le nombre à inclure, dans ses grandes lignes sont écrites et mises à jour m tout comme nous le faisions auparavant.

Certains code

La langue que j'ai choisi pour ce type de programme est le «C ANSI. Nous voyons le code. 

 / * * Sudoku - Version 0.1 * * Copyright (C) 2009 Danilo Abbasciano * * Ce programme est un logiciel libre vous pouvez le redistribuer et / ou la modifier * selon les termes de la Licence Publique Générale GNU telle que publiée par la Free Software Foundation * Fondation; version Soit 2 de la licence, ou * (à votre choix) toute version ultérieure. * * Ce programme est distribué dans l'espoir qu'il sera utile, * mais SANS AUCUNE GARANTIE, sans même la garantie implicite de VALEUR MARCHANDE ou * ADAPTATION À UN USAGE PARTICULIER.  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 " ) ; } } * Voir la Licence Publique Générale GNU pour plus de détails. * * Vous devriez avoir reçu une copie de la Licence Publique Générale GNU * avec ce programme, sinon, écrivez à la Free Software Foundation *, Inc, 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA * * Rapport de bogues: * * <danilo.abbasciano@gmail.com> / # include # include # include <stdlib.h> <stdio.h> <ctype.h> # define ALL -1 # define RESET 0 # define SOMME 1 # définir un ensemble unset 0 1 # define # define DIM (RIG * col) plate-forme avec int; m char [9] [9] [9] modèle char [9] [9 int ins_number] (int x, int y, int w, int entrée) grille (int x, int y, int z, int mode); résoudre int (entrée int) Imprimer void (); int main (int argc, char * argv []) (int X, Y, Z, ins = 0; FILE * f, s char [10] if (argc! = 2) (commande printf ("Usage:% s [motif] \ n ", argv [0]) return 1;) RIG = col = 3; if ((f = fopen (argv [1]," r ")) == NULL) return 1; / * * inizzializzazione / for (x = 0, x <DIM; x + +) pour (Y = 0, y <DIM; y + +) pour (z = 0 z <DIM; z + +) [m x] [y] [z] = SET; x = 0 while (fscanf (f, "% s \ n", s) & & x <size) (pour (Y = 0, s [y]! = '\ 0', y + +) (si (s [y]> = '1 '& & s [y] <= '9') = ins ins_number (x, y, s [y] - '0 ', INS);) x + +;) fclose (f ) if (résoudre (INS)) (printf ("Impossible de résoudre \"% s \ ". \ n", argv [1]) return 1;) print () return 0;) ins_number int (int x , int y, int w, int entrée) (if ([m x] [y] [n - 1] == Unset) (printf ("Erreur: position (% d,% d) ne peut être le nombre % d \ n ", x, y, n),), sortie (1);) [schéma (print x] [=] n Y; grille (x, y, n - 1, RESET); grille (ALL, y, n - 1, RESET); réseau (x, ALL, n - 1, RESET); réseau (x, y, CLEAR ALL) retour entrées + 1;) int résoudre (entrée int) (int x, y , z, i; int trace, tandis que (<input DIM DIM *) (= trace d'entrée, car (x = 0 x <DIM; x + +) pour (Y = 0, y <DIM; y + +), si ((z = grille (x, y, ALL, SUM))! = - 1) ins_number équipé = (x, y, z + 1, entrée) pour (x = 0 x <DIM; x + +) pour (z = 0 z <DIM; z + +) if ((y = grille (X, toutes, de A à Z, SUM))! = - 1) ins_number équipé = (x, y, z + 1, entrée) pour (Y = 0, y <DIM; y + +) pour (z = 0 z <DIM; z + +) if ((x = grille (ALL, y, z, SUM))! = - 1) L'entrée = ins_number (x, y, z + 1, entrée) pour (z = 0 z <DIM; z + +) pour (x = 0 x <DIM; x + = plate-forme) pour (Y = 0, y < DIM, + y = col) si (i = grille ((x, y, z, SUM))! = - 1) ins_number entrée = (x + (i / gréement), y + (i col%), z + 1, entrée) si (== trace d'entrée) return 0;) return 1;) grille (int x, int y, int z, int mode) (int somme = 0; int index = 0; int a, b if (x! = ALL & & Y! = ALL & & z! = ALL) (/ * * box / x = (x / * col) col; = (y / RIG) plate-forme y *, car (a = 0; un col <; a + +) pour (b = 0, b plate-forme <b + +) if (mode == SUM & & [m a + x] [b + y] [z] == SET) (+ somme +; plate-forme + = indice a * b;) else if (mode == CLEAR) m [a + x] [b + y] [z] = Unset; () d'autre pour (a = 0; une taille <; à + +) switch (mode) (RESET cas: 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] = Annuler le break; SUM logements: if (x == ALL & & m [a] [y] [z] == SET) ( somme + +; index = a;) else if (y == ALL & & [m x] [a] [z] == SET) (montant + +; index = a;) else if (m == z & & TOUS [x] [y] [a] == SET) (montant + +; index = a;))) return (somme == 1)? index - 1;) Imprimer void () (int x, y; printf ("\ n") pour (x = 0 x <DIM; x + +) (pour (Y = 0, y <DIM; y + +) (if (% y avec == 0) printf ("" ) printf ("% d", la touche [x] [y]);) if (x% banc == 2) printf ("\ n") printf ("");)) \ n

Les fonctions sont peu nombreux et assez claire. Il ins_number () insère un certain nombre actualiser les deux tableaux, la grille () nous aide à operaizoni pour la matrice M, solve () est la solution à Sudoku, et enfin de sortie () visualise le modèle matriciel.

Le programme accepte en entrée un fichier avec la clé initiale dans ce format. Où sont les chiffres de la clé. Pour les cases vides que nous mettons tout caractère non numérique.
########6
76##9###8
##5#8#17#
####13###
#412#983#
###76####
#26#3#5##
9###4##1#
8######4#

solution d'impression et 

    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 bon du tout.

3 réponses à "Résoudre Sudoku"

  1. Duckerized - Janvier 15th, 2009

    Brrrr.
    brrrr programmation dynamique ... ... .., mais qu'elle sert et est plus efficace que l'algorithme

  2. admin - 15 Janvier, 2009

    Merci pour votre suggestion. Là encore, c'est ma solution, c'est qu'il est le seul et qui est le meilleur.

    Si vous avez une meilleure, qui utilise la programmation dynamique ou une autre technique, l'envoyer à moi aussi. Ecrire un billet à quatre mains, et la publicité.

    J'ai trouvé d'autres moyens pour résoudre les Sudoku à cette adresse http://en.wikipedia.org/wiki/Algorithmics_of_sudoku mais personne ne parle de la programmation dynamique.

  3. Flavio - 1er Février, 2009

    La plume est juste ...
    Sudoku est NP-difficile, si P! = NP, toute démarche prend du temps> n ^ c pour tout c, où n est la longueur du côté de la place de sudoku.

Laisser un commentaire