Hi, ich habe folgende Klasse zum erstellen von 9*9 Sudoku Feldern geschrieben:
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:
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!
Code:
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
6 9 4 8 3 2 7 5 1
2 6 9 4 5 1 8 7 3
1 5 3 9 8 7 6 2 4
4 8 7 2 6 3 5 1 9
5 7 1 3 2 9 4 8 6
8 3 2 5 4 6 1 9 7
9 4 6 1 7 8 2 3 5
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!