Suche Hilfe bei der C-Programmierung

[trfreak]

Hey,

Ich bin Informatik Student im Erstsemester und bräuchte Hilfe bei der Programmierung eines voll funktionsfähigen Sudoku.

Es geht um die rekursive Funktion zur Lösung eines Sudokus.

Wenn mir jmd helfen kann, könnt ihr mich gerne bei Skype adden.
Danke im Voraus

Skype: trfreak2

[sk8land​]

Wenn du bei so einer Aufgabe noch nicht einmal einen Lösungsansatz selbstständig hinbekommst, dann war das Informatikstudium die falsche Wahl.

[trfreak]

Originally Posted by sk8land​

Wenn du bei so einer Aufgabe noch nicht einmal einen Lösungsansatz selbstständig hinbekommst, dann war das Informatikstudium die falsche Wahl.

Bin dabei es zu lernen, also ist das wirklich keine Hilfe.
Das Sudoku habe ich hinbekommen, das funktioniert aufjedenfall schon.
Es wird auf Richtigkeit (Die 3 Regeln des Sudokus) überprüft.

[Serraniel]

Hilfreich wäre es, welche konkreten Probleme du bei der Lösung der Aufgabe hast, damit Leute dir effektiv helfen können. "Sudoku lösen" ist relativ weit gefasst, vor allem wird nicht einmal klar ob es ein algorithmisches Problem ist, du also nicht weißt was du effektiv tun musst, oder nur nicht weißt wie man es implementiert. Da solltest du konkreter werden und ggf. deine bisherigen (ggf. fehlgeschlagenen) Ansätze mit posten.


Notiz am Rande: Verweis auf Skype ist zudem nicht wirklich notwendig oder gern gesehen; wenn du dein Problem nicht öffentlich diskutieren magst (und somit ggf. anderen mit dem selben Problem in Zukunft damit eine Lösung zu bieten) brauchst du auch nicht öffentlich nach Hilfe fragen.

[warfley]

Für einen rekursiven Algorithmus musst du Basisfälle finden, und dann dein Problem darauf kollabieren lassen.

Der Basisfall bei Sudoku ist wenn ein Feld nur eine legale Belegung hat.
Für jedes Feld für das es mehrere Belegungen gibt musst du zunächst die freien Nachbarn (selbe reihe, selbe Zeile oder selbes Kästchen) auswerten.

Das ist aber nur das sehr simple grundgerüst, und alles andere als optimal (wobei ich Sudoku auch nicht rekursiv lösen würde). Wenn es aber keine anderen Einschränkungen gibt außer das es rekursiv sein muss kann man auch andere lustige Algorithmen basteln. z.B.

bool solveField(index) {
  if (index == fieldCount) return checkIfGameIsValid();
  else if (index) {
    gameFields[index] = rand() % 9;
    return solveField(index + 1);
  } else do {
    gameFields[index] = rand() % 9;
  } while (!solveField(index + 1));
  return true;
}

[sk8land​]

Originally Posted by warfley

Für einen rekursiven Algorithmus musst du Basisfälle finden, und dann dein Problem darauf kollabieren lassen.

Der Basisfall bei Sudoku ist wenn ein Feld nur eine legale Belegung hat.
Für jedes Feld für das es mehrere Belegungen gibt musst du zunächst die freien Nachbarn (selbe reihe, selbe Zeile oder selbes Kästchen) auswerten.

Das ist aber nur das sehr simple grundgerüst, und alles andere als optimal (wobei ich Sudoku auch nicht rekursiv lösen würde). Wenn es aber keine anderen Einschränkungen gibt außer das es rekursiv sein muss kann man auch andere lustige Algorithmen basteln. z.B.

bool solveField(index) {
  if (index == fieldCount) return checkIfGameIsValid();
  else if (index) {
    gameFields[index] = rand() % 9;
    return solveField(index + 1);
  } else do {
    gameFields[index] = rand() % 9;
  } while (!solveField(index + 1));
  return true;
}

Genau so ein Ansatz ist wahrscheinlich gefragt. Allerdings sollte man das (teilweise gefüllte) Feld in jedem Zwischenschritt validieren und nicht immer erst am Ende, damit die Rekursionen jeweils frühzeitig abbrechen. Ansonsten geht man quasi alle kombinatorischen Möglichkeiten durch. Weil das von der Größenordnung 9^81 sind, wird der Algorithmus nicht in absehbarer Zeit eine Lösung finden.