Sudoku programmieren

[truesoul]

Morgen allerseits,

also wie schon der Titel des Threads sagt programmiere ich zur Zeit Sudoku was im Prinzip schon fertig ist.
Warum ich nun diesen Thread eröffnet habe ist, ob es doch bessere Arten gibt da ran zu gehen.
Der erste Punkt ist das Generieren vom Sudoku. Ich generiere auf dieser Weise ein Sudoku:

Schritt 1:
Ich fülle ein Array von 1-9 und vermische dann die Zahlen.
Aussehen:

3 4 2 5 1 6 9 7 8

Schritt 2:
Jetzt erstelle ich ein 2D Array [9][9] ( [Horizonal][Vertikal] ) und die erste Horizontale Liene(Bahn) bekommt die Zahlen die ich genieriert habe( Siehe Array (1-9) ) . Und so fülle ich anschliessend das 2D Array:

342 516 978 ---> 2D Array [0][0-8]
978 342 516 ---> 2D Array [1][0-8] ( Um 3 versetzt )
516 978 342 ---> 2D Array [2][0-8] ( Um 3 versetzt )

834 251 697 ---> 2D Array [3][0-8] ( Um 4 versetzt )
697 834 251 ---> 2D Array [4][0-8] ( Um 3 versetzt )
251 697 834 ---> 2D Array [5][0-8] ( Um 3 versetzt )

783 425 169 ---> 2D Array [6][0-8] ( Um 4 versetzt )
169 783 425 ---> 2D Array [7][0-8] ( Um 3 versetzt )
425 169 783 ---> 2D Array [8][0-8] ( Um 3 versetzt )

Schritt 3:
So und anschliessend vertausche ich jede Horizontale per Zufall miteinander:

516 978 342
342 516 978
783 425 169

251 697 834
425 169 783
978 342 516

834 251 697
169 783 425
697 834 251

Schritt 4:
Und nachdem das alles geschehen ist ersetzte ich per Zufall im 2D Array Zahlen mit 0 , dementsprechend welche Schwierigkeit eingestellt ist.
Überprüfe natürlich auch ob schon 0 vorhanden und suche neue Position wenn ja.

016 908 000
300 006 900
000 020 009

001 000 030
005 109 003
900 040 010

000 200 600
100 003 400
097 030 201

Und dies fülle ich dann JLabels ( Ohne 0 ).

1 Frage: Was haltet ihr von dieser herangehensweise?

Meine zweite Variante wäre noch das ich wieder ein Array erstelle wie in Schritt 1 geschehen und dann auch die erste Reihe mit den Zahlen fülle und ab 1-8 für jede Reihe per Zufall für jedes Kästen eine Zahl genierieren und überprüfen ob Vertikal ( 0 - aktuelleReihe-1 ) die Zahl schon vorhanden ist , wenn ja neue Zufallszahl.
Ich muss auch nicht jedes Mal Vertikal von 0-8 laufen , sondern ab da wo es schon korrekt war.
Ich änder im Prinzip Schritt 2-3.

Natürlich ist diser aufwand größer als die erste Variante, da ich überprüfen muss ob Zahl schon vorhanden. ( Siehe Zeilen oberhalb )

2 Frage: Welche von den beiden herangehensweisen würdet ihr bevorzugen?

Zur Zeit benutze ich die erste Variante!!!

3 Frage: Habt ihr andere herangehensweisen die Ihr mir empfehlen würdet?

So jetzt möchte ich eine eigene Variante von Sudoku erstellen.
Nämlich Mathematisches Sudoku. Gemeint ist damit:

Ich habe eine Reihe von:

|9|3|0| # |12|15|0| # |18|21|24| ---> Multipliziert mit 3

Wenn der User jetzt auf das leere Kästchen klickt erscheint ein Popup wo er dann eine Auswahl hat.
Die Auswahl soll nicht so ausschauen : 3 6 9 12 15 18 21 24 --
Sondern mit Mathematische Rechnungen, also für die fehlende Zahl 6 z.B:

6 = (6*6)/10-12 für den richtigen fall!
und natürlich noch 8 Rechnungen die aber die Zahl 6 ergeben sondern : 3 9 12 15 18 21 24
Die Auswahl ist natürlich durcheinander!

Überlege noch ob ich die Formel im Kästchen anzeigen lassen und erst die Entsumme beim erfolgreichen Lösen oder von der Rechnung direkt das Ergebnis anzeigen lasse.Aber das spielt jetzt keine Rolle.

Meine Überlegungen bisher waren das ich eine Datei habe für mehrere Mathematische wege für z.B die 6 gibt , sprich:

6:

- (6*6)/10-12
- ((4*12)-13)/5-1
- (120/2)/10
usw...

Diese Variante gefällt mir aber nicht!!!

Frage 4 und die wichtigste frage :
Wie kann man es umsetzen das ich Mathematische Rechnung generieren für die 3,6,9 usw ?


P.S ... Ich Multipliziere nicht nur mit 3 sondern von 2-20 z.B

Übrigens soll es für eine Schule sein.

Ich freue micht auf eure Beiträge und Hilfe !! :toll:

 

[Sonecc]

Das von dir abgebildete Sudoku (das fertige) ist ungültig. Außerdem verstehe ich nicht, warum du die zeilen verschiebst..

516 978 342
342 516 978
783 425 169

251 697 834
425 169 783
978 342 516

834 251 697
169 783 425
697 834 251

Der erste Block besitzt 2 mal eine 3. (Fett markiert)
Mehr hab ich mir nich angeschaut, aber das solltest du überprüfen^^

 

[truesoul]

Oh , danke für diesen Hinweis.
Tausche nun nur innerhalb eines Blockes, sprich:

123 456 789 ---->
789 123 456 ----> Block 1
456 789 123 ---->

912 345 678 ---->
678 912 345 ----> Block 2
345 678 912 ---->

usw....

Also tausche ich innerhalb Block 1, 2 und 3 die reihen.
Damit sollte es ausgeschlossen sein , gleiche Zahlen im Block zu haben!
Danke nochmals

 

[Sonecc]

Ich persönlich würde übrigens Methode 2 bevorzugen..
Methode 1 wirkt mir persönlich nicht zufällig genug, recht schnell lässt sich dann beim lösen ein Muster finden (beispiel: ich habe die Zahlen 251 gefunden, nun weiß ich schon, dass rechts daneben eine 6 und links daneben eine 4 sein muss usw. (siehe beispiel aus dem ersten Code)

 

[truesoul]

Jep, das war mir leider auch bewusst.
Das man irgendwann ein Muster erkennt , genauso wie du es beschrieben hast.
Die erste Variante ist halt schneller generiert ob ein großer zeitlicher unterschied zu Methode 2 besteht sei dahin gestellt
Aber ich denke die zweite Methode ist besser wenn nicht nur Kinder dieses Programm nutzen wollen.

Danke schonmal

 

[Sonecc]

Ich habe einen Sudokusolver geschrieben, der per Backtracking ein Sudoku löst.
Egal wie schwer das Sudoku ist, innerhalb von einem bruchteil einer Sekunde war es gelöst.
Das bedeuted, dass ein erzeugen eines sudokus auf Basis eines solchen Solvers keinen großen zeitlichen Aufwand bringen würde.

 

[truesoul]

Nunja , einige Fragen sind ja noch offen wie das mit den Mathematische Rechnung .
Ob diese herangehensweise ok ist , mit der Datei für die Rechnungen und ob es doch ne möglichkeit gibt diese Rechnung generieren zu lassen?

Mfg

 

[Sonecc]

Es wäre auch möglich sie zu berechnen.
Naiv ohne groß drüber nachgedacht zu haben, sollte das auch nicht schwierig sein.
So könnte man eine zufällig lange Rechnung wählen.
Beispiel 5 Schritte, zur Berechnung einer 6:

Zufallszahl als startwert: 3 <- 3 < 6, also benutzen wir entweder + oder * (per Zufall bestimmt)
Neue Zufallszahl: 3 + 8 = 11 <- 11 > 6, also benutzen wir entweder - oder / (per Zufall bestimmt)
Neue Zufallszahl: 3 + 8 / 2 = 7 <- 7 > 6, also benutzen wir entweder - oder / (per Zufall bestimmt)
Neue Zufallszahl: 3 + 8 / 2 - 1 = 6 <- 6 = 6 ... Fertig, Schritt 5 nicht nötig

Das ganze Bedarf natürlich einiger Überprüfungen, so darf keine ungerade Zahl durch eine gerade geteilt werden, z.B.

Mit ein bisschen probieren sollte das nicht zu schwer werden.

Wie gesagt ist das nur eine naive Überlegung

 

[truesoul]

Muss leider zugeben, das mir grad aufgefallen das ich meine 2 Methode so nicht verwenden kann wie ich erst gedacht habe

Also :

Meine Überlegung war das ich die erste stelle vom 2D Array mit Zufallszahlen von 1-9 fülle.
( Siehe Schritt 1 )

Danach gehe ich so an die Sache ran:

ich überprüfe im ZweiArray alle schon vorhanden zeilen mit der neu erstellen gemischten Reihe.

Im Prinzip so:

public void generiereSudoku (int array[][] , int Size , int array[] )
{
        tmp = mixed(tmp); // Hier mische ich die Zahl von 1-9 in neuer Anordnung

        for( int j = 0; j < Size ; j++ ) // Size == wieviel Reihen schon vorhanden?? Size am Anfang 1
        {
            for( int i = 0; i < 9 ; i++ )
            {
                if( array[j][i] == tmp[i]) // vergleiche die Reihen mit dem Array der neuen Reihe
                {
                    // wurde eine treffer gelandet mische eine neue Anordnung
                    tmp = mixed(tmp); 

                    j = -1;                   // jetzt gehts von vorne los
                    System.out.println("break");
                    break;
                }

            }
        }

        for( int j = Size; j < Size+1 ; j++ ) 
        {
            for( int i = 0; i < 9 ; i++ )
            {
                array[j][i] = tmp[i]; // Diese Reihe sollte jetzt stimmen
            }
        }

        Size++;
        if(Size < 9)
            generiereSudoku(array, Size , tmp);

}

leider führt es nicht zum gewünschten Erfolg.
Es führt zu einer unendlichen Schleife
Und ausserdem überprüfe ich nicht nach schon vorhandene Zahlen in einem Block.

Die Hitze tut dann noch sein übriges.

Wie kann ich es generieren und alle Bedingung stimmen ?

 

[Gast2]

Ich würde einfach nach und nach Zahlen hinzufügen.

Nehmen wir mal an du hast 81 Felder und möchtest 50 Zahlen vorbelegen.
Pseudocodemäßig:

while (weniger als 50 Zahlen gesetzt) {
    Point pos = eine zufällige freie Position;
    int number = [1..9];
    Prüfe ob die Zahl number an Stelle pos gültig ist. (zeile/spalte/block prüfen)
    Wenn ja, Zahl setzen, gesetzte_zahlen-counter um 1 erhöhen
    Wenn nein, nächsten schleifendurchlauf
}

Das wäre jetzt mal ne "Haudrauf Variante", vielleicht passierts dir hierbei aber auch dass du ein Soduko erstellst dass nicht lösbar ist, das weiß ich nicht.

 

[Sonecc]

@truesol:

Deine Methode kann auch nicht funktionieren.

Nehmen wir mal das gemischte Feld vom Anfang: 3 4 2 5 1 6 9 7 8
Nach dem ersten Aufruf der Methode hast du dann folgendes Ergebnis:

3 4 2 5 1 6 9 7 8

Beim zweiten Aufruf prüfst du nun die erste Zeile auf den Inhalt von 3 2 4 1 5 7 9 6 8 (neu gemischtes tmp)
Also:

i = 0; j = 0;
array[j] = array[0][0] = 3
tmp = tmp[0] = 3
3 = 3

Nun mischst du dein tmp und fängst von vorne an.

Sei tmp nun = 8 2 4 1 5 7 9 6 3

Die 8 ist aber schon vorhanden, weswegen das ganze wieder neu gestartet wird usw.

 

[truesoul]

Danke EikeB aber ich bekomme dies einfach nicht auf die Reihe.
Am Ende ist das alles so verschachtelt und endet im Fiasko.

Hmm , ich muss mir das morgen nochmal anschauen.
Mfg

Edit:

public void generiereSudoku(int Index , int array[][] , int Size )
    {

        int array2D [][] = array;

        int tmP[] = { 4,7,9, 8,5,6, 2,3,1 };
        tmP = mixed(tmP);

        for(int i = 0; i < Size; i++ )
        {
            for( int j = 0; j < 9 ; j++ )
            {
                if( array2D[i][j] == tmP[j])
                {
                    tmP = mixed(tmP);
                    i = -1;
                    j = 9;
                }
            }
        }

        int array2Neu[][] = new int[Size+1][9];
        for( int i = 0; i < Size+1; i++)
        {
            for(int j = 0; j < 9 ; j++ )
            {
                if( i < Size)
                    array2Neu[i][j] = array2D[i][j];
                else
                    array2Neu[i][j] = tmP[j];
            }
        }

        Size++;
        if( Size <= 8)
        {
            generiereSudoku(Index, array2Neu, Size);
        }
    }

Dies Funktioniert mit ausnahme der überprüfung vom Block!
Leider weiß ich nicht wie ich es jetzt umsetzen soll , das es auch blockweiße überprüft.

 

[Sonecc]

vielleicht hilft dir ja folgendes: (Bitte ignorieren dass die Kommentare auf deutsch sind, sie sollten natürlich eigentlich besser auf englisch sein...)

	/**
	 * Prüfe ob value gültig eingesetzt werden kann
	 * @param row Zeile
	 * @param column Spalte
	 * @param value Der Wert der geprüft werden soll
	 * @return true wenn a gültig ist
	 */
	private boolean check(int row, int column, byte value) {
		//Zeile durchlaufen und prüfen ob value dort schon vorhanden ist
		for (int k = 0; k < 9; k++) {
			if (fields[k][column] == value) {
				return false;
			}
		}
		//Spalte durchlaufen und prüfen ob value dort schon vorhanden ist
		for (int k = 0; k < 9; k++) {
			if (fields[row][k] == value) {
				return false;
			}
		}
		//Block durchlaufen
		//Ermittle die aktuelle startspalte des Blocks
		int blockColumn = (int) (column/3 * 3); 
		//Gleiches mit der Zeile
		int blockRow = (int) (row/3 * 3);
		//Durchlaufe den Block
		for (int k = blockRow; k < blockRow + 3; k++) {
			for (int l = blockColumn; l < blockColumn + 3; l++) {
				if (fields[k][l] == value) {
					return false;
				}
			}
		}
		// value wurde nirgends gefunden
		return true;
	}

Diese Methode prüft ob ein gegebener wert in einem Sudoku Feld korrekt ist.
Wenn ja, gibts true zurück, wenn nein gibt es false zurück.
Damit kannst du dann prüfen, ob ein von dir gesetztes Feld richtig ist oder nicht und auf dieser Basis bestimmen, ob du einen neuen Wert setzen musst...

 

[truesoul]

Herzlichen Dank schonmal für deine Mühe.
Werde es zu hause einbauen und testen aber es sieht so ziemlich vielversprechend aus.
Wirklich danke.

Melde mich sobald ich es testen konnte

Mfg

 

[truesoul]

So ich nun nochmal.
Ich habe es mal bissl abgeändert und irgendwann kommt er in eine entlosschleife und gedebuggt habe ich und eigentlich müsste der aus der Schliefe springen , was er aber nicht tut?!?!?

public void generiereSudokuNeu()
    {
        
        int Zeile = 0;
        int Spalte = 0;
        int zahl = 0;
        int runde = 0;
        while(runde < 82)
        {
            Zeile = new Random().nextInt(8);
            Spalte = new Random().nextInt(8);
            
            while( !checkVorhanden(Spalte, Zeile) ) //steht schon was in dieser Zeile+Spalte??
            {
                // neue Zeile und Spalte
                Zeile = new Random().nextInt(8);
                Spalte = new Random().nextInt(8);
            }

            zahl = generiereZahl(); // 1 - 9
            System.out.println("Zeile: "+ Zeile + " Spalte: "+ Spalte +" Zahl: "+zahl + " ----> "+runde);
            
            while( !check(Zeile, Spalte, zahl) )
            {
                zahl = generiereZahl();
            }

            zweiDimisionArray[Zeile][Spalte] = zahl;
            runde++;
        }

    }

private boolean check(int Zeile, int Spalte, int value ) {

        //Spalte durchlaufen und prüfen ob value dort schon vorhanden ist
        for (int k = 0; k < 9; k++) {
            if (zweiDimisionArray[k][Spalte] == value) {
                return false;
            }
        }
        //Spalte durchlaufen und prüfen ob value dort schon vorhanden ist
        for (int k = 0; k < 9; k++) {
            
            if (zweiDimisionArray[Zeile][k] == value) {
                return false;
            }
        }
        //Block durchlaufen
        //Ermittle die aktuelle startspalte des Blocks
        int blockSpalte = (int) (Spalte/3 * 3);
        //Gleiches mit der Zeile
        int blockZeile = (int) (Zeile/3 * 3);
        //Durchlaufe den Block
        for (int k = blockZeile; k < blockZeile + 3; k++) {
            for (int l = blockSpalte; l < blockSpalte + 3; l++) {
                if (zweiDimisionArray[k][l] == value) {
                    return false;
                }
            }
        }
        // value wurde nirgends gefunden
        return true;
    }

   public boolean checkVorhanden(int Spalte , int Zeile)
    {
        if(zweiDimisionArray[Zeile][Spalte] != 0)
            return false;

        return true;
    }

zweiDimisionArray ist mit 0 Initialisiert!
Die Variable zahl wird mit ein Zufallswert von 1-9 initialisiert.
Die while ( runde < 82 ) soll erstmal so sein , damit ich sehe kann ob alle kästchen korrekt sind!
Später wird die 82 variable sein.

Was mach ich jetzt falsch???

Danke schonmal für eure Hilfe!!

 

[Gast2]

Schreib mal in die beiden inneren while schleifen nen sysout.
Ich tippe drauf dass er in dieser while schleife hängen bleibt:

while( !check(Zeile, Spalte, zahl) ) { ... }

Du versuchst das komplette Feld zu füllen und du wirst irgendwann an einen Punkt kommen wo du dein Sudoku einfach nichtmehr lösbar ist.

 

[truesoul]

Ja genau da bleib ich hängen , habe wohl vergessen das zu erwähnen.
Mir ist ein kleiner fehler noch unterlaufen ,

Zeile = new Random().nextInt(9); // nicht 8 wie zuvor
Spalte = new Random().nextInt(9);

zahl = new Random().nextInt(10); // nicht 9

dachte immer das inklusiv wäre .

Aber das hat keine auswirkung auf das Ergebnis.
Also wird das Problem sein , das einer der drei Bedingung immer false ist oder sogar alle drei ???

 

[Gast2]

Ja du hast dir ein Spielfeld erzeugst bei dem du in ne sackgasse läufst.
Du versuchst ein Feld zu füllen, aber die Zahlen 1-9 sind nicht gültig. also haste da ne endlosschleife. Lass dir doch testweise mal das spielfeld ausgeben und die stelle für die du eine zahl suchst.

 

[truesoul]

Zeile: 1 Spalte: 4 Zahl: 6

090 573 001
405 100 078
003 024 090

050 800 010
000 010 307
800 000 405

100 060 520
628 090 030
009 700 840

Okay , jetzt blieb der mir in diesem fall hängen?
Also in der Spalte befindet sich dann schon mal ne 6, also sollte er eine neue Zahl bekommen.
Und genau da ist der punkt , keine Zahl wäre gültig.
Omg.

 

[truesoul]

Hmmm , muss ich nach jeden durchlauf überprüfen das das unausgefüllte Sudoku noch lösbar ist ?
Und wenn ja, und wenn der fall zu trifft das es nicht mehr lösbar ist, muss ich im Prinzip von vorne anfang ? Sprich:

mein 2D Array wird mit 0 initialisieren und dann wird füllen und nach jedem kästchen überprüfen ob es noch lösbar ist?

Und das alles so lange bis alle Kästchen voll sind?

 

[slawaweis]

3 Frage: Habt ihr andere herangehensweisen die Ihr mir empfehlen würdet?

die Ausschlussvariante, was eigentlich der Solver-Algorithmus ist.

1. Erstelle eine Datenstruktur, wo jedes Feld im Spiel 9 Werte aufnimmt und fülle es vollständig.
2. gehe durch jedes Feld einmal durch
3. aus den Werten, die noch übrig sind, wird per Zufall eine Zahl ermittelt. Diese Zahl ist die Zahl für dieses Feld.
4. die Zahl aus Punkt 3 wird aus dem restlichen Horizontalen, Vertikalen, sowie dem Quadranten entfernt.
5. wenn der Algorithmus fertig ist, wird jedes Feld genau eine Zahl enthalten und den Sudoku-Regeln entsprechen.

Slawa

 

[Gast2]

Ich würd das erstellen des Sudokus auch per Backtracking machen. Sprich, wenn du in einer Konstellation bist wo dein Sudoku nichtmehr gültig ist gehst du einen Schritt zurück und machst von dort dann weiter.
Das machst du solange bis du dein gewünschtes feld erstellt hast, z.b. 50 von 81 Feldern befüllt.

 

[truesoul]

Danke für eure Hilfe , habe es jetzt endlich hinbekommen , mit besagten Backtracking.
@Danke EikeB

:idea:

Wie würdet ihr an dem Punkt ran gehen , mit der Varianten für Mathematische Rechnung ( siehe Post #1 , unterer Bereich) ?

 

[bene_2808]

Ich weiß, die Meldung kommt ein bisschen spät, aber vielleicht kann hiermit ja noch jemandem geholfen werden.

Eine weitere Möglichkeit wäre die Folgende:

wie in Methode1 beschrieben: Vertauschen der Reihen innerhalb eines Blockes...

...und zusätzlich genau dasselbe, nur vertikal (also die Spalten werden innerhalb einer Blockspalte vertauscht).

Je nachdem, wie gut das Sudoku "gemischt" werden soll, müssen die Zeilen und Spalten oft oder eben nur ein paar mal getauscht werden.

Ich hoffe, ich habe das Vorgehen verständlich genug erklärt, damit es bei euch genauso gut läuft wie bei mir.