Sudoku Optimierung [war: mütze]

Hallo,
wieder geht es um das Thema Sudoku^^

Ich denke (oder hoffe), dass man aus der Funktion, die das Sudoku auf gültigkeit prüft, noch einiges an Geschwindigkeit herausholen kann. allerdings fiele mir kein weg ein, wie ich das anstellen sollte.
Die Funktion, die das int arr[9][9] prüft, sieht folgendermaßen aus:

bool pruefen()
{
    int a=0,b=0,c=0,d=0,e=0,f=0,g=0,h=0,i=0;

    //zeilen prüfen
    for(int l=0;l!=9;++l)
    {
        for(int k=0;k!=9;++k)
        {
            if(arr[k][l]==1)++a;
            if(arr[k][l]==2)++b;
            if(arr[k][l]==3)++c;
            if(arr[k][l]==4)++d;
            if(arr[k][l]==5)++e;
            if(arr[k][l]==6)++f;
            if(arr[k][l]==7)++g;
            if(arr[k][l]==8)++h;
            if(arr[k][l]==9)++i;
        }
        if(a>1)return false;
        if(b>1)return false;
        if(c>1)return false;
        if(d>1)return false;
        if(e>1)return false;
        if(f>1)return false;
        if(g>1)return false;
        if(h>1)return false;
        if(i>1)return false;
        a=0;b=0;c=0;d=0;e=0;f=0;g=0;h=0;i=0;
    }

    //spalten prüfen
    for(int k=0;k!=9;++k)
    {
        for(int l=0;l!=9;++l)
        {
            if(arr[k][l]==1)++a;
            if(arr[k][l]==2)++b;
            if(arr[k][l]==3)++c;
            if(arr[k][l]==4)++d;
            if(arr[k][l]==5)++e;
            if(arr[k][l]==6)++f;
            if(arr[k][l]==7)++g;
            if(arr[k][l]==8)++h;
            if(arr[k][l]==9)++i;
        }
        if(a>1)return false;
        if(b>1)return false;
        if(c>1)return false;
        if(d>1)return false;
        if(e>1)return false;
        if(f>1)return false;
        if(g>1)return false;
        if(h>1)return false;
        if(i>1)return false;
        a=0;b=0;c=0;d=0;e=0;f=0;g=0;h=0;i=0;
    }

    //die 3x3 Felder prüfen
    int aa=0,bb=0,cc=0,dd=0;

    for(int m=0;m!=3;++m)
    {
        if(m==0){cc=0;dd=3;}
        if(m==1){cc=3;dd=6;}
        if(m==2){cc=6;dd=9;}
        for(int n=0;n!=3;++n)
        {
            if(n==0){aa=0;bb=3;}
            if(n==1){aa=3;bb=6;}
            if(n==2){aa=6;bb=9;}
            for(int l=aa;l!=bb;++l)
            {
                for(int k=cc;k!=dd;++k)
                {
                    if(arr[k][l]==1)++a;
                    if(arr[k][l]==2)++b;
                    if(arr[k][l]==3)++c;
                    if(arr[k][l]==4)++d;
                    if(arr[k][l]==5)++e;
                    if(arr[k][l]==6)++f;
                    if(arr[k][l]==7)++g;
                    if(arr[k][l]==8)++h;
                    if(arr[k][l]==9)++i;
                }
            }
            if(a>1)return false;
            if(b>1)return false;
            if(c>1)return false;
            if(d>1)return false;
            if(e>1)return false;
            if(f>1)return false;
            if(g>1)return false;
            if(h>1)return false;
            if(i>1)return false;
            a=0;b=0;c=0;d=0;e=0;f=0;g=0;h=0;i=0;
        }
    }

return true;
}

Es geht bestimmt auch eleganter. Aber geht es auch schneller? Da die Funktion in meinem Backtracking Algorithmus sehr oft aufgerufen wird, würde das ganze Programm stark von einem solchen Geschwindikeitsgewinn profitieren.

Schonmal Danke für alle Tipps und Anregungen

Firefighter

1. Ja es geht schneller.
2. Das nächste mal wählst du lieber eine Überschrift wie "Hund" oder "Auto" dann weiß man direkt das es sich um Sudoku handelt. Troll!!

Shade Of Mine

2 Ansaetze:

1+2+3+4+5+6+7+8+9=45
1*2*3*4*5*6*7*8*9=362880

So kannst du ohne Spruenge alle Zeilen aufsummieren. Dazu noch jeweils ein Array fuer die summe und das produkt der spalten.
Denn egal in welcher reihenfolge die zahlen vorkommen, die beiden ergebnisse muessen stimmen.

(Pseudocode):

int sumres[9]={45};
int prodres[9]={362880};
int sumarr[9]={0};
int prodarr[9]={1};
for(int i=0;i<9;++i) {
  int sum=0, prod=1;
  for(int j=0:j<9;++j) {
    int val=feld[i][j];
    sum+=val;
    prod*=val;
    sumarr[j]+=val;
    prodarr[j]*=val;
  }
  if(sum!=45 || prod!=362880) return false;
}
return !memcmp(sumres, sumarr) && !memcmp(prodres, prodarr);

Der Nachteil: wenn die Zeilen alle korrekt sind aber die Spalten fehler haben dauert es recht lange bis man den Fehler findet...

Du verwendest 2 maps: eine zeilen map und eine spalten map.
wo jeweils in der 2. dimension die anzahl der vorkommen der zahl in der spalte/zeile steht.

steht wie oft die zahl x in der zeile 1 vorkommt.

(Pseudocode)

int zeilen[9][9]={0};
int spalten[9][9]={0};
for(int i=0;i<9;++i) {
  for(int j=0:j<9;++j) {
    int val=feld[i][j];
    if(zeilen[i][val]) return false;
    zeilen[i][val]=1;

    if(spalten[j][val]) return false;
    spalten[j][val]=1;
  }
}
return true;

Hier brichst du deutlich frueher ab, aber dafuer dauert ein kompletter durchgang fuer ein korrektes sudoku vermutlich laenger.

das sind so in etwa die 2 ansaetze die ich verfolgen wuerde...

Unglaublich!
Mit meinem ersten Ansatz (siehe 1. Post) habe ich für ein bestimmes Sudoku 1,8 Minuten gebraucht. Mit Shade Of Mine's 2. Ansatz sind es 0,16 SEKUNDEN!

Ist es wirklich ein sooo großer Unterschied, ob ich die Zeilen/Spalten nicht so

bool pruefen()
{
    int a=0,b=0,c=0,d=0,e=0,f=0,g=0,h=0,i=0;

    //zeilen prüfen
    for(int l=0;l!=9;++l)
    {
        for(int k=0;k!=9;++k)
        {
            if(arr[k][l]==1)++a;
            if(arr[k][l]==2)++b;
            if(arr[k][l]==3)++c;
            if(arr[k][l]==4)++d;
            if(arr[k][l]==5)++e;
            if(arr[k][l]==6)++f;
            if(arr[k][l]==7)++g;
            if(arr[k][l]==8)++h;
            if(arr[k][l]==9)++i;
        }
        if(a>1)return false;
        if(b>1)return false;
        if(c>1)return false;
        if(d>1)return false;
        if(e>1)return false;
        if(f>1)return false;
        if(g>1)return false;
        if(h>1)return false;
        if(i>1)return false;
        a=0;b=0;c=0;d=0;e=0;f=0;g=0;h=0;i=0;
    }

    //spalten prüfen
    for(int k=0;k!=9;++k)
    {
        for(int l=0;l!=9;++l)
        {
            if(arr[k][l]==1)++a;
            if(arr[k][l]==2)++b;
            if(arr[k][l]==3)++c;
            if(arr[k][l]==4)++d;
            if(arr[k][l]==5)++e;
            if(arr[k][l]==6)++f;
            if(arr[k][l]==7)++g;
            if(arr[k][l]==8)++h;
            if(arr[k][l]==9)++i;
        }
        if(a>1)return false;
        if(b>1)return false;
        if(c>1)return false;
        if(d>1)return false;
        if(e>1)return false;
        if(f>1)return false;
        if(g>1)return false;
        if(h>1)return false;
        if(i>1)return false;
        a=0;b=0;c=0;d=0;e=0;f=0;g=0;h=0;i=0;
    }
}

sondern so

bool pruefen()
{
    int waagerecht[9][9]={{0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0}};
    int senkrecht[9][9]={{0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0}};
    int val=1;
    for(int y=0;y!=9;++y)
    {
        for(int x=0;x!=9;++x)
        {
            if(arr[x][y])
                val=arr[x][y];
            else               //falls das Feld eine null enthält
                continue;

            if(waagerecht[x][val])
                return false;
            waagerecht[x][val]=1;

            if(arr[y][x])
                val=arr[y][x];
            else              //falls das Feld eine null enthält
                continue;

            if(senkrecht[x][val])
                return false;
            senkrecht[x][val]=1;
        }
        for(int z=0;z!=9;++z)   //array zurücksetzen
        {
            for(int p=0;p!=9;++p)
            {
                waagerecht[z][p]=0;
                senkrecht[z][p]=0;
            }
        }
    }
}

durchgehe??
Was kostet an meinem Ansatz denn so immens viel mehr Zeit??

(zum Threadtitel: ich habe die Eingabefelder "Benutzername" und "Titel" vertauscht. SORRY )

edit: hm mein neuer prüfen algorithmus funktioniert natürlich nicht (x und y müssten bei den beiden array vertauscht werden, war ich wohl zu voreilig ). Da muss ich nochmal ne nacht drüber schlafen.

mütze schrieb:

Unglaublich!
Mit meinem ersten Ansatz (siehe 1. Post) habe ich für ein bestimmes Sudoku 1,8 Minuten gebraucht.

Kannst Du dieses Sudoku bitte mal posten? Ich würde es gerne mal durch mein Prog laufen lassen.

klar

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

Du wirst nicht schneller werden, wenn du staendig alle Bedingungen testest. Warum solltest du auch. Du brauchst nur die Bedingungen neu pruefen, die von der aktuelle Veraenderung betroffen sind. Das setzen einer Zahl hat Einfluss auf nur 3 Bedingungen.

unskilled

Wenn es ihm auf Geschwindigkeit ankommt, hätte er mal auf mich hören sollen und ein Array á la bool feld[9][9][9] nehmen sollen - damit schafft man das Sodoku, für das er ein paar Minuten braucht, in ein paar Sekunden...
Es geht hier nun mal um Logik und nicht darum, einfach stumpf alles durchzuprobieren...
Mit meinem Lösungsansatz könnte man btw auch größere Sodokus lösen (0-F, 16Felder pro Quadrat) - so, wie man sie auch ab und an mal sieht... Und das wichtigste: Die benötigte Zeit steigt nicht expotentiell (wie das eben bei bruteforce-algorithmen so üblich ist)...

bb

knivil schrieb:

Du wirst nicht schneller werden, wenn du staendig alle Bedingungen testest. Warum solltest du auch. Du brauchst nur die Bedingungen neu pruefen, die von der aktuelle Veraenderung betroffen sind. Das setzen einer Zahl hat Einfluss auf nur 3 Bedingungen.

Darauf bin ich garnicht gekommen Wenn ich jedesmal nur die Zeile/Spalte/das 3x3 Feld prüfe, das gerade geändert wurde, komme ich für das sudoku, was vorher 1,5min gebraucht, auf ca 30sek.

unskilled schrieb:

Wenn es ihm auf Geschwindigkeit ankommt, hätte er mal auf mich hören sollen und ein Array á la bool feld[9][9][9] nehmen sollen - damit schafft man das Sodoku, für das er ein paar Minuten braucht, in ein paar Sekunden...

Das Problem ist, dass ich mit deiner Variante (soweit ich die durchschaut habe) keine leeren Sudokus bzw Sudokus, wo nur ein oder zwei Zahlen vorgegeben sind, lösen kann. Mit dem backtracking kann ich jedes Sudoku lösen.
Und andere Sudokus als 9x9 Sudokus möchte ich garnicht lösen

Nemonisinili

Dieser Bruteforce-Sover ist aber extrem schnell!

#include <string.h>
#include <stdlib.h>
#include <stdio.h>

int maxresults = 1;
int results = 0;
FILE *outfile;

void saveresult(const char *s) {
    fwrite(s, 1, 81, outfile);
    fprintf(outfile, "\n");
    return;
}

bool check(const char * s, int p) {
    char v = s[p];
    int x = p % 9;
    int y = p / 9;
    int qx = (int) (x / 3)*3;
    int qy = (int) (y / 3)*3;

    for (int r = 0; r < 3; r++) {
        int cp = (qy + r)*9 + qx;
        for (int c = 0; c < 3; c++) {
            if (c + cp != p && s[c + cp] == v) {
                return false;
            }
        }
    }

    for (int i = 0; i < 9; i++) {
        if (y * 9 + i != p && s[y * 9 + i] == v) {
            return false;
        }

        if (x + i * 9 != p && s[x + i * 9] == v) {
            return false;
        }
    }
    return true;
}

bool solve(const char * sp, int p) {

    char s[81];
    strcpy(s, sp);

    if (p == 81) {
        results++;
        saveresult(s);
        return true;
    }

    if (s[p] != '0') {
        return solve(s, p + 1);
    }

    for (char i = '1'; i <= '9'; i++) {
        s[p] = i;
        if (!check(s, p)) {
            continue;
        }

        bool rc = solve(s, p + 1);
        if (rc && results > maxresults - 1) {
            return true;
        }
    }
    return false;
}

int main(int argc, char *argv[]) {
    if (argc != 4) {
        return 1;
    }

    char s[81];
    memset(s, '0', 81);
    for (int i = 0; i < 81 && argv[1][i] != '\0'; i++) {
        s[i] = argv[1][i];
    }

    outfile = fopen(argv[2], "wt");
    if (outfile == NULL) {
        return 1;
    }

    maxresults = atoi(argv[3]);
    solve(s, 0);
    fclose(outfile);
    return 0;
}

volkard

ich würde die daten anders speichern.
mal ein kleiner versuch:

es gibt 9 reihen, 9 spalten und 9 blöcke.
jedes feld gehört zu einer reihe, einer spalte und einem block.
ich möchte zur laufzeit wenig rechnen.
integers kann ich als bitfelder mißbrauchen.

das mache ich so:

//bitfields
unsigned int reihen[9];
unsigned int spalten[9];
unsigned int bloecke[9];

//jedes Feld gehört zu drei bitfields
struct Feld{
  int zahl;
  unsigned int* reihe;
  unsigned int* spalte;
  unsigned int* block;
};

//naja, war ja klar, daß jetzt spwas kommt
Feld feld[9][9];

die zeiger auf die bitfields müssen mit ein paar schleifen vor dem eigentlichen suchlauf schnell gesetzt werden.

und

bool setze(Feld* f,int zahl){
  //prüfen
  unsigned int zahlbitmuster=1U<<zahl;
  if((f->reihe&zahlbitmuster)!=0) return false;
  if((f->spalte&zahlbitmusterl)!=0) return false;
  if((f->block&zahlbitmuster)!=0) return false;
  //setzen
  f->reihe|=zahlbitmuster;
  f->spalte|=zahlbitmuster;
  f->block|=zahlbitmuster;
  f->zahl=zahl;
  return true;
}
void loesche(Feld* f){
  //zurüclnehmen, dadurch muss im rekursiven abstieg niemals der ganze
  //spielstand gespeichert werden
  unsigned int zahlbitmuster=1U<<f->zahl;
  f->reihe&=~zahlbitmuster;
  f->spalte&=~zahlbitmuster;
  f->block&=~zahlbitmuster;
  f->zahl=0;
}

klingt ganz lecker. aber in dem versuch steckt null sudokuwissen.