Solving Sudoku

sudoku

Wir werden gemeinsam sehen, wie man ein Programm, um die Lösung eines Sudoku finden zu schreiben.

Überprüfen Sie die Regeln des Spiels. Es ist Gittern gespielt auf einem 9 × 9 3 Raster unterteilt in 3 ×, dass andere Regionen oder Telefonkabinen. Das Sudoku beginnt mit einem Raster mit Zahlen haben, ist das Ziel des Spiels zu leeren Zellen mit Zahlen zu füllen 1-9 (eine Nummer pro Zelle) im Anschluss an diese Regel: Die gleiche Nummer kann nur einmal vorkommen für jede Zeile, Spalte und Region.

Wie?

Hier ist meine Lösung, um das Spiel, so heißt es, dass die einzige und nicht gesagt wird, das Beste. Es ist nur meine Lösung, wenn einer von euch Lesern wird jemand mit weniger Komplexität, bessere Leistung und weniger Speicherplatz einnimmt finden schreiben Sie mir.

Wir brauchen ein Array m Halten Sie das Ergebnis von Sudoku, Muster, Größe 9 × 9 und weitere 3-dimensionale Matrix 9 × 9 × 9, wo jedes Element werden die Werte gesetzt oder nicht gesetzt. M-Matrix zeigt für jede Zelle, ob oder nicht, können Sie mehrere eingeben. Zum Beispiel, wenn der Wert eingestellt ist in den Feldern (x, y, 5) und (x, y, 6) bedeutet, dass die Position (x, y) des Rahmens können Sie 5 Geben Sie die Nummer und die Nummer 6. In diesem Fall könnten wir nicht einfügen, entweder weil wir noch nicht sicher, von denen eine richtig ist.

Wir können (Put eine Zahl in das Sudoku in der Position x, y), wenn m Bedingungen tritt in der Matrix dieser:

Wenn Sie Wert auf eine Zahl in den Schlüssel des müssen wir den Wert in das metrische m unset der Zeile, Spalte, Tiefe und geographische Position hinzu. Dies ist natürlich auch bedeutet, dass wenn ich eine Zahl gesetzt in den Schlüssel, dann können Sie nicht in die gleiche Anzahl in der gleichen Zeile, Spalte, Kasten (und in der Zelle.)

shema sudoku

shematizzazione Matrix M


Abbildung sehen Sie, welche Zellen-Array m involviert sind in die Reihe einfügen, wenn Sie die in das weiße Feld.

Erste Schritte

Es beginnt mit einem Vakuum-Diagramm, und die Matrix m initialisiert, um alle im September Weiter Eingabe von Zahlen in das Schema Quelle und unset-Ing als Folge der m-Zellen jeder Einfügung einer neuen Nummer. Endlichen Zahlen des Schlüssels, m ist auf der Suche nach oben analysiert unter den Bedingungen beachten, wenn wir die Nummer eingeben. Gefunden an der Zahl, werden schriftliche Übersicht enthalten ist in und vor der Aktualisierung m genau wie wir auch.

Einige Codes

Die Sprache habe ich gewählt Programm für diese Art der ist 'ANSI C. Lassen Sie uns sehen Sie den Code. 

 / * * Sudoku - Version 0.1 * * Copyright (C) 2009 Danilo Abbasciano * * Dieses Programm ist freie Software, die Sie es verteilen kann und / oder zu modifizieren * es unter den Bedingungen der GNU General Public License, wie Software veröffentlicht von der Free * Foundation, entweder unter Version 2 der Lizenz oder * (nach Ihrer Option) jeder späteren Version. * * Dieses Programm wird verteilt in der Hoffnung, dass es nützlich sein wird, aber OHNE IRGENDEINE GARANTIE, sogar ohne die implizite Garantie der MARKTREIFE oder FITNESS FÜR EINEN BESTIMMTEN ZWECK.  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 " ) ; } } * Siehe die GNU General Public License für weitere Details. * * Sie sollten dieses Programm erhalten haben, eine Kopie der GNU General Public License zusammen mit * falls nicht, schreiben Sie an die Free Software Foundation *, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA * * Bug Report: <danilo.abbasciano@gmail.com> * * / # include # include <stdlib.h> <stdio.h> <ctype.h> # define ALL -1 # define RESET 0 # 1 # define SUM 1 definiert gesetzt unset # 0 # define DIM define (rig * col) int Rigg mit; char m [9] [9] [9] char Muster [9] [9 ] ins_number int (int x, int y, int w, int input) int Stromnetz (int x, int y, int z, int mode); int solve (int Input) void print (); int main (int argc, * argv []) (int x, y, z, Ins = 0; FILE * f, char [10 s] if (argc! = 2) (printf ("Verwendung:% s char [pattern] \ n ", argv [0]) return 1;) rig = col = 3; if ((f = fopen (argv [1]," r ")) == NULL) return 1; / inizzializzazione * * / for (x = 0, x <DIM; x + +) für (y = 0, y <DIM; y + +) für (z = 0 z <DIM; z + +) m [x] [y] [z] = SET; x = 0 while (fscanf (f, "% s \ n", s) & & x <size) (for (y = 0, s [y]! = '\ 0', y + +) (falls (s [y]> = '1 's & & y [] <= '9') = Ins ins_number (x, y, s [y] - '0 ', Ins);) x + +;) fclose (f ) if (solve (Ins)) (printf ("Kann% beheben \" s \ ". \ n", argv [1]) return 1;) print () return 0;) int ins_number (int x , int y, int w, Eingang) (if (m [x] [y] int [n - 1] == Unset) (printf ("Fehler: Position (% d,% d) kann nicht die Zahl % d \ n ", x, y, n), print (), exit (1);) Schema [x] [y] = n; Gitter (x, y, n - 1, RESET); Raster (ALL, y, n - 1, RESET); Gitter (x, ALL, n - 1, RESET); Gitter (x, y, ALL CLEAR) Return Eingang + 1;) int solve (int Input) (int x, y , z, i, int Spur; while (input <SIZE * Größe) (trace = input; for (x = 0 x <size; x + +) für (y = 0, y <size; y + +), wenn ((z = Gitter (x, y, ALL, SUM))! = - 1) ausgerüstet ins_number = (x, y, z + 1, Eingang) für (x = 0 x <DIM; x + +) für (z = 0 z <DIM; z + +) if ((y = Gitter (x, ALL, Z, SUM))! = - 1) ausgerüstet ins_number = (x, y, z + 1, Eingang) für (y = 0, y <DIM; y + +) für (z = 0 z <DIM; z + +) if ((x = Gitter (ALL, y, z, SUM))! = - 1) = Eingang ins_number (x, y, z + 1, Eingang) für (z = 0 z <DIM; z + +) für (x = 0 x <DIM; x + = rig) for (y = 0, y < DIM, y + = col) if ((i = Gitter (x, y, z, SUM))! = - 1) = Eingang ins_number (x + (i / rig), y + (i% col), z + 1, Eingang) if (trace == Eingang) return 0;) return 1;) int Stromnetz (int x, int y, int z, int mode) (int sum = 0; int index = 0; int a, b if (x! = ALL & & y! = ALL & & z! = ALL) (/ * box * / x = (x / col) * col; y = (y / rig) * rig; for (a = 0; a <col; A + +) für (b = 0, b <rig b + +) if (mode == SUM & & m [a + x] [b + y] [z] == SET) (Summe + +; index = rig + a * b;) else if (mode == CLEAR) m [a + x] [b + y] [z] = entschärft;) else (for (a = 0; bis <DIM; zu + +) Schalter (Modus) (bei RESET: 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; Immobilien SUM: if (x == ALL & & m [a] [y] [z] == SET) ( Summe + +; index = a;) else if (y == ALL & & m [x] [a] [z] == SET) (Summe + +; index = a;) else if (z == m & & ALL [x] [y] [a] == SET) (Summe + +; index = a;))) return (Summe == 1)? Index - 1;) void print () (int x, y; printf ("\ n") für (x = 0 x <DIM; x + +) (: for (y = 0, y <DIM; y + +) (if (y% mit == 0) printf ("" ) printf ("% d", die Taste [x] [y]);) if (x% rig == 2) printf ("\ n") printf ("\ n ");))

Die Funktionen sind nur wenige und klar genug. Es ins_number () fügt eine Reihe Aktualisierung der beiden Arrays, grid () hilft uns operaizoni für die Matrix m, solve () ist die Lösung für Sudoku und schließlich release () visualisiert das Array Muster.

Das Programm akzeptiert als Eingabe eine Datei mit dem ersten Schlüssel in diesem Format. Wo sind die Nummern der Schlüssel. Für die leeren Felder legen wir alle nicht-stellige Charakter.
########6
76##9###8
##5#8#17#
####13###
#412#983#
###76####
#26#3#5##
9###4##1#
8######4#

und Drucklösung 

    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 1 4 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 guter überhaupt.

3 Responses to "Solving Sudoku"

  1. Duckerized - 15. Januar 2009

    Brrrr.
    Dynamische Programmierung brrrr ... ... .., sondern dient und ist effizienter als der Algorithmus

  2. admin - 15. Januar 2009

    Vielen Dank für Ihren Vorschlag. Auch dies ist meine Lösung ist, dass es die einzige und das ist das Beste.

    Wenn Sie ein besseres, die dynamische Programmierung oder eine andere Technik verwendet, schicken Sie es mir auch. Schreibe einen Beitrag zu vier Händen, und Publizität.

    Ich fand andere Wege, um Sudoku-Adresse zu lösen, um diese http://en.wikipedia.org/wiki/Algorithmics_of_sudoku aber niemand spricht von der dynamischen Programmierung.

  3. Flavio - 1. Februar 2009

    Die Feder ist richtig ...
    Sudoku ist NP-schwer, so dass, wenn P! = NP, jede Annäherung braucht Zeit> n ^ c für alle c, wobei n die Länge der Seite des Platzes von Sudoku.

Lassen Sie eine Antwort