# Sudokulöser 4x4



## Dude! (24. Mrz 2010)

Hallo ich wollte einen Sudokulöser programieren.
Ich habe mir dabei was ausgedacht und umgesetzt fuktionieren tut er jedoch nichts. Es gibt keine Fehlermeldung, alles lässt sich kompilen doch es gibt keine Ausgage am Ende.

[JAVA=24]

import java.util.Scanner;
import java.util.Random;
public class Minisudoku {
	public static void main(String[]args){
		Scanner tastatur=new Scanner(System.in);
		Random generator=new Random();
		int x1, x2, x3,x4,y1,y2,y3,y4,z1,z2,z3,z4,q1,q2,q3,q4, e;

		System.out.println("Gebe die Zahlen ein. Leeres Feld =0");
		System.out.println("Die erste Reihe");
		x1=tastatur.nextInt();
		x2=tastatur.nextInt();
		x3=tastatur.nextInt();
		x4=tastatur.nextInt();
		System.out.println("2. Reihe");
		y1=tastatur.nextInt();
		y2=tastatur.nextInt();
		y3=tastatur.nextInt();
		y4=tastatur.nextInt();
		System.out.println("3. Reihe");
		z1=tastatur.nextInt();
		z2=tastatur.nextInt();
		z3=tastatur.nextInt();
		z4=tastatur.nextInt();
		System.out.println("4. Reihe");
		q1=tastatur.nextInt();
		q2=tastatur.nextInt();
		q3=tastatur.nextInt();
		q4=tastatur.nextInt();
		e=x1+x2+x3+x4+y1+y2+y3+y4+z1+z2+z3+z4+q1+q2+q3+q4;
		while (e!=0) {
		while (x1==0 || x1==x2 || x1==x3 || x1==x4 || x1==y1 || x1==z1 || x1==q1 || x1==y2)x1=generator.nextInt(4)+1;
		while (x2==0 || x2==x1 || x2==x3 || x2==x4 || x2==y2 || x2==z2 || x2==q2 || x2==y1)x2=generator.nextInt(4)+1;
		while (x3==0 || x3==x2 || x3==x1 || x3==x4 || x3==y3 || x3==z3 || x3==q3 || x3==y4)x3=generator.nextInt(4)+1;
		while (x4==0 || x4==x2 || x4==x3 || x4==x1 || x4==y4 || x4==z4 || x4==q4 || x4==y3)x4=generator.nextInt(4)+1;

		while (y1==0 || y1==y2 || y1==y3 && y1==y4 || y1==x1 || y1==z1 || y1==q1 || y1==x2)y1=generator.nextInt(4)+1;
		while (y2==0 || y2==y1 || y2==y3 && y2==y4 || y2==x2 || y2==z2 || y2==q2 || y2==x1)y2=generator.nextInt(4)+1;
		while (y3==0 || y3==y2 || y3==y1 && y3==y4 || y3==x3 || y3==z3 || y3==q3 || y3==x4)y3=generator.nextInt(4)+1;
		while (y4==0 || y4==y2 || y4==y3 && y4==y1 || y4==x4 || y4==z4 || y4==q4 || y4==x3)y4=generator.nextInt(4)+1;

		while (z1==0 || z1==z2 || z1==z3 && z1==z4 || z1==y1 || z1==x1 || z1==q1 || z1==q2)z1=generator.nextInt(4)+1;
		while (z2==0 || z2==z1 || z2==z3 && z2==z4 || z2==y2 || z2==x2 || z2==q2 || z2==q1)z2=generator.nextInt(4)+1;
		while (z3==0 || z3==z2 || z3==z1 && z3==z4 || z3==y3 || z3==x3 || z3==q3 || z3==q4)z3=generator.nextInt(4)+1;
		while (z4==0 || z4==z2 || z4==z3 && z4==z1 || z4==y4 || z4==x4 || z4==q4 || z4==q3)z4=generator.nextInt(4)+1;

		while (q1==0 || q1==q2 || q1==q3 && q1==q4 || q1==y1 || q1==z1 || q1==x1 || q1==z2)q1=generator.nextInt(4)+1;
		while (q2==0 || q2==q1 || q2==q3 && q2==q4 || q2==y2 || q2==z2 || q2==x2 || q2==z1)q2=generator.nextInt(4)+1;
		while (q3==0 || q3==q2 || q3==q1 && q3==q4 || q3==y3 || q3==z3 || q3==x3 || q1==z4)q3=generator.nextInt(4)+1;
		while (q4==0 || q4==q2 || q4==q3 && q4==q1 || q4==y4 || q4==z4 || q4==x4 || q1==z3)q4=generator.nextInt(4)+1;
		e=x1+x2+x3+x4+y1+y2+y3+y4+z1+z2+z3+z4+q1+q2+q3+q4;
		}
		System.out.println(x1+" "+x2+" "+x3+" "+x4);
		System.out.println(y1+" "+y2+" "+y3+" "+y4);
		System.out.println(z1+" "+z2+" "+z3+" "+z4);
		System.out.println(q1+" "+q2+" "+q3+" "+q4);
	}
}


[/code]


----------



## Sonecc (24. Mrz 2010)

wie wäre es mal mit vernünftigen variablennamen?
wie wäre es mal mit der vernünftigen verwendungen von { und }

aber zu deinem Problem:


```
e=x1+x2+x3+x4+y1+y2+y3+y4+z1+z2+z3+z4+q1+q2+q3+q4;
```

Dieser Ausdruck kann niemals 0 werden, deine while schleife (die einzige vernünftig geklammerte) kann damit nie enden


----------



## Dude! (24. Mrz 2010)

Vielen Dank!

Zu den Variablen:
Was sind denn bessere?
Hatte keine besseren dafür gefunden.

Zu den Klammern:
Ich habe gelernt, dass man, wenn man nur einen Befehl hat, keine Klammern braucht sondern ein Semikolon ausreichtl.
Erst wenn 2 Sache gleichzeitig geschehen soll braucht man diese.

Zum Fehler:
Vielen Dank. Dies hatte ich vergessen sollte eigentlich 40 sein.

Neue Frage:

Nun gibt er schon was aus, jedoch ist die nicht wirklcih die Lösung, da zT falsche Zahlen vorkommen


Konsole:

Gebe die Zahlen ein. Leeres Feld =0
Die erste Reihe
2
0
0
1
2. Reihe
0
3
4
0
3. Reihe
0
1
2
0
4. Reihe
4
0
0
3
2 4 3 1
1 3 4 4
3 1 2 2
4 2 1 3


hatte doch immer gesagt, dass der das tun soll solange die Zahl nicht gleich ist wie die iner reihe spalte oder feld.


----------



## SlaterB (24. Mrz 2010)

wie oft hast du das Programm schon getestet und dann immer 16 Zahlen manuell eingetippt?
das bringt doch gar nix, definiere im Programm 

x1=2;
und du sparst Jahrmillionen an Zeit, ganz zum Ende kannst du die Eingabe wieder einbauen

----------

dass du überhaupt etwas herausbekommst ist erschaunlich,
jede der inneren while-Schleifen kann einen Deadlock bewirken nämlich wenn die die vier Zahlen 1-4 unter den sechs Vergleichszahlen alle schon vergeben sind, dann wird ewig neue Zufallszahlen probiert, aber nichts klappt


----------



## Dude! (24. Mrz 2010)

Hm
das stimmt natürlich,

Wobei das Spiel ja so aufgebaut ist, dass nichts in der Reihe,Spalte und Kasten sein darf. Auch beim normalen Spiel klappt es nicht wenn alles Zahlen schon vergeben sind. 

Wobei an den neuen Einwand von dir habe ich noch nicht gedacht.

Ich schaus mir mal an.

Vielen DAnk


----------



## Sonecc (24. Mrz 2010)

ein beispiel für einen besseren namen wäre:

feldXY, mit X = reihe und Y = Spalte

feld11, feld12, feld13 usw.

zu der Sache mit den Klammern:

Was du da sagst ist richtig, aber so wie du es da gemacht hast, ist es dennoch unübersichtlich.


```
public class Minisudoku {

    public static void main(String[] args) {
        Scanner tastatur = new Scanner(System.in);
        Random generator = new Random();
        int x1, x2, x3, x4, y1, y2, y3, y4, z1, z2, z3, z4, q1, q2, q3, q4, e;

        System.out.println("Gebe die Zahlen ein. Leeres Feld =0");
        System.out.println("Die erste Reihe");
        x1 = tastatur.nextInt();
        x2 = tastatur.nextInt();
        x3 = tastatur.nextInt();
        x4 = tastatur.nextInt();
        System.out.println("2. Reihe");
        y1 = tastatur.nextInt();
        y2 = tastatur.nextInt();
        y3 = tastatur.nextInt();
        y4 = tastatur.nextInt();
        System.out.println("3. Reihe");
        z1 = tastatur.nextInt();
        z2 = tastatur.nextInt();
        z3 = tastatur.nextInt();
        z4 = tastatur.nextInt();
        System.out.println("4. Reihe");
        q1 = tastatur.nextInt();
        q2 = tastatur.nextInt();
        q3 = tastatur.nextInt();
        q4 = tastatur.nextInt();
        e = x1 + x2 + x3 + x4 + y1 + y2 + y3 + y4 + z1 + z2 + z3 + z4 + q1 + q2 + q3 + q4;
        while (e != 0) {
            while (x1 == 0 || x1 == x2 || x1 == x3 || x1 == x4 || x1 == y1 || x1 == z1 || x1 == q1 || x1 == y2) {
                x1 = generator.nextInt(4) + 1;
            }
            while (x2 == 0 || x2 == x1 || x2 == x3 || x2 == x4 || x2 == y2 || x2 == z2 || x2 == q2 || x2 == y1) {
                x2 = generator.nextInt(4) + 1;
            }
            while (x3 == 0 || x3 == x2 || x3 == x1 || x3 == x4 || x3 == y3 || x3 == z3 || x3 == q3 || x3 == y4) {
                x3 = generator.nextInt(4) + 1;
            }
            while (x4 == 0 || x4 == x2 || x4 == x3 || x4 == x1 || x4 == y4 || x4 == z4 || x4 == q4 || x4 == y3) {
                x4 = generator.nextInt(4) + 1;
            }

            while (y1 == 0 || y1 == y2 || y1 == y3 && y1 == y4 || y1 == x1 || y1 == z1 || y1 == q1 || y1 == x2) {
                y1 = generator.nextInt(4) + 1;
            }
            while (y2 == 0 || y2 == y1 || y2 == y3 && y2 == y4 || y2 == x2 || y2 == z2 || y2 == q2 || y2 == x1) {
                y2 = generator.nextInt(4) + 1;
            }
            while (y3 == 0 || y3 == y2 || y3 == y1 && y3 == y4 || y3 == x3 || y3 == z3 || y3 == q3 || y3 == x4) {
                y3 = generator.nextInt(4) + 1;
            }
            while (y4 == 0 || y4 == y2 || y4 == y3 && y4 == y1 || y4 == x4 || y4 == z4 || y4 == q4 || y4 == x3) {
                y4 = generator.nextInt(4) + 1;
            }

            while (z1 == 0 || z1 == z2 || z1 == z3 && z1 == z4 || z1 == y1 || z1 == x1 || z1 == q1 || z1 == q2) {
                z1 = generator.nextInt(4) + 1;
            }
            while (z2 == 0 || z2 == z1 || z2 == z3 && z2 == z4 || z2 == y2 || z2 == x2 || z2 == q2 || z2 == q1) {
                z2 = generator.nextInt(4) + 1;
            }
            while (z3 == 0 || z3 == z2 || z3 == z1 && z3 == z4 || z3 == y3 || z3 == x3 || z3 == q3 || z3 == q4) {
                z3 = generator.nextInt(4) + 1;
            }
            while (z4 == 0 || z4 == z2 || z4 == z3 && z4 == z1 || z4 == y4 || z4 == x4 || z4 == q4 || z4 == q3) {
                z4 = generator.nextInt(4) + 1;
            }

            while (q1 == 0 || q1 == q2 || q1 == q3 && q1 == q4 || q1 == y1 || q1 == z1 || q1 == x1 || q1 == z2) {
                q1 = generator.nextInt(4) + 1;
            }
            while (q2 == 0 || q2 == q1 || q2 == q3 && q2 == q4 || q2 == y2 || q2 == z2 || q2 == x2 || q2 == z1) {
                q2 = generator.nextInt(4) + 1;
            }
            while (q3 == 0 || q3 == q2 || q3 == q1 && q3 == q4 || q3 == y3 || q3 == z3 || q3 == x3 || q1 == z4) {
                q3 = generator.nextInt(4) + 1;
            }
            while (q4 == 0 || q4 == q2 || q4 == q3 && q4 == q1 || q4 == y4 || q4 == z4 || q4 == x4 || q1 == z3) {
                q4 = generator.nextInt(4) + 1;
            }
            e = x1 + x2 + x3 + x4 + y1 + y2 + y3 + y4 + z1 + z2 + z3 + z4 + q1 + q2 + q3 + q4;
        }
        System.out.println(x1 + " " + x2 + " " + x3 + " " + x4);
        System.out.println(y1 + " " + y2 + " " + y3 + " " + y4);
        System.out.println(z1 + " " + z2 + " " + z3 + " " + z4);
        System.out.println(q1 + " " + q2 + " " + q3 + " " + q4);
    }
}
```

Dieser Code ist deutlich übersichtlicher und einfacher zu lesen und das einfach nur deshalb, weil die Klammern dennoch genutzt werden.
Wenn man sie nun unbedingt nicht möchte (was übrigens auch noch fehleranfällig ist), dann bitte wenigstens einrücken, so dass es so aussieht:


```
while (x1 == 0 || x1 == x2 || x1 == x3 || x1 == x4 || x1 == y1 || x1 == z1 || x1 == q1 || x1 == y2) 
                x1 = generator.nextInt(4) + 1;
```

zu deinem neuen problem:


```
while (y1==0 || y1==y2 || y1==y3 && y1==y4 || y1==x1 || y1==z1 || y1==q1 || y1==x2)y1=generator.nextInt(4)+1;
        while (y2==0 || y2==y1 || y2==y3 && y2==y4 || y2==x2 || y2==z2 || y2==q2 || y2==x1)y2=generator.nextInt(4)+1;
        while (y3==0 || y3==y2 || y3==y1 && y3==y4 || y3==x3 || y3==z3 || y3==q3 || y3==x4)y3=generator.nextInt(4)+1;
        while (y4==0 || y4==y2 || y4==y3 && y4==y1 || y4==x4 || y4==z4 || y4==q4 || y4==x3)y4=generator.nextInt(4)+1;
        
        while (z1==0 || z1==z2 || z1==z3 && z1==z4 || z1==y1 || z1==x1 || z1==q1 || z1==q2)z1=generator.nextInt(4)+1;
        while (z2==0 || z2==z1 || z2==z3 && z2==z4 || z2==y2 || z2==x2 || z2==q2 || z2==q1)z2=generator.nextInt(4)+1;
        while (z3==0 || z3==z2 || z3==z1 && z3==z4 || z3==y3 || z3==x3 || z3==q3 || z3==q4)z3=generator.nextInt(4)+1;
        while (z4==0 || z4==z2 || z4==z3 && z4==z1 || z4==y4 || z4==x4 || z4==q4 || z4==q3)z4=generator.nextInt(4)+1;
        
        while (q1==0 || q1==q2 || q1==q3 && q1==q4 || q1==y1 || q1==z1 || q1==x1 || q1==z2)q1=generator.nextInt(4)+1;
        while (q2==0 || q2==q1 || q2==q3 && q2==q4 || q2==y2 || q2==z2 || q2==x2 || q2==z1)q2=generator.nextInt(4)+1;
        while (q3==0 || q3==q2 || q3==q1 && q3==q4 || q3==y3 || q3==z3 || q3==x3 || q1==z4)q3=generator.nextInt(4)+1;
        while (q4==0 || q4==q2 || q4==q3 && q4==q1 || q4==y4 || q4==z4 || q4==x4 || q1==z3)q4=generator.nextInt(4)+1;
```

Hier ist jeweils ein && drin, in den ersten 4 while schleifen sind diese nicht drin.
Eventuell liegt der Fehler hier


----------



## 0x7F800000 (25. Mrz 2010)

Deswegen sollte man schülern niemals irgendwelche Aufgaben geben, die theoretisch per hand lösbar sind...  

Tu dir selbst und der Welt einen gefallen, und reduziere das Problem auf ein allgemeines NxN-Sudoku: spart dir sicherlich eine Menge Ärger.


----------



## Sonecc (25. Mrz 2010)

0x7F800000 hat gesagt.:


> Deswegen sollte man schülern niemals irgendwelche Aufgaben geben, die theoretisch per hand lösbar sind...
> 
> Tu dir selbst und der Welt einen gefallen, und reduziere das Problem auf ein allgemeines NxN-Sudoku: spart dir sicherlich eine Menge Ärger.



Ob er schon soweit ist, dass er backtracking verwenden könnte?
ich bezweifle es und sonst, fällt mir grad keine sinnvolle möglichkeit ein, wie man das lösen will:rtfm:


----------



## faetzminator (25. Mrz 2010)

Sonecc hat gesagt.:


> Ob er schon soweit ist, dass er backtracking verwenden könnte?
> ich bezweifle es und sonst, fällt mir grad keine sinnvolle möglichkeit ein, wie man das lösen will:rtfm:



Die meisten Sudokus sind ohne Raten lösbar. Da man immer wieder Zahlen einfügt, eröffnen sich neue Situationen, in welchen genau eine Zahl passt. Backtracking / "Raten" kann man immer noch nachträglich einbauen, für den Fall, dass keine Lösung gefunden werden kann.

Ich habe es (generisch, für ein 9x9 Sudoku) etwa so programmiert (aus Langeweile  ):

Eine Zahl muss an diesem Platz sein
weil sie in einer Spalte/Reihe sein muss, in welcher in diesem Feld nur noch ein Platz frei ist

Alle Zahlen - ausser eine - können nicht an diesem Platz sein
weil sie bereits in der Spalte, Zeile oder dem Feld bereits vorkommen


Kann sein, dass ich eine Regel vergessen habe, aber mit diesen 2 Bedingungen mit jeweils ein paar Überprüfungen lässt sich ein Sudoku ganz gut lösen. Ich habe dazu analysiert, wie ich im Kopf ein Sudoku löse.


----------



## Sonecc (25. Mrz 2010)

ich bezweifle aber, dass dies für NxN Sudokus so umsetzbar ist.
Für Sodukos fester Größe, kann man natürlich so arbeiten, wie du es machst

Dennoch glaube ich (und lasse mich gern vom gegenteil überzeugen), dass es utopisch schwer ist, ein NxN Sudoku ohne Backtracking zu lösen


----------



## faetzminator (25. Mrz 2010)

Natürlich muss die Regel jeweils angepasst werden. Aber Grundsätzlich sollte ein Feld des Sudokus immer die gleiche Anzahl Zahlen wie auch jede Reihe und Spalte beinhalten, ansonsten Frage ich mich über gewisse Regeln. Ein 15x15 Sudoku mit 3x3 Feldern würde für mich keinen Sinn machen, da dann in einem Feld nicht alle der 15 Zahlen/Zeichen abgedeckt werden müssen, 5x5 Felder gehen grundsätzlich nur, wenn dort dann wieder eine Zahl / ein Zeichen mehrfach vorkommen darf. Ich will damit sagen, dass ich Sudokus nur in den Grössen 4x4, 9x9, 16x16 (HexSudoku  ), 25x25 ... machen würde. Oder seh ich das falsch?


----------



## Sonecc (25. Mrz 2010)

Eine gültige Folge an N ist folgende:

{NxN | N = x^2 , x element aus den Natürlichen Zahlen}

Deine Überlegung ist also richtig.

Ein gültiges Sudoku Feld hat nunmal diese größen

4x4 (2^2), 9x9 (3^3), 16x16 (4^4) usw.

Dennoch ändert das nichts an meiner Befürchtung, dass es nicht praktikabel umsetzbar ist, deine Methode für NxN Sudokus zu schreiben.
Das heißt nicht, dass es für ein Soduko nicht umsetzbar ist, sondern dass ich nicht vorher angeben kann, welche Größe mein Sudoku haben wird.
Ich muss aber auch zugeben, dass ich zur Zeit auch nicht vollständig nachvollziehe wie du das für ein 9x9 sudoku umgesetzt hast (kannst mir ja mal ne PN schicken mit dem Code)


----------



## faetzminator (25. Mrz 2010)

Wenn ich nur wüsste, wo der Code ist. Werde ihn irgendwann suchen, wenn ich nicht gerade im Stress bin... Wie gesagt, der Code wurde natürlich *nicht* für eine fixe Grösse geschrieben. Aber wenn ich das Sudoku in den Stdin werfe, sollte ich wissen, wie gross es ist


----------



## Sonecc (25. Mrz 2010)

ich warte gespannt


----------



## 0x7F800000 (25. Mrz 2010)

Sonecc hat gesagt.:


> Ob er schon soweit ist, dass er backtracking verwenden könnte?


Wozu soll man dem sonst solche Aufgaben stellen? Damit er sich in hyperexponentieller Zeit eine Lösung zusammenwürfelt? :autsch:

Das wäre ja sogar noch einigermaßen akzeptabel, wenn der code nicht so furthbar hässlich wäre^^ Was is'n das überhaupt? Mit gutem Code ist es wie mit Beweisen: Guter Code liest sich wie ein Gedicht, dieser hier liest sich wie ein Telefonbuch...


----------



## Sonecc (25. Mrz 2010)

wofür man das macht sei mal dahingestellt, aber dem code nach zu urteilen ist sowas wie rekursivität noch nicht dran gewesen 
Edit: Netter vergleich:lol:


----------



## 0x7F800000 (25. Mrz 2010)

Sonecc hat gesagt.:


> wofür man das macht sei mal dahingestellt, aber dem code nach zu urteilen ist sowas wie rekursivität noch nicht dran gewesen


Variante A: Prof hat Rekursionen vergessen und dazu eine Hausaufgabe gestellt.
Variante B: Student hat gepennt.

Hmmm... Ne, also, B? Das kann doch gar nicht sein^^ :autsch:


----------



## Sonecc (25. Mrz 2010)

hmm...
Aber mal ganz doof gefragt...
Wenn die Aufgabe wirklich Rekursion als Übungsziel hat, wieso dann nur 4x4?
Ich habs wenigstens direkt in 9x9 gelernt


----------



## Dude! (28. Mrz 2010)

Vielen Dank für eure Hilfe.


----------

