# Sudoku Algorithmus



## The_S (11. Okt 2006)

Hi, ich habe folgende Klasse zum erstellen von 9*9 Sudoku Feldern geschrieben:


```
import java.util.*;

public class Sudo {
	
	private int[][] cur = null;
	
	public void generateSudo() {
		
		cur = new int[9][9];
		generate(0, 0);
	}
	
	private boolean generate(int y, int x) {
		
		if (y >= cur.length) {
			return true;
		}
		int[] poss = getPoss(y, x);
		int nextX = x + 1;
		int nextY = y;
		if (nextX >= cur[y].length) {
			nextX = 0;
			nextY++;
		}
		if (poss.length == 0) {
			cur[y][x] = 0;
			return false;
		}
		cur[y][x] = poss[(int)(Math.random() * poss.length)];
		while (!generate(nextY, nextX)) {
			poss = remove(cur[y][x], poss);
			if (poss.length == 0) {
				cur[y][x] = 0;
				return false;
			}
			else {
				cur[y][x] = poss[(int)(Math.random() * poss.length)];
			}
		}
		return true;
	}
	
	private int[] remove(int ziffer, int[] kette) {
		
		int[] array = new int[kette.length - 1];
		for (int i = 0, j = 0; i < kette.length; i++, j++) {
			if (kette[i] != ziffer) {
				array[j] = kette[i];
			}
			else {
				j--;
			}
		}
		return array;
	}
	
	private int[] getPoss(int y, int x) {
		
		Vector<Integer> poss = new Vector<Integer>();
		int quadStartX = (int)(x / 3) * 3;
		int quadStartY = (int)(y / 3) * 3;
		for (int i = 1; i < 10; i++) {
			poss.add(i);
		}
		for (int i = 0; i < cur.length; i++) {
			if (i != y && cur[i][x] != 0) {
				if (poss.contains(cur[i][x])) {
					poss.removeElement(cur[i][x]);
				}
			}
			if (i != x && cur[y][i] != 0) {
				if (poss.contains(cur[y][i])) {
					poss.removeElement(cur[y][i]);
				}
			}
		}
		for (int i = 0; i < 3; i++) {
			for (int j = 0; j < 3; j++) {
				if (i + quadStartY != y && j + quadStartX != x && cur[i + quadStartY][j + quadStartX] != 0) {
					poss.removeElement(cur[i + quadStartY][j + quadStartX]);
				}
			}
		}
		int[] val = new int[poss.size()];
		for (int i = 0; i < val.length; i++) {
			val[i] = poss.elementAt(i);
		}
		return val;
	}
	
	public int[][] getMatrix() {
		return cur;
	}
	
	public int[][] createSpielfeld(int showFields) {
		
		if (cur == null || showFields <= 0) {
			return null;
		}
		int[][] field = cur;
		int clear = field.length * field[0].length - showFields - 1;
		int rand1 = 0;
		int rand2 = 0;
		for (int i = clear; i > -1; i--) {
			rand1 = (int)(Math.random() * field.length);
			rand2 = (int)(Math.random() * field[0].length);
			if (field[rand1][rand2] == 0) {
				i++;
			}
			else {
				field[rand1][rand2] = 0;
			}
		}
		return field;
	}
}
```

Funktioniert soweit auch ganz gut. Allerdings ist mir eine Sache aufgefallen (ist ein bisschen schwer zu erklären, aber ich versuch mal):

Pro Quadrat-Reihe sind in allen drei Quadraten immer 2 Zahlen in der selben Reihe (Anordnung unterschiedlich). ein Beispiel:



> 7 1 8 6 9 5 3 4 2
> 
> 3 2 5 7 1 4 9 6 8
> 
> ...



Wie man erkennen kann tauchen in der 1. Quadrat-Reihe pro Quadrat immer die Zahlen 7 und 1,  3 und 2,  9 und 6 auf (wenn auch in Unterschiedlicher Anordnung). Das Schema läss sich in jeder Quadrat-Zeile verfolgen. 

Kommen wir zu meinen Fragen:

1. Ich hatte zuerst einen anderen Algorithmus, der mithilfe von Versetzung erstmal sehr einfache Sudoku generiert und anschließend einzelne Spalten und Ziffern innerhalb eines Quadrats vertauscht, so dass immernoch alle Regeln beachtet wurden. Dort konnte ich das oben beschriebene Verhalten auch beobachten und Schloss aber mal darauf, dass es daran liegt, dass mein 1. Algorithmus ja nicht wirklich zufällig ist. Weshalb ich auch diesen 2., imho vollständig zufälligen, Algorithmus geschrieben habe. Aber da ich dort ebenfalls diese Muster feststellen kann, würde ich gerne wissen ob das evtl. ein typisches (unausweichliches) Muster bei Sudokus ist (ich selbst kann dazu nicht viel sagen, da ich in meinem ganzen Leben noch kein Sudoku gelöst habe => Interessiert mich einfach nicht, aber eine Freundin wollte so einen kleinen Sudoku-Generator)!?

2. Kritik/Wünsche/Anregungen/Verbesserungen? 

Danke!


----------



## The_S (13. Okt 2006)

*push* ... wollt ich einfach mal so in den Raum geworfen haben


----------



## Gast (16. Okt 2006)

ich spiel auch kein sudoku


----------



## Redfrettchen (16. Okt 2006)

Hi,
random-Anmerkungen:

```
(int)(x/3)*3 -> (x - (x % 3))
```
-ArrayList statt Vector

Haupt-Anmerkung:
Vielleicht musst du auch noch die Durchlaufreihenfolge randomisieren, also nicht (0,0)->(1,0)->...->(8,0)->(0,1)->..., sondern in zufälliger Reihenfolge, die du am Anfang festlegst. Aber komisch ist es schon...


----------



## The_S (16. Okt 2006)

joa, könnt auch ne ArrayList nehmen, aber um die performance geht es erstmal nicht. Hab festgestellt, dass selbiges Muster auch bei Spalten auftritt. Und bei allen Freeware-Sudokus im Netzt konnte ich das selbe Muster beobachten   .

Aber danke schonmal


----------



## The_S (20. Okt 2006)

Irgendwie scheint mir das ein Standardverhalten von Sudokus zu sein (also dieses Muster vertikal UND horizontal). Deswegen möchte ich meine Frage mal umformolieren:

Kann mir jemand ein Sudoku posten (inkl. Lösung oder auch nur die Lösung), bei welchem dieses Muster nicht auftritt? Danke!


----------



## Wooky (24. Nov 2006)

Hi, ja das kann ich.

hier ist eins:
 |-------+-------+-------|   |-------+-------+-------|   |-------+-------+-------|
 | 0 7 0 | 4 0 0 | 3 0 0 |   | 8 7 5 | 4 9 1 | 3 6 2 |   | 8 7 5 | 4 9 1 | 3 6 2 |
 | 0 0 0 | 2 0 0 | 0 5 0 |   | 3 1 9 | 2 8 6 | 7 5 4 |   | 3 1 9 | 2 8 6 | 7 5 4 |
 | 2 6 0 | 5 0 0 | 0 0 8 |   | 2 6 4 | 5 7 3 | 9 1 8 |   | 2 6 4 | 5 7 3 | 9 1 8 |
 |-------+-------+-------|   |-------+-------+-------|   |-------+-------+-------|
 | 9 0 0 | 0 5 4 | 0 0 0 |   | 9 2 6 | 7 5 4 | 1 8 3 |   | 9 2 6 | 7 5 4 | 1 8 3 |
 | 0 0 0 | 0 0 2 | 6 4 0 |   | 7 8 3 | 9 1 2 | 6 4 5 |   | 7 8 3 | 9 1 2 | 6 4 5 |
 | 4 0 1 | 0 0 0 | 2 0 0 |   | 4 5 1 | 6 3 8 | 2 7 9 |   | 4 5 1 | 6 3 8 | 2 7 9 |
 |-------+-------+-------|   |-------+-------+-------|   |-------+-------+-------|
 | 0 9 0 | 0 0 7 | 0 0 0 |   | 5 9 2 | 1 4 7 | 8 3 6 |   | 5 9 2 | 1 4 7 | 8 3 6 |
 | 0 0 8 | 0 6 0 | 0 0 0 |   | 1 4 8 | 3 6 9 | 5 2 7 |   | 1 4 8 | 3 6 9 | 5 2 7 |
 | 0 0 7 | 8 0 0 | 4 0 1 |   | 6 3 7 | 8 2 5 | 4 9 1 |   | 6 3 7 | 8 2 5 | 4 9 1 |
 |-------+-------+-------|   |-------+-------+-------|   |-------+-------+-------|

Ich hoffe das hilft dir.

Gruß
Wooky

PS: das hat mein Testgenerator ausgeworfen, den ich mal geschrieben hatte.
Kannst du auch selbst aufrufen unter: http://home.arcor.de/wooky123/sudoku.html
Auf der Konsole bekommst du im Log dann auch diese Lösung!


----------



## The_S (24. Nov 2006)

Da tritt das Muster aber auch auf ... :roll:

trotzdem danke


----------



## Wooky (24. Nov 2006)

Wo denn? 
Das zwei Zahl in der selben Reihenfolge vorkommen können, ist ja normal und läst sich nicht verhindern. Es hat jedenfalls kein System wie bei Deiner Lösung.
Gruß
Wooky


----------



## SlaterB (24. Nov 2006)

betrachen wir mal nur die oberen drei Quadrate,
-> drei Zeilen 


```
123  |  ----- | -----
-----| ? ? ?  | y y y
-----| ? ? ?  | y y y
```

die Zahlen 1, 2 und 3 müssen auch im mittleren Qudrat vorkommen,
es stehen nur noch Zeile 2 oder 3 zur Auswahl,
nach Adam Riesling muss dann mindestens in einer der beiden Zeilen zwei Zahlen stehen,
allgemein gesehen also


```
123  |  ----- | -----
-----| 1 2 ?  | y y y
-----| 3 ? ?  | y y y
```

was bedeutet das für das letzte Quadrat?
1 und 2 müssen unbedingt in die unterste Zeile

->


```
123  |  ----- | -----
-----| 1 2 ?  | 3 y y
-----| 3 ? ?  | 1 2 y
```


genauso gilt das für alle anderen Zeilen und Spalten,
daher mathematisch gesehen unmöglich zu vermeiden


----------



## The_S (25. Nov 2006)

Hm, hät ich eigneltich auch selber drauf kömmen können ... danke @SlaterB

@Gast, wo siehst du einen Unterschied zu meinem?


----------



## xysawq (6. Aug 2008)

SlaterB hat gesagt.:
			
		

> nach Adam Riesling muss dann mindestens in einer der beiden Zeilen zwei Zahlen stehen



Jetzt hab ichs erst gemerkt ^^ ... Adam Ries(ling) ... net schlecht


----------



## The_S (8. Aug 2008)

2 Jahre hast dafür gebraucht?


----------

