[Ben]

Mach das mal. Durchaus interessant ;)

[The_S]

OK, der Code ist wie gesagt etwas älter. Hab auch gerade festgestellt, dass er nur teilweise kommentiert ist. Hab jetzt mal die nötigsten Kommentare und eine Beispiel-Main-Methode hinzugefügt, bei Fragen einfach die Hand heben (könnte man sicher noch optimieren, z. B. keinen Vector bei getPoss verwenden ... aber so funktioniert er ja erstmal!).

import java.util.Arrays;
import java.util.Vector;

public class SudoGenerator {
    
    private static int[][] cur = null; // die Matrix komplett ausgefüllt
    
    /**
     * Berechnet alle möglichen Zahlen für eine bestimmte Position in einem vorgegebenen, teilweise
     * ausgefüllten Sudoku-Feld
     * 
     * @param y - Y-Position in der Matrix
     * @param x - X-Position in der Matrix
     * @param mat - die Matrix
     * 
     * @return Ein Array mit allen Möglichen Zahlen zur angegebenen Position
     */
    public static int[] getPoss(int y, int x, int[][] mat) {
        
        Vector<Integer> poss = new Vector<Integer>();
        int quadStartX = (int)(x / 3) * 3; // Startfeld auf der X-Achse des Quadrats, in dem sich die übergebene Position befindet
        int quadStartY = (int)(y / 3) * 3; // Startfeld auf der Y-Achse des Quadrats, in dem sich die übergebene Position befindet
        for (int i = 1; i < 10; i++) { // Der Vector mit allen Zahlen befüllen
            poss.add(i);
        }
        for (int i = 0; i < mat.length; i++) { // Zeilen und Spalten auf bereits angelegte Zahlen überprüfen
            if (i != y && mat[i][x] != 0) {
                if (poss.contains(mat[i][x]) || poss.contains(mat[i][x] - 10)) {
                    poss.removeElement(mat[i][x]);
                    poss.removeElement(mat[i][x] - 10);
                }
            }
            if (i != x && mat[y][i] != 0) {
                if (poss.contains(mat[y][i]) || poss.contains(mat[y][i] - 10)) {
                    poss.removeElement(mat[y][i]);
                    poss.removeElement(mat[y][i] - 10);
                }
            }
        }
        for (int i = 0; i < 3; i++) { // Quadrat wird auf bereits angelegte Zahlen überprüft
            for (int j = 0; j < 3; j++) {
                if (i + quadStartY != y && j + quadStartX != x && mat[i + quadStartY][j + quadStartX] != 0) {
                    poss.removeElement(mat[i + quadStartY][j + quadStartX]);
                    poss.removeElement(mat[i + quadStartY][j + quadStartX] - 10);
                }
            }
        }
        int[] val = new int[poss.size()];
        for (int i = 0; i < val.length; i++) { // Von Vector in Array
            val[i] = poss.get(i);
        }
        return val;
    }
    
    /**
     * Leert das Sudoku-Feld
     */
    public static void blankSudo() {
        
        cur = new int[9][9];
    }
    
    /**
     * Generiert eine Sudoku-Matrix (vollständig ausgefüllt)
     */
    public static boolean generateSudo() {
        
        cur = new int[9][9];
        return generate(0, 0);
    }
    
    /**
     * Überprüft, ob die aktuelle Matrix gültig ist
     */
    public static boolean check() {
        
        for (int y = 0; y < cur.length; y++) {
            for (int x = 0; x < cur[y].length; x++) {
                if (cur[y][x] > 0) {
                    if (Arrays.binarySearch(getPoss(y, x, cur), cur[y][x]) < 0) {
                        return false;
                    }
                }
            }
        }
        return true;
    }
    
    /**
     * Löst ein Sudoku-Feld
     */
    public static boolean solveSudo() {
        
        if (!check()) {
            return false;
        }
        for (int y = 0; y < cur.length; y++) {
            for (int x = 0; x < cur[y].length; x++) {
                if (cur[y][x] > 0) {
                    cur[y][x] += 10;
                }
            }
        }
        boolean val = generate(0, 0);
        for (int i = 0; i < cur.length; i++) {
            for (int j = 0; j < cur[i].length; j++) {
                if (cur[i][j] > 9) {
                    cur[i][j] -= 10;
                }
            }
        }
        return val;
    }
    
    /**
     * Erstellt rekursiv ein Sudokufeld mit 9x9 Feldern. Dabei werden zufällig den Regeln von Sudoku entsprechende
     * Zahlen ausgewählt und nacheinander in die jeweiligen Felder eingefügt. Anschließend geschied selbiges für
     * das nächste Feld. Gibt es keine möglichen Zahlen mehr für ein Feld, so wird versucht für das vorhergehende Feld
     * eine andere Zahl zu ermitteln.
     * 
     * @param y - zu bearbeitendes Feld auf der Y-Achse
     * @param x - zu bearbeitendes Feld auf der X-Achse
     * 
     * @return true falls eine mögliche Belegung gefunden wurde, ansonsten false
     */
    public static boolean generate(int y, int x) {
        
        if (y >= cur.length) { // Spielfeld wurde erfolgreich erstellt, wenn das Ende erreicht ist
            return true;
        }
        int[] poss = getPoss(y, x, cur); // Mögliche Zahlen für dieses Feld ermitteln
        int nextX = x + 1; // nächstes Feld auf der X-Achse festlegen
        int nextY = y; // nächstes Feld auf der Y-Achse festlegen
        if (nextX >= cur[y].length) { // falls nächstes Feld auf der X-Achse nicht existiert ...
            nextX = 0;  // ... nächstes Feld auf der X-Achse = 0
            nextY++; // ... nächstes Feld auf der Y-Achse + 1
        }
        if (poss.length == 0) { // Wenn es für dieses Feld keine möglichen Zahlen gibt ...
            if (cur[y][x] < 10) {
                cur[y][x] = 0; // ... setze das aktuelle Feld wieder auf 0
            }
            return false; // ... geb der aufrufenden Methode bescheid
        }
        else if (cur[y][x] == 0 ) {
            cur[y][x] = poss[(int)(Math.random() * poss.length)]; // Wähle eine zufällige Zahl aus den möglichen Zahlen für dieses Feld
        }
        
        while (!generate(nextY, nextX)) { // solange das generieren des nächsten Feldes fehlschlägt
            if (cur[y][x] > 9) {
                return false;
            }
            poss = remove(cur[y][x], poss); // ausgewählte Ziffer löschen, da nachfolgende Methode bei dieser Ziffer keine Zahl setzen kann
            if (poss.length == 0) { // überprüfen ob noch weitere mögliche Zahlen vorhanden sind
                cur[y][x] = 0;
                return false;
            }
            else {
                cur[y][x] = poss[(int)(Math.random() * poss.length)]; // neue Zahl zuweisen
            }
        }
        return true;
    }
    
    /**
     * Entfernt eine bestimmte Zahl aus einem int-Array.
     * 
     * @param ziffer - die zu entfernende Zahl
     * @param kette - das Integer-Array aus dem die Ziffer entfernt werden soll 
     * 
     * @return das übergebene int-Array ohne die übergebene Ziffer
     */
    private static 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;
    }
    
    /**
     * @return gibt das erstellte Sudoku-Feld zurück
     * 
     * @see generateSudo()
     * @see createSpielfeld(int showFields)
     */
    public static int[][] getMatrix() {
        return cur;
    }
    
    /**
     * Setzt ein Sudoku-Feld
     */
    public static void setMatrix(int[][] matrix) {
        cur = matrix;
    }
    
    /**
     * Erstellt ein Spielfeld aus der vorher generierten Matrix. Dabei werden zufällige Felder ausgewählt,
     * die schon im Voraus angezeigt werden. Dadurch können für ein und die selbe Matrix mehrere, unterschiedliche
     * Spielfelder erstellt werden. Die Anzahl der vorbelegten Felder richtet sich nach dem übergebenen Parameter.
     * 
     * @param showFields - Anzahl der Felder die ausgefüllt werden sollen
     * 
     * @return gibt ein zweidimensonales Spielfeld der zuvor erstellten Matrix zurück
     * 
     * @see getMatrix()
     * @see generateSudo()
     */
    public static int[][] createSpielfeld(int showFields) {
        
        if (cur == null) { // Wenn noch keine Matrix angelegt wurde eine anlegen
            generateSudo();
        }
        else if (showFields < 0) { // Stellt sicher, dass die Anzahl der vorgeblendten Fenster positiv ist
            showFields *= -1;
        }
        int[][] field = new int[cur.length][cur[0].length]; // Array in welchem das Spielfeld gespeichert wird
        for (int i = 0; i < field.length; i++) { // Verschachtelte Schleife um die bisherige Matrix zu klonen
            for (int j = 0; j < field[i].length; j++) {
                field[i][j] = cur[i][j];
            }
        }
        int clear = field.length * field[0].length - showFields - 1; // So viele Felder werden nicht vorgeblendet
        if (clear > 80) { // Falls mehr Felder nicht vorgeblendet werden sollen, als es überhaupt gibt wird die max. Zahl an Feldern vorgeblendet
            clear = 80;
        }
        int rand1 = 0;
        int rand2 = 0;
        for (int i = clear; i > -1; i--) { // Solange, wie noch zuviele Felder vorgeblendet werden
            rand1 = (int)(Math.random() * field.length); // Zufälliges Feld auf der Y-Achse auswählen
            rand2 = (int)(Math.random() * field[0].length); // Zufälliges Feld auf der X-Achse auswählen
            if (field[rand1][rand2] == 0) { // Ist das Feld schon als nicht vorgeblendet markiert => Schritt zurück gehen
                i++;
            }
            else { // Ansonsten Feld als nicht vorgeblendet markieren
                field[rand1][rand2] = 0;
            }
        }
        return field;
    }
    
    public static void main(String[] args) {
        
        int[][] mat = createSpielfeld((int)(Math.random() * 40 + 22));
        for (int i = 0; i < mat.length; i++) {
            for (int j = 0; j < mat[i].length; j++) {
                System.out.print(mat[i][j] + " ");
            }
            System.out.println();
        }
        setMatrix(mat);
        System.out.println("\n-----------------\n");
        solveSudo();
        for (int i = 0; i < mat.length; i++) {
            for (int j = 0; j < mat[i].length; j++) {
                System.out.print(mat[i][j] + " ");
            }
            System.out.println();
        }
    }
}

[$traight-$hoota]

was bringt denn poss.removeElement(mat[i][x] - 10);??

[The_S]

Wenn ein Sudoku nicht neu erstellt, sondern gelöst werden soll, so werden alle bereits eingetragenen Zahlen + 10 genommen, damit ich beim Backtracing feststellen kann, ob es sich um eine vorgeblendete und somit nicht veränderbare, oder um eine "normale" Zahl, die ich verändern darf, handelt. Und auf diese Zahlen muss natürlich auch geprüft werden.