soduku_solver

znarf

Ich habe mich mal darin versucht einen rekursiver Algorithmus für das Lösen eines Sudoku-Rätsels zu basteln, aber irgendwie klappt es mit der Implementierung nicht ganz:

// sudoku_solver.cpp

#include<iostream>

void backtrack(int *sudoku, int *track) {
	bool row=true, column=true, quadrat=true;
	if(*(sudoku + *track)==9) {
		--track;
		backtrack(sudoku, track);
	}
	++(*(sudoku + *track));
	for(int i=0; i<9; ++i)
		if(*(sudoku+9*((*track-1)/9)+i)==*(sudoku+*track) && *track!=9*((*track-1)/9)+i) {
			row=false;
			break;
		}
	for(int i=0; i<9; ++i)
		if(*(sudoku+9*i+(*track-1)%9)==*(sudoku+*track) && *track!=9*i+(*track-1)%9) {
		column=false;
			break;
		}
	for(int i=0; i<81; ++i)
		if(*(sudoku+i)==*(sudoku+*track) && *track!=i && ((i-1)%9)/3==((*track-1)%9)/3 && ((i-1)/9)/3==((*track-1)/9)/3) {
			quadrat=false;
			break;
}

	if(row && column && quadrat) ++track;
	if(*track!=-1) backtrack(sudoku, track);
	}

int main() {
	int track[81];
	int *tracker=track;
	for(int *ptr1=track; ptr1-track<81; ++ptr1)
		*ptr1=-1;
	int sudoku[81];
	for(int *ptr2=sudoku; ptr2-sudoku<81; ++ptr2) {
		std::cin >> *ptr2;
		if(*ptr2==0) {
			*tracker=ptr2-sudoku;
			++tracker;
		}
	}
	backtrack(sudoku, track);
	for(int *ptr3=sudoku; ptr3-sudoku<81; ++ptr3) {
		std::cout << *ptr3 << " ";
		if((ptr3-sudoku+1)%3==0) std::cout << " ";
		if((ptr3-sudoku+1)%9==0) std::cout << "\n";
		if((ptr3-sudoku+1)%9==0 && ((ptr3-sudoku+1)/9)%3==0) std::cout << "\n";
	}
	return 0;
}

*Wird heute ev. noch mal durchkommentiert*

Das Problem liegt eindeutig im ersten rekursiven Aufruf der backtracking-Funktion (Zeile 30), aber ich kann mir einfach keinen Reim darauf machen und habe keine Ahnung, wie sich der seg fault beheben lässt. Bitte um Aufklärung eines Unwissenden.

Geh mal mit dem Debugger durch, damit lassen sich die Ursachen für solche Probleme recht leicht identifizieren.

Bitsy

Die Positionsformeln sind schon mal falsch! (tip: warum -1 bei *track?)
Dadurch sucht er sich tot.

for (int i=0; i<9; ++i)
  {
    int pos = *track/9;
    pos = pos*9 + i;
    if (*(sudoku+pos)==*(sudoku+*track) && *track!=pos)
    {
      row=false;
      break;
    }
  }
  for (int i=0; i<9; ++i)
  {
    int pos = *track%9;
    pos += 9*i;
    if (*(sudoku+pos)==*(sudoku+*track) && *track!=pos)
    {
      column=false;
      break;
    }
  }

...und die dritte fur Dich
Sieht übersichtlicher aus, und verliert bei /9 *9 nichts...

Dann stimmt was mit dem Zurücklaufen und der Abbruchbedingung nicht.
Wenn Du zurückläufst, rufst Du wieder rekursiv auf. Das geht dann aber wieder tiefer und nicht zurück! Da ist ein Umbau angesagt!!!

Bitsy

Ein schönes Testfeld zum Debuggen wäre auch angebracht:
(aber laß Dich nicht täuschen, wenn er hier nur mit geänderten Positionsformeln heil rauskommt...)

int sudoku[81] =
{
  7,9,5,2,6,3,8,1,4,
  3,0,4,8,5,1,7,9,2, // 6
  1,8,2,9,7,4,3,6,5,
  8,5,7,4,1,6,2,3,9,
  2,3,1,7,8,9,4,5,6,
  6,4,9,3,2,5,1,7,8,
  4,2,6,5,3,7,9,8,1,
  5,7,8,1,9,2,6,4,3,
  9,1,3,6,4,8,5,2,7
};

mit

//    int sudoku[81];
  for (int *ptr2=sudoku; ptr2-sudoku<81; ++ptr2)
  {
//      std::cin >> *ptr2;

oops - copyright verletzt! Ist aus der 'Logisch' vom Oktober... man verzeihe mir.

Bitsy

und nun tutto completti, weil doch einiges dazu zu sagen ist:

bool backtrack(int *sudoku, int *track)
{
  do
  {
    bool ok = true;

    ++(*(sudoku + *track));

    int i; // MSVC 6.0 @&+#...
    for (i=0; i<9 && ok; ++i)
    {
      int pos = *track/9; pos = pos*9 + i;
      if (*track==pos) continue;
      ok = *(sudoku+pos)!=*(sudoku+*track);
    }
    for (i=0; i<9 && ok; ++i)
    {
      int pos = *track%9; pos += 9*i;
      if (*track==pos) continue;
      ok = *(sudoku+pos)!=*(sudoku+*track);
    }
    for (i=0; i<9 && ok; ++i)
    {
      int x = *track%9; x/=3; x*=3; x+=i%3;
      int y = *track/9; y/=3; y*=3; y+=i/3;
      int pos = x + 9*y;
      if (*track==pos) continue;
      ok = *(sudoku+pos)!=*(sudoku+*track);
    }

    if (ok)
    {
      if (*(track+1)==-1)
        return true;
      if (backtrack(sudoku, track+1))
        return true;
    }
  }
  while (*(sudoku + *track) != 9);
  *(sudoku + *track) = 0;
  return false;
}

Der backtrack wird nun nur einmal gerufen.
Außerdem wird track selbst nicht mehr verändert - darf es auch nicht, weil es ja auf dem Stack liegt. Das track+1 macht es dann, beim Rücklauf wird mit dem dort ansässigen weitergearbeitet.
Ferner wird ein wichtiges return geliefert, daß nun entscheidet, ob es vorwärts oder rückwärts weitergeht, im Falle rückwärts müssen wir nämlich wieder in der Loop ankommen. Im Fehlerfall putzen wir auch schön mit dem Nulleintrag, wir könnten ja wieder dahin kommen.
In den for-loops ist das ok in der Abbruchbedingung mit eingebaut. Eins reicht.
Die Zeile mit continue ist nur für die Lesbarkeit, man sieht, daß dies eine Sonderbedingung ist, die zu einem 'early out' führt.
Für den Falle einer total leeren Matrix solltest Du 82 track-plätze reservieren

Hier noch ein hübscher Link für Logikrätselfreunde:
clicky

knivil

ok = *(sudoku+pos)!=*(sudoku+*track)

Wenn ich sowas sehe, wird mir uebel. Schon mal was von Abstraktion gehoert? Entwerfe ordentliche Datenstrukturen und arbeite mit diesen! Das verringert auch die Fehleranfaelligkeit.

znarf

@ Bitsy
Ja genau, das zweimalige Aufrufen der backtrack-Funktion war das Hauptproblem (die falsche Positionsrechnung ist mir dann auch aufgefallen) Danke, jetzt funktioniert es super.

@ knivil
Ich habe vor vier Monaten das erste mal das Wort Compiler vernommen. Im fortgeschrittenen Zustand sollte man - da hast du sicherlich Recht - wenn man schon mit einer auf oo ausgelegten Sprache programmiert oo schreiben, aber da beginne ich mich jetzt erst hineinzuarbeiten. Das würde momentan mein Verständnis sicherlich übersteigen, aber vielleicht könntest du ja mal erklärend aufzeigen, was du genau einkapseln würdest und wieso.

camper

knivil schrieb:

ok = *(sudoku+pos)!=*(sudoku+*track)
Wenn ich sowas sehe, wird mir uebel. Schon mal was von Abstraktion gehoert? Entwerfe ordentliche Datenstrukturen und arbeite mit diesen! Das verringert auch die Fehleranfaelligkeit.

Als ganz so schlimm sehe ich das nicht an, allerdings könnte die Verwendung passender Variablennamen helfen. Abgesehen davon dürfte die Verwendung des Trackerfeldes schlecht für die Geschwindigkeit sein, weil es dazu führt, dass die einzelnen Test umfangreicher werden.

bool conflicts(const int* sudoku, int x, int y, int value)
{
// es genügt, für kleinere x bzw. y zu prüfen, wenn zusätzlich auf
// Konflikte getestet wird, wenn wir über Vorbelegungen laufen
    for ( int i = 0; i < x; ++i )
        if ( sudoku[ y*9 + i ] == value )
            return true;
    for ( int i = 0; i < y; ++i )
        if ( sudoku[ i*9 + x ] == value )
            return true;
    for ( int i = y - y % 3; i < y; ++i )
        for ( int j = x - x % 3; j < x - x % 3 + 3; ++j )
            if ( sudoku[ i*9 + j ] == value )
                return true;
    return false;
}
bool backtrack(int* sudoku, int x, int y)
{
    if ( y > 8 ) // Am Ende des Feldes angelangt
        return true;
    if ( sudoku[ y*9 + x ] != 0 ) // Position bereits vorbelegt
    {
        return !conflicts( sudoku, x, y, sudoku[ y*9 + x ] )
            && backtrack( sudoku, ( x + 1 ) % 9, y + ( x == 8 ) );
    }
    for ( int value = 1; value < 10; ++value )
        if ( !conflicts( sudoku, x, y, value ) )
        {
            sudoku[ y*9 + x ] = value;
            if ( backtrack( sudoku, ( x + 1 ) % 9, y + ( x == 8 ) ) )
                return true;
            sudoku[ y*9 + x ] = 0;
        }
    return false;
}

Bitsy

knivil schrieb:

ok = *(sudoku+pos)!=*(sudoku+*track)
Wenn ich sowas sehe, wird mir uebel. Schon mal was von Abstraktion gehoert? Entwerfe ordentliche Datenstrukturen und arbeite mit diesen! Das verringert auch die Fehleranfaelligkeit.

Bei so einer Antwort wird's mir auch übel.
Der Ton in dem Forum ist mittlerweile unter aller Sau.
Immerhin hast Du nicht als unregistrierter 'kozzzer' gepostet.

Nicht jeder ist so weit fortgeschritten, daß er schon in Shanghai ohne deutsche Tastatur sitzt. Und viel mehr als ein [] hätte er auch nicht verbessern können.
Ansonsten hääte ich das gerne mal gesehen.