Problem beim Backtracking

[Jennesta]

Naja Backtracking ist ja eigentlich ausprobieren und dauert bei Sudoku nichtmal ne halbe Sekunde und das auch im schlechtesten Fall (es seidenn dein Computer ist 10 Jahre alt) , aber ich bin mal gespannt was du zeigst.

 

[Dragonate]

Ok dann hatte ich maybe ne falsche Auffassung von Backtracking, warscheinlich habe ich dann eine Art Kombination aus ein bisschen Backtracking + Effizienz ^^

Mal schaun. Kann nur gerade leider wenig auf der Arbeit machen ^^
Tss das große Konzerne immer Access nutzen, muss ich mich hier mit VBA rumschlagen würgh

 

[Matthias Reitinger]

Danke für die Inspirationen.

Aber mein Grüst steht schon! Soweit ich das richtig sehe @ Matthias, probiert deine Methode ja alle Möglichkeiten durch, bis Sudoku gelöst ist.
Meine Methode ist und soll aber eine effektivere sein, sie wird proportional schneller, und probiert nicht aus (es sei denn 2 mögliche Lösungen).
Eine Ausprobier-Verfahren strebe ich nicht an.

Ich hatte befürchtet, dass das kommt Ich wollte eigentlich nur das Prinzip verdeutlichen, aber trotzdem ein komplettes, funktionierendes Programm vorzeigen. Aber gut, dann eben etwas abstrahierter:

#include "stdio.h"

// Das Sudoku-Feld
int fields[4*4] = {
  0, 0, /**/ 0, 0,
  0, 0, /**/ 0, 0,
  /**************/
  0, 0, /**/ 0, 4,
  4, 0, /**/ 1, 0,
};

// Testet, ob an den Positionen i, j, k, l genau die 4 Ziffern 
// 1, 2, 3, 4 gespeichert sind.
int all_four(int i, int j, int k, int l) {
  return ((1 << fields[i]) |
          (1 << fields[j]) |
          (1 << fields[k]) |
          (1 << fields[l])) == 0x1E;
}

// Testet, ob das Sudoku gelöst ist.
int is_solved(void) {
  int i;
  for (i = 0; i < 4; ++i) {
    int block_base = (i%2)*2;
    if (i > 1) block_base += 8;
    if (!all_four(4*i, 4*i+1, 4*i+2, 4*i+3) ||
        !all_four(i, i+4, i+8, i+12) ||
        !all_four(block_base, block_base+1, block_base+4, block_base+5))
      return 0;
  }
  return 1;
}

// Gibt die noch möglichen Werte für ein bestimmtes Feld zurück,
// ausgehend vom aktuellen Zustand der restlichen Felder
void possible_values_for(int i, int *out, int *n) {
  // Naiver Ansatz, kann aber durch was besseres ersetzt werden!
  out[0] = 1;
  out[1] = 2;
  out[2] = 3;
  out[3] = 4;
  *n = 4;
}

// Versucht, das Sudoku über Backtracking lösen.
int solve(int i) {
  if (i == 16) {
    // Letzter Aufruf, prüfe ob das Sudoku gelöst ist
    return is_solved();
  }
  
  // Feld bereits gesetzt => weiter mit dem nächsten
  if (fields[i] > 0) return solve(i+1);
  
  // Alle Möglichkeiten bestimmen und durchprobieren
  int values[4], k;
  possible_values_for(i, values, &k);
  int n;
  for (n = 0; n < k; ++n) {
    // Die n-te mögliche Ziffer ausprobieren...
    fields[i] = values[n];
    // ... und mit dem nächsten Feld weiter machen
    if (solve(i+1)) return 1;
    // Wenn wir hier angekommen sind, war mit dieser Ziffer das Feld nicht lösbar,
    // also nächste ausprobieren (nächster Schleifendurchlauf)
  }
  // Keine Lösung gefunden... Backtracking
  fields[i] = 0;
  return 0;
}

int main(void) {
  if (solve(0)) {
    printf("Lösung gefunden:\n");
    int i;
    for (i = 0; i < 4; ++i)
      printf("%d\t%d\t%d\t%d\n", fields[4*i],
                                 fields[4*i+1],
                                 fields[4*i+2],
                                 fields[4*i+3]);
  } else {
    printf("Keine Lösung...\n");
  }
}

Jetzt probiert man nicht mehr stumpf sämtliche Ziffern durch, sondern nur diejenigen, die die Funktion possible_values_for zurückliefert. In dieser könnte man jetzt bestimmte Ziffern schon ausschließen. Insbesondere kann die Funktion auch melden, dass es für dieses Feld keine Möglichkeiten mehr gibt. Dann wird überhaupt keine Zahl mehr ausprobiert und das Backtracking startet. Bist du damit zufrieden?

Grüße,
Matthias

 

[Dragonate]

Ich guck mir das nacher an, hab gerade wenig Zeit und muss dazu sagen, das mein C++ noch nicht so gut ist, aber verstehen werde ichs schon mit etwas Zeit.

Aufjedenfall danke schonmal für deine Mühe.