Mehrsimensionales Array logisch vervollständigen

B

blauerzettel

Grünschnabel
Hallo,

zuerst einmal entschuldige ich mich für mein Fauxpas mich in einem Forum anzumelden und direkt Fragen zu stellen. Der Grund dafür ist folgender...

Ich lerne zur Zeit C++ aus einem Buch (C++ für Spieleprogrammierer) obwohl ich das Buch noch nicht vollständig durchgelesen habe brennt es mir unter den Fingern ein spezielles Programm zu schreiben...
Dieses Programm soll in der Lage sein Sudokus selbstständig zu lösen.
Bisher konnte ich ohne Probleme ein mehrdimensionales Array erzeugen und in dieses meine Werte eintragen. Die eingetragene Werte (0-9, wobei 0 für ein noch leeres Feld steht) werden auch direkt auf ihre legalität überprüft, nun kommt allerdings der wichtigste Teil, man könnte es auch als "Herzstück" des Programmes bezeichnen. Das Programm soll nun selbstständig die fehlende Teile ersetzen, dazu möchte ich es erst das Array durchsuchen lassen und Felder in denen nur eine Möglichkeit zur Verfügung steht direkt ausfüllen lassen.
Sollte es dannach noch freie Felder geben so sollen diese mittels Brute-Force gelöst werden.
Doch Schritt für Schritt...
Wir stellen uns vor in einem 3x3 Feld großen Array (für Übungszwecke muss es ja nicht gleich das 9x9-Feld sein) wäre nur eine 0 eingegeben, das Array sieht also z.B. folgendermaßen aus:

123
406
789

Jetzt soll das Programm von selbst erkennen, welcher Wert sich in das freie Feld eintragen lässt, ich habe mir bereits darüber den Kopf zerbrochen komme allerdings auf keine anständige Lösung...
Sollte Quelltext vom bereits fertigen Teil gewünscht werden einfach schreiben :)
Ich hoffe ich habe meine Frage in einem verständlichen Deutsch geschrieben, als Schwabe muss ich zugeben habe ich ab und an meine Probleme mit "Hochdeutsch" :D

Ich würde mich über Hilfe wirklich freuen!

MFG: blauerzettel

Ich habe mich doch dazu durchgerungen euch einfach einmal den kompletten Quelltext anzugeben, wen es nicht interessiert der kann ja einfach weiterscrollen ;)
Vielleicht kann mir ja auch der eine oder andere noch ein paar Tipps zu meinem Quellcode und zum sauberen Programmieren geben (das ist das erste mal das 3. Personen von mir geschriebenen Quellcode zu Gesicht bekommen).
Dadurch das ich bisher noch nicht sonderlich viel zu C++ gelernt habe wundert euch bitte nicht wenn einige Befehle komplizierter geschrieben sind als nötig.
So und nun der Quellcode:

PHP: 
/*
Sudokulöser Version 1.0
Autor: Tim Sottona
Start des Projektes: 21.12.2009
Vorraussichtliches Veröffentlichung: Zusammen mit Duke Nukem Forever :D
*/

#include <iostream>

using namespace std;

//Hauptprogramm
//
int main ()
{
	//Konstanten
	//
	const int Breite = 3; //Breite eines Sudoku-Feldes
	const int Hoehe = 3; //Höhe eines Sudoku-Feldes

	//Variablen
	//
	int Feld [Breite] [Hoehe];	//Zweidimensionales Sudoku-Feld
	int Eingabe = 1; //Benutzereingabe des Wertes des Feldes
	int i=0, p=0, q=1, m, n, x, y;	// Schleifenzähler
	int xWert0;
	int yWert0;
	//Begrüssungstext
	//

	cout << "Willkommen!" << endl;
	cout << "Dies ist der Sudokuloeser von blauerzettel V1.0" << endl;

	
	//Weiter im Begrüssungstext
	//

	cout << "Das Programm wurde nun vollstaendig geladen!" << endl;
	cout << "Wir werden erst eine kleine Initialisierung durchfuehren..." << endl;
	cout << "hierbei wird ueberprueft ob das Programm alle Daten richtig geladen hat!" << endl;
	cout << "Bedenken Sie beim eingeben der Werte das diese Zeile fuer Zeile eingegeben werden!" << endl;
	cout << "Bitte geben Sie jetzt ihre Werte ein!" << endl;

	//Sudoku-Feld mit Werten füllen + zzgl. Überprüfung der Werte auf Ihre Legalität
	//
	for (y=0; y<Hoehe; y++)
	{
		for (x=0; x<Breite; x++)
		{
			cin >> Eingabe;
			//Überprüfung >9
			//
			while (Eingabe > 9)
			{
				cout << "Der von Ihnen eingegebene Wert ist groesser als 9!" << endl;
				cout << "Bitte geben Sie einen neuen Wert ein!" << endl;
				cin >> Eingabe;
			}
			//Überprüfung <0
			//
			while (Eingabe < 0)
			{
				cout << "Der von Ihnen eingegebene Wert ist kleiner als 0!" << endl;
				cout << "Bitte geben Sie einen neuen Wert ein!" << endl;
				cin >> Eingabe;
			}
			//Überprüfung doppelte Werte mit Ausnahme 0
			if (Eingabe != 0)
			{
				for (m=0; m<Breite; m++)
				{
					for (n=0; n<Hoehe; n++)
					{
						if (Eingabe == Feld [n] [m])
						{
							cout << "Der Wert wurde bereits eingegeben!" << endl;
							cout << "Bitte geben Sie einen neuen Wert ein!" << endl;
							cin >> Eingabe;
						}
					}
				}
			}
			Feld [x] [y] = Eingabe;
			cout << "Bitte geben Sie den nächsten Wert ein!" << endl;
		}
	}

	//Überprüfung ob das Sudoku gelöst werden kann (1 Zahl fehlt)
	//Speichern der 0-Koordinaten
	for (y=0; y<Hoehe; y++)
	{
		for (x=0; x<Breite; x++)
		{
			if (Feld [x] [y] == 0)
			{
				p++;
				xWert0 = x;
				yWert0 = y;
				cout << p << endl;
				cout << xWert0 << endl;
				cout << yWert0 << endl;
			}
		}
	}
	if (p != 1)
	{
		cout << "Das Sudoku kann nicht gelöst werden!" << endl;
	}
	//Genau 1 Zahl fehlt 
	//
	else
	{
		i=0;
		while (i <= 15)
		{
			for (m=0; m<Breite; m++)
			{
				for (n=0; n<Hoehe; n++)
				{
					i++;
					if (q == Feld [m] [n])
					{
						q++;
					}
				}
			}
		}
		Feld [xWert0] [yWert0] = q;
	}	
	//Sudoku-Feld ausgeben
	//
	for (y=0; y<Hoehe; y++)
	{
		for (x=0; x<Breite; x++)
		{
			cout << Feld [x] [y];
		}

		cout << endl;
	}

	return 0;
}

Über Hilfe und konstruktive Kritik würde ich mich sehr freuen!

MFG: blauerzettel
 
Zuletzt bearbeitet:
Am besten zu schreibst erstmal 3 Funktionen, welche überprüfen ob
1. Eine ganze Reihe korrekt gesetzt ist
2. eine Spalte korrekt gesetzt ist
3. diese Box(wie du sie gepostet hast) korrekt gesetzt ist

Soa es gibt 2 möglichkeiten, entweder du setzt eine Zahl hinein (ganz iterativ) und überprüfst ob diese stehen bleiben darf, oder du guckst dir erst an ob die Zahl, wo du gerade angekommen bist gesetzt werden darf.

Ich erläuter das mal an deinem Feld. Nun fehlt ja die 5. Dein Programm fängt bei 1 an zu iterieren, dann kommt deine Fkt die diese Box dort überprüft, der Funktion wird die 1 vorgeschlagen. Die Funktion soll liefern "nein", dann die 2 gefragt werden usw (bis theoretisch 9), jedesmal zählt deine Funktion durch dein Feld und guckt ob die Zahl gesetzt werden darf oder bereits vorhanden ist. Wenn nein wie im Falle der 5 darf sie gesetzt werden (nicht vergessen das ganze Feld durchzugehen, da die 5 ja auch an letzter Stelle stehen kann).

Dieser 3x3 Block ist beim Sudoku etwas tricky versuchs mal mit dem Modulo-Operator. Falls du doch nicht drauf kommst kann ich dir auch diese Funktion geben. Aber versuchs erstma selbst. ;)

Gruß Jennesta
 
So das ist ja hier mein Hauptthema ^^

Ich bin schon seid längerem dabei ein Sudoku lösendes Programm zu schreiben. Mein Code löst bereits 9X9 Sudokus, der leichteren Schwierigkeit, spricht, wenn es zumindest immer eine eindeutige Lösung gibt. Für schwierigere Sudokus steht mein Gerüst auch schon, habe ich allerdings noch nicht ganz fertig, habe da im Moment auch nicht soviel Zeit zu.

So nun zu den Tips :

Sofern dein Code effizient arbeiten soll, ist es sinvoll mit "Pools" zu arbeiten.

Ich habe in meinem Fall, einen Pool, der 9 mal die zahlen 1-9 enthält (2D-Array). Die vorgegebenen Zahlen aus einem Sudoku, werden aus diesem Pool entfernt. (entsprechend Spalte/Zeile aus dem entsprechenden Array-Bereich)

Aus diesem Array wird das Haupt-Sudoku-Array befüllt, so kann Sudoku nur Zahlen erhalten, die es auch nur noch braucht. (Du musst natürlich eine parallele zwischen dem Pool und Sudoku in Beziehung zu der z.B. entsprechenden Zeile oder Spalte schaffen.)

Dann kannst du das Sudoku (2-D-Array) am anfang mit 0 initialisieren, vorgebene Zahlen müssen eingetragen werden, und bei der Befüllung einfach überprüfen, ob Sudoku[x][y] == 0 ist, wenn ja, hier darf etwas eingesetzt werden.

Ich verfahre nicht mit Brutforce, weil es wiegesagt nicht sehr effizient ist, wenn du das vielleicht auch in Erwägung ziehen willst, kannst du auf folgende Weise verfahren:

Du legst 2 weitere Pools an (2-D-Arrays) Namens Spalte[][] und Zeile[][] .
In diesen sperrst du Zeilen und Spalten, für bereits vorhandene Zahlen in diesen Spalten/Zeilen. Quasi so wie du vorgehst, wenn du selbst per Hand ein Sudoku löst.

Dann hast du als Kriterien zum einem "wenn Sudoku[x][y] == 0" und "wenn Spalte[][] und zeile[][] nicht gesperrt (spricht Zahl noch nicht vorhanden), dann kann diese hier unter umständen eingesetzt werden.
Um herrauszufinden ob es eine eindeutige Lösung gibt, kannst du einen Count verwenden, der sich erhöht für jede Möglichkeit, an der diese Zahl erlaubt wäre, wenn dieser Count == 1 ist, spricht nur eine Möglichkeit --> eindeutig --> setze ein.

So das war mal im Schnellverfahren mein grober Ansatz, die Prüfungen für die Spalten und Zeilen sind natürlich nicht ganz einfach, du musst genau aufpassen wie du die Arrays befüllst / löscht. (wenn eine Zahl eingesetzt wird muss sie natürlich aus den entsprechenden Pools entfernt bzw eingefügt werden, auf diese Weise wird das Programm fortlaufend schneller.

Ich hoffe ich konnte dir helfen, Detailfragen kannst du gerne stellen, ich guck ab und zu vorbei.

Mfg Dragonate
 
Zuletzt bearbeitet:
Hallo BlauerZettel,
zunächst eine Bemerkung zur Eingabedatenprüfung.
Code: 
if (eingabe < 0) {
  cout << "...";
  cin >> eingabe;
}
Was passiert, wenn der Benutzer von Natur aus frech ist und ein zweites Mal eine Zahl <0 eingibt? Deshalb besser
Code: 
while (eingabe < 0) {
  cout << "...";
  cin >> eingabe;
}
Zur Lösungsstrategie: Bei Problemen mit wenig Variablen kommt man oft durch systematisches Ausprobieren ans Ziel. Z.B. erste freie Zahl auf erstes freies Feld. Wenn Matrix i.O., dann nächste freie Zahl auf nächstes freies feld. Wenn Matrix nicht i.O. dann Abbruch und nächste Zahlenkombination durchprobieren, usw.
Das ganze sollte rekursiv gestaltet werden.
 
Kann man so machen wie Onkel Schuppig sagt, ist aber uneffizient. Und ein 9x9 Sudoku bietet eine beachtliche Anzahl an Möglichkeiten.
Meine Strategie lässt sich auch mit Backtracking kombinieren, in dem du eine rekursion verwendest.

Achso und noch ein Hinweis was mir gerade an deinem Code aufgefallen ist @ Blauerzettel, die Überprüfung ob die Zahl bereits eingegeben wurde ist nicht ganz Korrekt, sie kann unter Umständen noch doppelte Werte zulassen.
Wenn im späterem Verlauf deiner Doppelschleife, entdeckt wird das es diese Zahl bereits gibt, gibst du eine neue ein, dann läuft die Schleife aber noch etwas weiter, und prüft den neueingegebenen Wert nur noch auf die hinteren Felder, das solltest du noch korrigieren.

Mfg Dragonate
 
Zuletzt bearbeitet:
Zuerst einmal vielen Dank für eure bisherige Hilfe, dass es hier so schnell geht hätte ich echt nicht erwartet!
Ich habe mir bis jetzt alle bisherigen Beiträge durchgelesen und sogar, wie es für fleissige Schüler Normalität ist, Wörter die ich nicht verstanden habe nachgegoogelt (<- cooles Wort :D). Trotzallem würde es mich freuen wenn ihr veruschen würdet auf "Einsteigerprogrammiererisch" (<- noch colleres Wort :D:D) zu sprechen.
Bisher knoble ich immer noch darüber nach wie ich das Programm dazu bringen kann mir eine freie Stellen (0) durch die entsprechende Zahl zu ersetzen. Allerdings ohne dieses Knobeln wäre Programmieren auch verdammt langweilig von daher lasst mir noch ein paar Tage Zeit es selber zu versuchen ( Tipps ja gerna - Quellcode nein danke)
Besonders bedanken möchte ich mich auch noch einmal bei den Usern die sonstige Fehler in meinem Quelltext entdeckt haben, mir wären diese vllt. nie aufgefallen!

Edit:
Ich habe jetzt endlich eine Lösung für mein Problem gefunden :)
Auch wenn ich bereits weis das es 100 schnellere und bessere Lösungen gibt wie meine umständliche Alternative bin ich doch recht stolz darauf es (mehr oder weniger) alleine geschafft zu haben.
Ausserdem ist das Programm perfekt zum Urlaub fertig geworden von daher bitte nicht wundern wenn ich mich die nächste zeit nicht melde, ich bin immer noch an euren Meinungen interessiert!
Ich bin einfach so frei und editiere meinen Quelltext auf den neuesten Stand ihr könnt es euch ja mal anschauen und eure Meinung dazu äussern!
MFG: blauberzettel
Schöne Weihnachten und `nen guten Rutsch!
 
Zuletzt bearbeitet:
@ Matthias : Naja etwas anders ist es schon , bei mir wird nach der richtigen Zahl für ein Feld gesucht, irgendwo steckt da in Konsequenz auch ein gewisses Ausprobieren drin, aber es is doch schon eher finden statt ausprobieren.

@ Blauerzettel

Lass eine Schleife durchlaufen mit den Zahlen 1-9, und setzte einen Wert davon ein. Jenachdem nach welchem Verfahren du jetzt vorgehst, probierst du alle aus, oder lässt anhand von Kriterien nur eindeutige Zahlen einsetzen, das wäre der Fall wie ich ihn dir beschrieben habe.

In nächster Konsequenz, solltest du auch eine Lösungsfunktion schreiben, die Prüft wann Sudoku gelöst ist.
Das ist in meinem Fall wenn alle Felder einen Wert bekommen haben, und anhand der Vorkretierien ist bereits sichergestellt, das es die richtigen Werte sind.
Oder z.B. eine Schleife die Zeile für Zeile des Sudokus addiert und jede Zeile muss ==45 sein, wenn das für alle 9 Zeilen gewährleistet ist, ist dein Sudoku gelöst.

Mfg Dragonate
 
Dragonate hat gesagt.:
Oder z.B. eine Schleife die Zeile für Zeile des Sudokus addiert und jede Zeile muss ==45 sein, wenn das für alle 9 Zeilen gewährleistet ist, ist dein Sudoku gelöst.

Mfg Dragonate
Zum Vergrößern anklicken....

Würde ich vorsichtig sein ;) Falls du zwei Werte falsch gesetzt haben solltest (könnte ja sein), könnte die Summe ebenfalls 45 sein. Besser wäre prüfen, wie du selbst ein Sudoku auf Richtigkeit prüfst.

Sagmal wie lange braucht dein Programm für die Lösung eines Sudokus?
Gruß
 
Ja in meinem Fall ist durch Vorbedingungen bereits gewährleistet das keine Zahl an der falschen stelle steht.
Aber das muss in seinem Fall natürlich auch erstmal gewährleistet sein, hast du recht.

Ähm gute frage, muss ich morgen auf der Arbeit mal testen, da hab ich den Code.

Bisher funktioniert es ja vollständig nur bei etwas leichteren Sudokus, und die werden auch super fix gelöst, guck ich morgen mal aber das Programm ist sofort fertig.
 
Um antworten zu können musst du eingeloggt sein.

Neue Beiträge

Zurück