Problem beim Backtracking

[Dragonate]

Ich versuche mal auszuformulieren was ich bisher hab, wie die Vorgehensweise ist und wo das Problem liegt.(es geht wiedermal um Sudoku)
Mein Code ist mittlerweile viel zu Komplex, als das ich Ihn hier posten könnte, deshalb die Problemstelle via Pseudo-Code:

Variable count1 zählt wieviele Möglichkeiten es für eine Zahl in einem 9ner Block gibt.

Bedingung1:
Wenn count1 == 1 ist (nur eine Möglichkeit) --> setze in Sudoku ein (funktioniert)

//(Dabei ist drum herum alles geregelt, wie festgestellt wird, wieviele Möglichkeiten es gibt)

Bedingung2:
Wenn count1 == 2 ist (es gibt 2 möglichkeiten) &&  Bedingung1 nicht mehr möglich ist[
--> merke dir beide Möglichkeiten && setze die erste ein (funktioniert)

Dabei werden immer, wenn es 2 Möglichkeiten gibt (und natürlich keine nach Bedingung1) , diese in einem 2D Array gespeichert, welches sich nach 2 gesetzten Werten im Zähler erhöht, etwa so :

temp_lösungen["Position1"]["zähler"]=Zahl_für_sudoku
temp_lösungen["Position2"]["zähler"]=Zahl_für_Sudoku

//("Zahl_für_sudoku" könnte an 2 verschiedenen Positionen im Sudoku stehen)

Wenn 2 Lösungen eingesetzt wurden -->  zähler++; 
//(damit wenn neue 2 Lösungen gefunden werden, die alten nicht verloren gehen)

Nun habe ich auch eine Bedingung im Code die sagt, wenn ich nichts mehr einsetzen kann, gehe zur letzten temp_Lösungen zähler-stelle, und setze statt der ersten Möglichkeit, die 2te Möglichkeit in Sudoku ein.
Ab hier kriege ich die Probleme, es wird immer nur die zuletzt gefundene Doppel-Lösung ausgetauscht und ich habe Probleme es zu programmieren, das eventuell vorherige doppel-lösungen schon falsch waren, und er an dieser Stelle tauschen muss.
Mir ist klar das ich da auch mit Zählern arbeiten muss, aber hat da jemand einen hilfreichen logischen tip ?

 

[Vereth]

Das klingt, als würdest du rein iterativ vorgehen. Bei Backtracking kann man sich oft die Arbeit erleichtern, wenn man eine rekursive Funktion programmiert. Dann wird jedesmal eine lokale Variable für den jeweiligen Zähler verwendet, der, wenn der Rekusiv-Aufruf zurückkehrt, für das aktuelle Durchzählen weiterverwendet werden kann, weil sein Wert - wie bei allen anderen lokalen Variablen auch - erhalten bleibt.

 

[Dragonate]

Ja die Rekursion benutze ich bereits, habe ich nur nicht erwähnt.
Das Problem ergibt sich aber trotzdem für mich, in der Form wie ich es geschildert habe.

Ich habe aber gerade auch eine Idee, ich werde zusätzlich ein Array des Typ's boolean anwenden, um damit bereits eingesetzte Möglichkeiten kenntlich zu machen, mal sehen obs klapt.

Danke

 

[Vereth]

Vielleicht ist es von der Verwaltung her einfacher, wenn du int-Werte verwendest, um Sperrvermerke zu zählen. Eine Zelle kann ja auf drei Arten für eine Zahl gesperrt werde, über Zeile, Spalte und Block. Wenn du eine Zelle für eine Zahl sperren willst, erhöhst du den Zähler, wenn du sie freigeben willst, erniedrigst du ihn. Ein Wert von 0 bedeutet, die Zelle ist für die Zahl verfügbar.

 

[Dragonate]

Ja, das geht aber so auch sehr gut.

Ich sage :

wenn 
    erste Möglichkeit nicht funktioniert hat
dann
    setzte 2te Möglichkeit ein
    schon_mal_eingesetzt[aktuelle_möglichkeit]=true;

und im nachfolgendem Durchlauf sage ich dann:

wenn
    programm kommt nicht mehr weiter, weil eine Zahl Falsch ist
dann
    wenn schon_mal_eingesetzt[vorherige_möglichkeit]==false
         dann
              setze vorherige 2teMöglichkeit ein
         sonst
              springe noch eine Möglichkeit zurück

Das mit den Spalten Zeilen und Blöcken ist in diesem Fall nicht mehr von Bedeutung, weil mein Programm von der Funktionsweise folgendermaßen vorgeht:

-Es werden nur noch Zahlen an die Funktion übergeben, die noch nicht im Sudoku vorhanden sind, wird eine Zahl eingesetzt und ist eindeutig richtig, wird sie aus dem Block-Pool entfernt.

-Innerhalb der Funktion wird ausserdem überprüft, ob die noch einzusetzenden Zahlen innerhalb eines Blocks, durch eine Spalte oder Zeile blockiert werden. Ich habe die Sperrung also so programmiert, wie man als Mensch bei einem Sudoku auch vorgehen würde.

In den Teil des Codes, vondem wir gerade Sprechen, kommen also nur noch Zahlen ran, die auch Relevanz haben.

 

[Vereth]

Ich vermute einfach mal, dass du den zähler nicht wieder dekrementierst (herunterzählst), wenn die aktuelle zweite Möglichkeit auch falsch war.
Abgesehen davon scheint mir dein Algorithmus etwas umständlich zu sein. Kannst du mir mal die Sourcen mailen?

 

[Dragonate]

Ähm naja würde ich schon machen, aber um den Code nachzuvollziehen, müsstest du denke ich zuviel Zeit investieren und das will ich dir nicht antun. Keinesfalls wegen deiner Kompetenzen, die warscheinlich weitaus höher als die meinen sind, aber einige Variablen Bezeichnungen sind nicht optimal etc, das wollte ich im Nachinein für die Lesbarkeit erst verbessern.

Dekrementieren tue ich schon, nur wenn es mehrere Äste gibt mit mehreren Unterästen, dann tue ich mich glaube ich mit der Dekrementierung schwer.

Ich konnte übers Wochenende und heute leider nicht am Code arbeiten, und werde vielleicht Morgen wenn ich wieder einen klaren Kopf habe, weitermachen.

Ich versuche es erst nochmal selbst, und komme dann auf dich zurück Vereth !

Danke !

 

[Jennesta]

Hast du wirklich soviel Code?
Ich habe dasselbe vor einem Monat auch gemacht und bei mir ist das sogar recht komprimiert. Also wenn du da irgendwelche Fragen hast kannste gerne ma schreiben.
Deine Pseudocodes sehen auch so aus, als machst du dir das Leben vielleicht zu schwer

 

[Matthias Reitinger]

Deine Pseudocodes sehen auch so aus, als machst du dir das Leben vielleicht zu schwer

Das Gefühl habe ich auch. Hier mal ein (naiver) Löser für ein 2er-Sudoku, der über Backtracking einfach alle Möglichkeiten durchprobiert und zurückläuft, wenn keine gültige Lösung entstanden ist:

#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;
}

// Versucht, das Sudoku über naives 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 durchprobieren
  int n;
  for (n = 1; n <= 4; ++n) {
    // Die Ziffer n ausprobieren...
    fields[i] = 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");
  }
}

Nur mal um das Prinzip zu verdeutlichen. Die Implementierungen von all_four und is_solved bitte nicht zum Vorbild nehmen

Grüße,
Matthias

 

[Dragonate]

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.

Melde mich wieder

Und naja, vielleicht ist es auch nicht soviel, aber wenn ich den Code hier Poste, dann werde ich den vorher noch besser Kommentieren etc, damit ihr da schneller durchsteigt. Vielleicht poste ich den über Weihnachten