Sudoku Rekursion

mymaksimus · 5. Mai 2015 um 10:01

hach ja, schon wieder ne anfänger frage…

Also, habe mal versucht einen algorithmus zu schreiben, der mithilfe von backtracking
sudoku löst. (klausurthema, deshalb muss ich mich damit etwas auseinandersetzen)

Jedenfalls, es funktioniert eigentlich soweit alles, hier der code:
(der eigentliche algo ist solveSudoku, ab z 20)


import java.io.File;
import java.io.PrintStream;
import java.util.Arrays;

public class SudokuSolver {
	
	private static final int SUDOKU_SIZE = 9;
	
	public static int[][] solveSudoku(int sudoku[][]){
		for(int i = 0; i < SUDOKU_SIZE; i++){
			if(!testSudokuAndLog(sudoku, i, i)) throw new IllegalArgumentException("Sodukou isn't correct.");
		}
		return solveSudoku(sudoku, 0, 0, 1);
	}
	
	
	private static boolean ready;
	public static int[][] solveSudoku(int sudoku[][], int currentRow, int currentCol, int currentNumber){
		int nextCol = currentCol + 1;
		int nextRow = currentRow;
		if(nextCol > SUDOKU_SIZE - 1){
			nextCol = 0;
			nextRow++;
		}
		if(nextRow > SUDOKU_SIZE - 1){
			ready = true;
			return sudoku;
		}
		if(sudoku[currentRow][currentCol] > 0){
			return solveSudoku(sudoku, nextRow, nextCol, 1);
		}
		else {
			for(int i = 1; i <= SUDOKU_SIZE; i++){
				sudoku[currentRow][currentCol] = i;
				outSudoku(sudoku);
				if(testSudoku(sudoku, currentRow, currentCol)){
					sudoku = solveSudoku(sudoku, nextRow, nextCol, 1);
					if(ready){
						return sudoku;
					}
				}
				else {
					sudoku[currentRow][currentCol] = 0;
				}
			}
		}
		return sudoku;
	}
	
	public static void outSudoku(int sudoku[][]){
		System.out.println("[out sudoku]");
		for(int row[] : sudoku){
			System.out.println(Arrays.toString(row));
		}
		System.out.println();
	}
	
	public static boolean testSudoku(int sudoku[][], int currentRow, int currentCol){
		int ninthRow = currentRow / 3;
		int ninthCol = currentCol / 3;
		int numberArrayRow[] = createTestArray();
		int numberArrayCol[] = createTestArray();
		int numberArrayNinth[] = createTestArray();
		for(int i = 0; i < SUDOKU_SIZE; i++){
			int rowValue = sudoku[currentRow]**;
			int colValue = sudoku**[currentCol];
			int ninthValue = sudoku[ninthRow * 3 + i / 3][ninthCol * 3 + i % 3];
			if(rowValue > 0 && !extendAndTestNumberArray(numberArrayRow, rowValue)){
				return false;
			}
			if(colValue > 0 && !extendAndTestNumberArray(numberArrayCol, colValue)){
				return false;
			}
			if(ninthValue > 0 && !extendAndTestNumberArray(numberArrayNinth, ninthValue)){
				return false;
			}
		}
		return true;
	}
	
	public static boolean testSudokuAndLog(int sudoku[][], int currentRow, int currentCol){
		System.out.println("checking sudoku at row(" + currentRow + ")" + " & col(" + currentCol + ")");
		boolean result = testSudoku(sudoku, currentRow, currentCol);
		System.out.println("checked => " + result);
		return result;
	}
	
	public static boolean extendAndTestNumberArray(int numberArray[], int value){
		boolean result = !(numberArray[value - 1] > 0); 
		numberArray[value - 1] = value;
		return result;
	}
	
	public static int[] createTestArray(){
		return new int[SUDOKU_SIZE];
	}
	
	public static void main(String[] args) throws Exception {
		System.setOut(new PrintStream(new File(System.getProperty("user.home") + "\\Desktop\\log")));
		int sudoku[][] = new int[][]{
				{0, 0, 0,	0, 3, 0,	0, 1, 5},	
				{0, 5, 0,	0, 1, 0,	8, 9, 4},
				{4, 0, 8,	0, 0, 5,	3, 6, 7},
				
				{0, 0, 6,	0, 0, 0,	0, 0, 8},
				{5, 9, 7,	0, 0, 0,	0, 0, 3},
				{0, 0, 0,	0, 6, 0,	1, 0, 9},
				
				{6, 0, 0,	0, 8, 0,	4, 3, 0},
				{0, 0, 2,	3, 0, 0,	0, 5, 0},
				{3, 0, 0,	0, 0, 7,	9, 0, 2}
		};
		long startTime = System.nanoTime();
		solveSudoku(sudoku);
		long endTime = System.nanoTime();
		float millis = (endTime - startTime) / 1e6f;
		System.out.println("final solution: ");
		outSudoku(sudoku);
		System.out.println("time taken: " + millis + " millis");
	}
}

mein “problem”: ich brauche diese variable “ready”, die außerhalb der methode liegt. das
macht die rekursion ja ein bisschen kaputt, weil man eben diese schwierigkeit umgeht,
das man irgendwie auf jeder ebene von allem bescheid wissen muss… oder?

Ich missbrauche diesen boolean quasi als abbruchbedingung. ready = true, wenn nextRow > sudoku_size - 1.
(ich arbeite mich von oben nach unten links nach rechts durch). Das heißt, wenn allese abgearbeitet wurde.
Sobald der Algo dann wieder bei der letzten rekursionsebene angekommen ist, wird in der for schleife
die lösung returned, damit die for schleife nicht alle weiteren zahlen durchläuft.

Das ist doch nicht wirklich schön, oder? Meine frage wäre, ob es da eine elegante lösung gäbe,
oder ob mein ganzer ansatz (zB die for schleife) schon hässlich ist.

Danke ^^

system · 5. Mai 2015 um 10:51

Könnte schon richtig sein, aber wie wär’s hiermit:

int[][] col = new int[9][9];
int[][] quadrat = new int[9][9];```

und

```public boolean solve(int x, int y) {
  if (!richtig()) {
    return false;
  }
  if (vollst()) {
    return true;
  }
  for (int i = 1; i <= 9; i++) {
    // setze i in row col quadrat ein
    if (solve((y*9+x+1) % 9, (y*9+x+1) / 9)) {
      return true;
    }
  }
  // ( setze 0 in row col quadrat ein )
  return false;
}```

Erklärung:
vollst == voll == Sudoku voll
0 == darf eingesetzt werden == ansonsten direkt solve(schritt + 1) aufrufen

Verstehst du, was ich meine, Methode etwas zu lang man sieht zu viel, besser neue Methode schreiben. ;)

Wie durchlaufen wird (und das mit der wichtigen Abbruchbedingung), hab ich verstanden.

grüße

Marco13 · 5. Mai 2015 um 11:38

Hab’s nicht im Detail nachvollzogen, aber … auch auf die Gefahr hin, dass meine Steinigung gleich nicht mehr Optional ist … : Könnte man nicht einfach „null“ zurückgeben, wenn es keine Lösung gab, und nicht-null, wenn doch?

system · 5. Mai 2015 um 11:55

Doch, könnte man, aber meine find’ ich besser, denn dem Aufrufer it ja das Sudoku bekannt, und man bräuchte anschließend nicht mehr auf “null” prüfen.^^

Sonnige und regnerische grüße!!!

system · 5. Mai 2015 um 12:26

Okay, meins ist vorgegriffen, vielleicht muss das gespoilert werden. Wikipedia beschreibt es doch viel besser:

Funktion FindeLoesung (Stufe, Vektor)
  1. wiederhole, solange es noch neue Teil-Lösungsschritte gibt:
     a) wähle einen neuen Teil-Lösungsschritt;
     b) falls Wahl gültig ist:
               I) erweitere Vektor um Wahl;
              II) falls Vektor vollständig ist, return true; // Lösung gefunden!
                  sonst:
                       falls (FindeLoesung(Stufe+1, Vektor)) return true; // Lösung!
                       sonst mache Wahl rückgängig; // Sackgasse (Backtracking)!
  2. Da es keinen neuen Teil-Lösungsschritt gibt: return false // Keine Lösung!

Backtracking – Wikipedia - Diese Seite wurde zuletzt am 26. Juni 2014 um 12:51 Uhr geändert.

Ich will 1. nicht,
das vereinfachen, was dort steht,
2., jemand anderes den Ruhm abkaufen.

Marco, was sagst du dazu?

grüße

cmrudolph · 5. Mai 2015 um 22:18

@CyborgBeta : es bringt nichts, wenn du anonym postest. Deine Beiträge sind so einzigartig, dass man sofort sieht, dass alle 3 Beiträge von Unregistered von dir sind…

Ich sehe das genauso wie @Marco13 , der aktuelle Zustand wird ja in der aufrufenden Methode gehalten. Der Rückgabewert ist nur dann relevant, wenn dort die Lösung gefunden wurde. Ansonsten wird der gehaltene Zustand verwendet - der Schritt zurück im Backtracking.

Andere Lösung ohne Backtracking
[spoiler]Ja, ich weiß - es geht bei der Aufgabenstellung explizit um Backtracking. Allerdings habe ich vor fast 2 Jahren “woanders” mal einen Sudokusolver entwickelt, der das Problem des Sudoku-Lösens in ein Problem der exakten Überdeckung überführt hat. Der ist äußerst effizient, gerade bei “großen” Sudokus (z. B. 16x16). “Woanders” hat auch ein anderer User einen Solver gepostet, der eine optimierte, entrekursivierte Variante des klassischen rekursiven Ansatzes ist.
Auch ikwudls alias hüte alias CyborgBeta hat einen Beitrag mit seiner Lösung (die Klasse hieß SuMist - ich hab sie in meinen alten Projekten noch gefunden) geleistet. Wie die funktioniert vermag ich jetzt auf die Schnelle nicht zu beurteilen - typischer ikwudls-Code halt.

Ich poste meine Klassen hier einfach mal - der Thread “woanders” ist verloren gegangen…

Das Interface habe ich nur gebaut, damit ich verschiedene Sudoku-Implementierungen besser vergleichen konnte.


public interface Sudoku {
    /**
     * Solve the sudoku.
     * 
     * @return {code true} if sudoku could be solved
     */
    boolean solve();

    /**
     * @return how many steps were needed to solve the sudoku.
     */
    long getSteps();
}```
```package net.byte_welt.sudoku;

import java.util.ArrayList;
import java.util.List;

//import java.util.Collections;

/**
 * User: Christian
 * Date: 20.07.13
 * Time: 13:48
 */
public class SudokuExactCover implements Sudoku {
    private final int fixed;
    private final MatrixEntry head;
    private final List<MatrixEntry> solution;
    private long steps = 0;
    private final int blockWidth;
    private final int totalWidth;
    private final int fieldCount;

    public SudokuExactCover(int[][] sudoku, int blockWidth) {
        this.blockWidth = blockWidth;
        totalWidth = blockWidth * blockWidth;
        fieldCount = totalWidth * totalWidth;

        if (sudoku.length != totalWidth)
            throw new IllegalArgumentException("sudoku must be a " + totalWidth + "x" + totalWidth + " array");
        for (int[] row : sudoku)
            if (row.length != totalWidth)
                throw new IllegalArgumentException("sudoku must be a " + totalWidth + "x" + totalWidth + " array");

        solution = new ArrayList<>(fieldCount);
        head = generateMatrix();
        extractFixed(sudoku);
        fixed = solution.size();
        countRows();
    }

    private void countRows() {
        MatrixEntry p = head.getRight();
        while (p != head) {
            p.countRows();
            p = p.getRight();
        }
    }

    /*private void sortHeads() {
        MatrixEntry p = head.getRight();
        List<MatrixHead> heads = new ArrayList<MatrixHead>(324 - fixed);
        while (p != head) {
            heads.add(new MatrixHead(p.getValue(), p));
            //p.setValue(p.countRows());
            p = p.getRight();
        }

        Collections.sort(heads);
        head.setRight(head);
        head.setLeft(head);
        for (MatrixHead matrixHead : heads) {
            head.insertBefore(matrixHead.getHead());
        }
    }*/

    private void extractFixed(int[][] sudoku) {
        MatrixEntry p = head;
        for (int i = 0; i < 3 * fieldCount; i++)
            p = p.getRight();

        for (int col = 0; col < totalWidth; col++) {
            for (int row = 0; row < totalWidth; row++) {
                p = p.getRight();
                if (sudoku[row][col] == 0) continue;

                MatrixEntry s = p.get(row, sudoku[row][col] - 1);
                s.removeEntry();
                solution.add(s);
            }
        }
    }

    private MatrixEntry generateMatrix() {
        MatrixEntry head = new MatrixEntry();
        List<MatrixEntry> headers = generateHeaders(head);

        for (int number = 0; number < totalWidth; number++) {
            for (int row = 0; row < totalWidth; row++) {
                for (int col = 0; col < totalWidth; col++) {
                    MatrixEntry h = headers.get(number * totalWidth + col);
                    MatrixEntry entryCol = new MatrixEntry(col, row, number, h);
                    h.insertAbove(entryCol);

                    h = headers.get(fieldCount + number * totalWidth + row);
                    MatrixEntry entryRow = new MatrixEntry(col, row, number, h);
                    h.insertAbove(entryRow);

                    h = headers.get(2 * fieldCount + number * totalWidth + col / blockWidth * blockWidth + row / blockWidth);
                    MatrixEntry entryBlock = new MatrixEntry(col, row, number, h);
                    h.insertAbove(entryBlock);

                    h = headers.get(3 * fieldCount + col * totalWidth + row);
                    MatrixEntry entryField = new MatrixEntry(col, row, number, h);
                    h.insertAbove(entryField);

                    entryCol.setLeft(entryField);
                    entryCol.setRight(entryRow);
                    entryRow.setLeft(entryCol);
                    entryRow.setRight(entryBlock);
                    entryBlock.setLeft(entryRow);
                    entryBlock.setRight(entryField);
                    entryField.setLeft(entryBlock);
                    entryField.setRight(entryCol);
                }
            }
        }
        return head;
    }

    private List<MatrixEntry> generateHeaders(MatrixEntry head) {
        List<MatrixEntry> headers = new ArrayList<>(4 * fieldCount);
        for (int i = 0; i < 4 * fieldCount; i++) {
            MatrixEntry entry = new MatrixEntry();
            head.insertBefore(entry);
            headers.add(entry);
        }
        return headers;
    }

    @Override
    public boolean solve() {
        steps = 0;

        eleminateOnes();

        MatrixEntry p = head.getRight();
        while (head.getRight() != head) {
            p = p.getLower();
            steps++;
            if (p.getCol() != -1) {
                solution.add(p);
                if (p.removeEntry()) {
                    p = head.getRight();
                } else {
                    p = backtrack();
                }
            } else {
                if (solution.size() == fixed) return false;
                p = backtrack();
            }
        }

        return head.getRight() == head;
    }

    private void eleminateOnes() {
        MatrixEntry p = head.getRight();
        while (p != head) {
            steps++;
            if (p.getRowCount() == 1) {
                p = p.getLower();
                solution.add(p);
                p.removeEntry();
                p = head.getRight();
            } else {
                p = p.getRight();
            }
        }
    }

    private MatrixEntry backtrack() {
        MatrixEntry entry = solution.remove(solution.size() - 1);
        entry.reinsert();

        return entry;
    }

    @Override
    public long getSteps() {
        return steps;
    }

    @Override
    public String toString() {
        int[][] field = new int[totalWidth][totalWidth];
        for (MatrixEntry entry : solution) {
            field[entry.getRow()][entry.getCol()] = entry.getValue() + 1;
        }
        String result = "";
        for (int row = 0; row < totalWidth; row++) {
            for (int col = 0; col < totalWidth; col++) {
                if (col > 0) result += " ";
                if (totalWidth > 9 && field[row][col] <= 9) result += " ";
                result += field[row][col];
                if ((col + 1) % blockWidth == 0 && col + 1 < totalWidth) result += " |";
            }
            result += "
";
            if ((row + 1) % blockWidth == 0 && row + 1 < totalWidth) {
                for (int col = 0; col < totalWidth; col++) {
                    if (col > 0) result += "-";
                    if (totalWidth > 9) result += "-";
                    result += "-";
                    if ((col + 1) % blockWidth == 0 && col + 1 < totalWidth) result += "-+";
                }
                result += "
";
            }
        }
        return result;
    }
}```
```package net.byte_welt.sudoku;

/**
 * User: Christian
 * Date: 20.07.13
 * Time: 17:43
 */
class MatrixEntry /*implements Comparable<MatrixEntry>*/ {
    private final int row;
    private final int col;
    private final MatrixEntry columnHeader;
    private MatrixEntry left;
    private MatrixEntry right;
    private MatrixEntry upper;
    private MatrixEntry lower;
    private int value;

    MatrixEntry() {
        row = -1;
        col = -1;
        value = -1;
        left = this;
        right = this;
        upper = this;
        lower = this;
        columnHeader = this;
    }

    MatrixEntry(int col, int row, int value, MatrixEntry columnHeader) {
        this.row = row;
        this.col = col;
        this.columnHeader = columnHeader;
        this.value = value;
    }

    void insertBefore(MatrixEntry entry) {
        entry.right = this;
        entry.left = left;
        left.right = entry;
        left = entry;
    }

    public void insertAbove(MatrixEntry entry) {
        entry.lower = this;
        entry.upper = upper;
        upper.lower = entry;
        upper = entry;
    }

    public void setLeft(MatrixEntry left) {
        this.left = left;
    }

    public MatrixEntry getRight() {
        return right;
    }

    public void setRight(MatrixEntry right) {
        this.right = right;
    }

    MatrixEntry get(int row, int value) {
        MatrixEntry result = this.columnHeader;
        // Endlosschleife, falls col nicht gefunden wird
        /*while (result.value != 243 + col * 9 + row) {
            result = result.right;
        }*/
        // Endlosschleife, falls row nicht gefunden wird
        while (result.row != row || result.value != value) {
            result = result.lower;
        }
        return result;
    }

    private boolean removeRow() {
        boolean result = true;
        MatrixEntry p = this.right;
        while (p != this) {
            p.upper.lower = p.lower;
            p.lower.upper = p.upper;
            p.columnHeader.value--;
            if (p.columnHeader.value == 0) result = false;
            p = p.right;
        }
        return result;
    }

    private boolean removeCol() {
        boolean result = true;
        columnHeader.left.right = columnHeader.right;
        columnHeader.right.left = columnHeader.left;
        MatrixEntry p = this.lower;
        while (p != this) {
            if (p != columnHeader)
                if (!p.removeRow()) result = false;
            p = p.lower;
        }
        return result;
    }

    boolean removeEntry() {
        boolean result = true;
        MatrixEntry p = this;
        do {
            if (!p.removeCol()) result = false;
            p = p.right;
        } while (p != this);
        return result;
    }

    MatrixEntry getLower() {
        return lower;
    }

    private void reinsertRow() {
        MatrixEntry p = this.right;
        while (p != this) {
            p.upper.lower = p;
            p.lower.upper = p;
            p.columnHeader.value++;
            p = p.right;
        }
    }

    private void reinsertCol() {
        columnHeader.left.right = columnHeader;
        columnHeader.right.left = columnHeader;
        MatrixEntry p = this.lower;
        while (p != this) {
            if (p != columnHeader)
                p.reinsertRow();
            p = p.lower;
        }
    }

    void reinsert() {
        MatrixEntry p = this;
        do {
            p.reinsertCol();
            p = p.right;
        } while (p != this);
    }

    int getCol() {
        return col;
    }

    int getRow() {
        return row;
    }

    int getValue() {
        return value;
    }

    int countRows() {
        int result = 0;
        MatrixEntry p = columnHeader.lower;

        while (p != columnHeader) {
            result++;
            p = p.lower;
        }

        columnHeader.value = result;
        return result;
    }

    /*@Override
    public int compareTo(MatrixEntry o) {
        if (value > o.value) return 1;
        if (value < o.value) return -1;
        return 0;
    }*/

    int getRowCount() {
        return columnHeader.getValue();
    }
}```
```package net.byte_welt.sudoku;

/**
 * User: Christian
 * Date: 20.07.13
 * Time: 21:57
 */
class MatrixHead implements Comparable<MatrixHead> {
    private final int rows;
    private final MatrixEntry head;

    public MatrixHead(int rows, MatrixEntry head) {
        this.rows = rows;
        this.head = head;
    }

    MatrixEntry getHead() {
        return head;
    }

    @Override
    public int compareTo(MatrixHead o) {
        return Integer.compare(rows, o.rows);
    }
}```

Die entrekursivierte Lösung vom User bone2:
```package net.byte_welt.sudoku;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class SudokuBone2 implements Sudoku {
    private long steps = 0;

    public class Position implements Comparable<Position> {
        private final int x;
        private final int y;
        private final int count;

        public Position(int x, int y, int count) {
            this.x = x;
            this.y = y;
            this.count = count;
        }

        @Override
        public int compareTo(Position o) {
            if (count > o.count) {
                return -1;
            }
            if (count < o.count) {
                return 1;
            }
            return 0;
        }

        public int getX() {
            return x;
        }

        public int getY() {
            return y;
        }
    }

    private final int[] columns;
    private final int[] rows;
    private final int[] squares;
    private final int[][] values;
    private final int limit;
    private final int squareSize;
    private final List<Position> positions;

    public SudokuBone2(int[][] sudoku, int limit) {
        limit *= limit;
        values = new int[limit][limit];
        rows = new int[limit];
        squares = new int[limit];
        columns = new int[limit];
        Arrays.fill(rows, 1);
        Arrays.fill(squares, 1);
        Arrays.fill(columns, 1);
        squareSize = (int) Math.sqrt(limit);
        this.limit = limit;

        // prepare
        for (int y = 0; y < limit; y++) {
            for (int x = 0; x < limit; x++) {
                values[y][x] = sudoku[y][x];
                rows[y] |= 1 << sudoku[y][x];
                columns[x] |= 1 << sudoku[y][x];
                squares[x / squareSize + y / squareSize * squareSize] |= 1 << sudoku[y][x];
            }
        }

        // get best order
        positions = new ArrayList<>();
        Position[][] positionMatrix = new Position[limit][limit];

        for (int y = 0; y < limit; y++) {
            for (int x = 0; x < limit; x++) {
                if (values[y][x] == 0) {
                    int usedValues = rows[y] | columns[x] | squares[x / squareSize + y / squareSize * squareSize];
                    int c = 0;

                    for (int i = 1; i <= limit; i++) {
                        if ((usedValues & (1 << i)) != 0) {
                            c++;
                        }
                    }

                    Position posi = new Position(x, y, c);
                    positionMatrix[y][x] = posi;
                    positions.add(posi);
                }
            }
        }

        Collections.sort(positions);
    }

    @Override
    public boolean solve() {
        steps = 0;
        solveSudoku(0);
        return true;
    }

    @Override
    public long getSteps() {
        return steps;
    }

    @Override
    public String toString() {
        String result = "";
        for (int[] aRow : values) {
            result += Arrays.toString(aRow) + "
";
        }
        return result;
    }

    private boolean solveSudoku(int current) {
        steps++;
        if (current >= positions.size()) {
            return true;
        }

        int x = positions.get(current).getX();
        int y = positions.get(current).getY();
        int square = x / squareSize + y / squareSize * squareSize;
        int usedValues = rows[y] | columns[x] | squares[square];

        for (int i = 1; i <= limit; i++) {
            if (((1 << i) & usedValues) == 0) {
                int shifted = 1 << i;
                rows[y] |= shifted;
                columns[x] |= shifted;
                squares[square] |= shifted;
                values[y][x] = i;

                if (solveSudoku(current + 1)) {
                    return true;
                }

                rows[y] ^= shifted;
                columns[x] ^= shifted;
                squares[square] ^= shifted;
            }
        }

        values[y][x] = 0;
        return false;
    }
}```

Eine Main-Klasse mit Beispielsudokus (den Benchmark würde ich heute anders machen...):
```package net.byte_welt.sudoku;

import java.util.ArrayList;
import java.util.List;

/**
 * User: Christian
 * Date: 16.07.13
 * Time: 18:51
 */
public class Main {
    public static void main(String[] args) {
        int[][] easy16x16 = {
                {3, 0, 14, 0, 15, 7, 4, 16, 0, 0, 6, 5, 0, 0, 0, 0},
                {12, 0, 0, 0, 0, 0, 0, 11, 0, 10, 16, 13, 0, 5, 0, 0},
                {0, 0, 0, 0, 6, 9, 5, 0, 0, 0, 0, 0, 13, 12, 8, 14},
                {7, 11, 0, 4, 0, 0, 0, 0, 0, 0, 0, 0, 0, 16, 0, 0},

                {0, 13, 1, 0, 9, 12, 8, 6, 0, 0, 0, 0, 0, 0, 0, 0},
                {10, 0, 15, 0, 0, 16, 0, 13, 0, 11, 0, 6, 9, 0, 0, 0},
                {0, 0, 16, 0, 0, 0, 0, 5, 0, 1, 12, 7, 10, 13, 0, 0},
                {11, 9, 12, 0, 0, 0, 2, 10, 0, 0, 15, 0, 3, 7, 0, 5},

                {13, 3, 8, 0, 4, 2, 12, 7, 0, 0, 9, 0, 0, 0, 16, 0},
                {0, 0, 0, 0, 0, 11, 0, 8, 0, 16, 0, 2, 0, 9, 15, 0},
                {9, 0, 11, 2, 0, 0, 0, 0, 0, 4, 7, 10, 0, 0, 3, 8},
                {0, 0, 0, 16, 0, 1, 0, 9, 0, 0, 0, 8, 0, 4, 2, 0},

                {0, 1, 9, 14, 2, 10, 11, 0, 0, 0, 0, 0, 8, 0, 0, 16},
                {16, 6, 10, 15, 0, 8, 9, 0, 0, 0, 13, 12, 0, 0, 0, 11},
                {0, 12, 0, 0, 5, 3, 15, 4, 0, 0, 0, 0, 14, 0, 0, 7},
                {0, 0, 0, 0, 16, 0, 0, 0, 11, 15, 8, 0, 0, 0, 1, 4}
        };
        int[][] hard16x16 = {
                {0, 0, 0, 8, 3, 0, 0, 0, 9, 12, 10, 2, 0, 0, 11, 14},
                {0, 0, 0, 10, 6, 13, 0, 0, 16, 0, 0, 0, 0, 0, 4, 9},
                {0, 0, 0, 15, 0, 0, 11, 16, 0, 4, 0, 0, 0, 12, 13, 0},
                {0, 14, 5, 3, 0, 12, 0, 0, 0, 0, 0, 6, 0, 0, 2, 16},

                {0, 8, 0, 0, 11, 0, 10, 0, 6, 0, 7, 0, 9, 0, 5, 2},
                {0, 0, 1, 16, 0, 0, 13, 0, 0, 15, 3, 0, 0, 6, 0, 0},
                {10, 12, 0, 0, 0, 14, 0, 0, 5, 0, 16, 8, 15, 0, 0, 0},
                {0, 0, 0, 0, 0, 4, 0, 5, 11, 0, 0, 13, 0, 0, 0, 0},

                {0, 0, 0, 0, 12, 0, 0, 7, 10, 0, 13, 0, 0, 0, 0, 0},
                {0, 0, 0, 6, 16, 10, 0, 13, 0, 0, 12, 0, 0, 0, 9, 8},
                {0, 0, 14, 0, 0, 11, 15, 0, 0, 16, 0, 0, 3, 10, 0, 0},
                {2, 11, 0, 12, 0, 5, 0, 8, 0, 6, 0, 15, 0, 0, 7, 0},

                {15, 5, 0, 0, 14, 0, 0, 0, 0, 0, 2, 0, 12, 1, 16, 0},
                {0, 3, 4, 0, 0, 0, 12, 0, 1, 9, 0, 0, 13, 0, 0, 0},
                {6, 10, 0, 0, 0, 0, 0, 1, 0, 0, 5, 11, 4, 0, 0, 0},
                {16, 1, 0, 0, 4, 15, 6, 3, 0, 0, 0, 12, 11, 0, 0, 0}
        };
        int[][][] sudokus = {
                {{0, 0, 0, 0, 0, 0, 0, 1, 0}, {4, 0, 0, 0, 0, 0, 0, 0, 0}, {0, 2, 0, 0, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 5, 0, 4, 0, 7}, {0, 0, 8, 0, 0, 0, 3, 0, 0}, {0, 0, 1, 0, 9, 0, 0, 0, 0}, {3, 0, 0, 4, 0, 0, 2, 0, 0}, {0, 5, 0, 1, 0, 0, 0, 0, 0}, {0, 0, 0, 8, 0, 6, 0, 0, 0}},
                {{0, 3, 0, 0, 0, 0, 0, 0, 0}, {0, 0, 0, 1, 9, 5, 0, 0, 0}, {0, 0, 8, 0, 0, 0, 0, 6, 0}, {8, 0, 0, 0, 6, 0, 0, 0, 0}, {4, 0, 0, 8, 0, 0, 0, 0, 1}, {0, 0, 0, 0, 2, 0, 0, 0, 0}, {0, 6, 0, 0, 0, 0, 2, 8, 0}, {0, 0, 0, 4, 1, 9, 0, 0, 5}, {0, 0, 0, 0, 0, 0, 0, 7, 0}},
                {{0, 0, 0, 0, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 3, 0, 8, 5}, {0, 0, 1, 0, 2, 0, 0, 0, 0}, {0, 0, 0, 5, 0, 7, 0, 0, 0}, {0, 0, 4, 0, 0, 0, 1, 0, 0}, {0, 9, 0, 0, 0, 0, 0, 0, 0}, {5, 0, 0, 0, 0, 0, 0, 7, 3}, {0, 0, 2, 0, 1, 0, 0, 0, 0}, {0, 0, 0, 0, 4, 0, 0, 0, 9}},
                {{0, 0, 0, 0, 0, 0, 0, 1, 2}, {0, 0, 0, 0, 0, 0, 0, 0, 3}, {0, 0, 2, 3, 0, 0, 4, 0, 0}, {0, 0, 1, 8, 0, 0, 0, 0, 5}, {0, 6, 0, 0, 7, 0, 8, 0, 0}, {0, 0, 0, 0, 0, 9, 0, 0, 0}, {0, 0, 8, 5, 0, 0, 0, 0, 0}, {9, 0, 0, 0, 4, 0, 5, 0, 0}, {4, 7, 0, 0, 0, 6, 0, 0, 0}},
                {{0, 2, 0, 0, 5, 0, 7, 0, 0}, {4, 0, 0, 1, 0, 0, 0, 0, 6}, {8, 0, 0, 0, 0, 3, 0, 0, 0}, {2, 0, 0, 0, 0, 8, 0, 0, 3}, {0, 4, 0, 0, 2, 0, 5, 0, 0}, {0, 0, 0, 6, 0, 0, 0, 1, 0}, {0, 0, 2, 0, 9, 0, 0, 0, 0}, {0, 9, 0, 0, 0, 0, 0, 0, 5}, {7, 0, 4, 0, 0, 0, 9, 0, 0}},
                {{0, 0, 0, 0, 0, 0, 0, 0, 3}, {0, 0, 1, 0, 0, 5, 6, 0, 0}, {0, 9, 0, 0, 4, 0, 0, 7, 0}, {0, 0, 0, 0, 0, 9, 0, 5, 0}, {7, 0, 0, 0, 0, 0, 0, 0, 8}, {0, 5, 0, 4, 0, 2, 0, 0, 0}, {0, 8, 0, 0, 2, 0, 0, 9, 0}, {0, 0, 3, 5, 0, 0, 1, 0, 0}, {6, 0, 0, 0, 0, 0, 0, 0, 0}},
                {{1, 2, 0, 3, 0, 0, 0, 0, 4}, {3, 5, 0, 0, 0, 0, 1, 0, 0}, {0, 0, 4, 0, 0, 0, 0, 0, 0}, {0, 0, 5, 4, 0, 0, 2, 0, 0}, {6, 0, 0, 0, 7, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 8, 0, 9, 0}, {0, 0, 3, 1, 0, 0, 5, 0, 0}, {0, 0, 0, 0, 0, 9, 0, 7, 0}, {0, 0, 0, 0, 6, 0, 0, 0, 8}},
                {{1, 0, 0, 0, 0, 0, 0, 0, 2}, {0, 9, 0, 4, 0, 0, 0, 5, 0}, {0, 0, 6, 0, 0, 0, 7, 0, 0}, {0, 5, 0, 9, 0, 3, 0, 0, 0}, {0, 0, 0, 0, 7, 0, 0, 0, 0}, {0, 0, 0, 8, 5, 0, 0, 4, 0}, {7, 0, 0, 0, 0, 0, 6, 0, 0}, {0, 3, 0, 0, 0, 9, 0, 8, 0}, {0, 0, 2, 0, 0, 0, 0, 0, 1}},
                {{0, 0, 0, 0, 0, 0, 0, 3, 9}, {0, 0, 0, 0, 0, 1, 0, 0, 5}, {0, 0, 3, 0, 5, 0, 8, 0, 0}, {0, 0, 8, 0, 9, 0, 0, 0, 6}, {0, 7, 0, 0, 0, 2, 0, 0, 0}, {1, 0, 0, 4, 0, 0, 0, 0, 0}, {0, 0, 9, 0, 8, 0, 0, 5, 0}, {0, 2, 0, 0, 0, 0, 6, 0, 0}, {4, 0, 0, 7, 0, 0, 0, 0, 0}},
                {{1, 2, 0, 3, 0, 0, 0, 0, 0}, {4, 0, 0, 0, 0, 0, 3, 0, 0}, {0, 0, 3, 0, 5, 0, 0, 0, 0}, {0, 0, 4, 2, 0, 0, 5, 0, 0}, {0, 0, 0, 0, 8, 0, 0, 0, 9}, {0, 6, 0, 0, 0, 5, 0, 7, 0}, {0, 0, 1, 5, 0, 0, 2, 0, 0}, {0, 0, 0, 0, 9, 0, 0, 6, 0}, {0, 0, 0, 0, 0, 7, 0, 0, 8}},
                {{0, 0, 3, 0, 0, 6, 0, 8, 0}, {0, 0, 0, 1, 0, 0, 2, 0, 0}, {0, 0, 0, 0, 7, 0, 0, 0, 4}, {0, 0, 9, 0, 0, 8, 0, 6, 0}, {0, 3, 0, 0, 4, 0, 0, 0, 1}, {0, 7, 0, 2, 0, 0, 0, 0, 0}, {3, 0, 0, 0, 0, 5, 0, 0, 0}, {0, 0, 5, 0, 0, 0, 6, 0, 0}, {9, 8, 0, 0, 0, 0, 0, 5, 0}},
                {{1, 0, 0, 0, 0, 0, 0, 0, 9}, {0, 0, 6, 7, 0, 0, 0, 2, 0}, {0, 8, 0, 0, 0, 0, 4, 0, 0}, {0, 0, 0, 0, 7, 5, 0, 3, 0}, {0, 0, 5, 0, 0, 2, 0, 0, 0}, {0, 6, 0, 3, 0, 0, 0, 0, 0}, {0, 9, 0, 0, 0, 0, 8, 0, 0}, {6, 0, 0, 0, 4, 0, 0, 0, 1}, {0, 0, 2, 5, 0, 0, 0, 6, 0}},
                {{0, 0, 9, 0, 0, 0, 4, 0, 0}, {0, 7, 0, 3, 0, 0, 0, 2, 0}, {8, 0, 0, 0, 6, 0, 0, 0, 7}, {1, 0, 0, 8, 0, 0, 0, 0, 6}, {0, 0, 0, 0, 1, 0, 0, 7, 0}, {0, 0, 0, 0, 5, 6, 0, 0, 0}, {3, 0, 0, 0, 0, 5, 0, 0, 1}, {0, 4, 0, 0, 0, 0, 0, 9, 0}, {0, 0, 2, 0, 0, 0, 7, 0, 0}},
                {{0, 0, 0, 0, 9, 0, 0, 5, 0}, {0, 1, 0, 0, 0, 0, 0, 3, 0}, {0, 0, 2, 3, 0, 0, 7, 0, 0}, {0, 0, 4, 5, 0, 0, 0, 7, 0}, {8, 0, 0, 0, 0, 0, 2, 0, 0}, {0, 0, 0, 0, 0, 6, 4, 0, 0}, {0, 9, 0, 0, 1, 0, 0, 0, 0}, {0, 8, 0, 0, 6, 0, 0, 0, 0}, {0, 0, 5, 4, 0, 0, 0, 0, 7}},
                {{4, 0, 0, 0, 3, 0, 0, 0, 0}, {0, 0, 0, 6, 0, 0, 8, 0, 0}, {0, 0, 0, 0, 0, 0, 0, 0, 1}, {0, 0, 0, 0, 5, 0, 0, 9, 0}, {0, 8, 0, 0, 0, 0, 6, 0, 0}, {0, 7, 0, 2, 0, 0, 0, 0, 0}, {0, 0, 0, 1, 0, 2, 7, 0, 0}, {5, 0, 3, 0, 0, 0, 0, 4, 0}, {9, 0, 0, 0, 0, 0, 0, 0, 0}},
                {{7, 0, 8, 0, 0, 0, 3, 0, 0}, {0, 0, 0, 2, 0, 1, 0, 0, 0}, {5, 0, 0, 0, 0, 0, 0, 0, 0}, {0, 4, 0, 0, 0, 0, 0, 2, 6}, {3, 0, 0, 0, 8, 0, 0, 0, 0}, {0, 0, 0, 1, 0, 0, 0, 9, 0}, {0, 9, 0, 6, 0, 0, 0, 0, 4}, {0, 0, 0, 0, 7, 0, 5, 0, 0}, {0, 0, 0, 0, 0, 0, 0, 0, 0}},
                {{3, 0, 7, 0, 4, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 0, 0, 9, 1}, {8, 0, 0, 0, 0, 0, 0, 0, 0}, {4, 0, 0, 0, 0, 0, 7, 0, 0}, {0, 0, 0, 1, 6, 0, 0, 0, 0}, {0, 0, 0, 2, 5, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 0, 3, 8, 0}, {0, 9, 0, 0, 0, 0, 5, 0, 0}, {0, 2, 0, 6, 0, 0, 0, 0, 0}},
                {{0, 0, 0, 0, 0, 0, 0, 0, 8}, {0, 0, 3, 0, 0, 0, 4, 0, 0}, {0, 9, 0, 0, 2, 0, 0, 6, 0}, {0, 0, 0, 0, 7, 9, 0, 0, 0}, {0, 0, 0, 0, 6, 1, 2, 0, 0}, {0, 6, 0, 5, 0, 2, 0, 7, 0}, {0, 0, 8, 0, 0, 0, 5, 0, 0}, {0, 1, 0, 0, 0, 0, 0, 2, 0}, {4, 0, 5, 0, 0, 0, 0, 0, 3}},
                {{0, 0, 0, 0, 0, 0, 0, 1, 0}, {4, 0, 0, 0, 0, 0, 0, 0, 0}, {0, 2, 0, 0, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 5, 0, 4, 0, 7}, {0, 0, 8, 0, 0, 0, 3, 0, 0}, {0, 0, 1, 0, 9, 0, 0, 0, 0}, {3, 0, 0, 4, 0, 0, 2, 0, 0}, {0, 5, 0, 1, 0, 0, 0, 0, 0}, {0, 0, 0, 8, 0, 6, 0, 0, 0}},
                {{0, 0, 0, 0, 0, 0, 0, 1, 2}, {0, 0, 0, 0, 3, 5, 0, 0, 0}, {0, 0, 0, 6, 0, 0, 0, 7, 0}, {7, 0, 0, 0, 0, 0, 3, 0, 0}, {0, 0, 0, 4, 0, 0, 8, 0, 0}, {1, 0, 0, 0, 0, 0, 0, 0, 0}, {0, 0, 0, 1, 2, 0, 0, 0, 0}, {0, 8, 0, 0, 0, 0, 0, 4, 0}, {0, 5, 0, 0, 0, 0, 6, 0, 0}},
                {{1, 0, 0, 0, 0, 0, 0, 0, 2}, {0, 9, 0, 4, 0, 0, 0, 5, 0}, {0, 0, 6, 0, 0, 0, 7, 0, 0}, {0, 5, 0, 3, 0, 4, 0, 0, 0}, {0, 0, 0, 0, 6, 0, 0, 0, 0}, {0, 0, 0, 0, 5, 8, 0, 4, 0}, {0, 0, 2, 0, 0, 0, 6, 0, 0}, {0, 3, 0, 0, 0, 9, 0, 8, 0}, {7, 0, 0, 0, 0, 0, 0, 0, 1}},
                {{0, 0, 0, 0, 0, 1, 0, 2, 0}, {3, 0, 0, 0, 4, 0, 5, 0, 0}, {0, 0, 0, 6, 0, 0, 0, 0, 7}, {0, 0, 2, 0, 0, 0, 0, 0, 1}, {0, 8, 0, 0, 9, 0, 0, 3, 0}, {4, 0, 0, 0, 0, 0, 8, 0, 0}, {5, 0, 0, 0, 0, 2, 0, 0, 0}, {0, 9, 0, 0, 3, 0, 4, 0, 0}, {0, 0, 6, 7, 0, 0, 0, 0, 0}}
        };

        //warmup
        for (int i = 0; i < 5; i++) {
            for (int[][] s : sudokus) {
                Sudoku sudoku = new SudokuExactCover(s, 3);
                //Sudoku sudoku = new SudokuBone2(s, 3);
                sudoku.solve();
            }
        }

        List<Result> results = new ArrayList<>(24);
        long totalStartTime = System.currentTimeMillis();
        for (int[][] s : sudokus) {
            long startTime = System.currentTimeMillis();
            Sudoku sudoku = new SudokuExactCover(s, 3);
            //Sudoku sudoku = new SudokuBone2(s, 3);
            sudoku.solve();
            long finishTime = System.currentTimeMillis();

            results.add(new Result(startTime, finishTime, sudoku));
        }

        Sudoku sudoku = new SudokuExactCover(hard16x16, 4);
        //Sudoku sudoku = new SudokuBone2(hard16x16, 4);
        long startTime = System.currentTimeMillis();
        sudoku.solve();
        long finishTime = System.currentTimeMillis();

        results.add(new Result(startTime, finishTime, sudoku));

        sudoku = new SudokuExactCover(easy16x16, 4);
        //Sudoku sudoku = new SudokuBone2(easy16x16, 4);
        startTime = System.currentTimeMillis();
        sudoku.solve();
        finishTime = System.currentTimeMillis();

        results.add(new Result(startTime, finishTime, sudoku));

        long totalFinishTime = System.currentTimeMillis();
        long totalSteps = 0;
        for (Result result : results) {
            totalSteps += result.getSteps();
            System.out.println("steps: " + result.getSteps());
            System.out.println("time : " + (result.getFinishTime() - result.getStartTime()) + " ms");
            System.out.println(result.getSolution());
            System.out.println("");
        }
        System.out.println("total steps: " + totalSteps);
        System.out.println("total time : " + (totalFinishTime - totalStartTime) + " ms");
    }

    private static class Result {
        private final long startTime;
        private final long finishTime;
        private final Sudoku solution;

        private Result(long startTime, long finishTime, Sudoku solution) {
            this.startTime = startTime;
            this.finishTime = finishTime;
            this.solution = solution;
        }

        private long getStartTime() {
            return startTime;
        }

        private long getFinishTime() {
            return finishTime;
        }

        private long getSteps() {
            return solution.getSteps();
        }

        private String getSolution() {
            return solution.toString();
        }
    }
}```[/spoiler]


Hier findet man übrigens 50.000 lösbare Sudokus, mit denen man super testen kann:
https://sudoku-solver-qt.googlecode.com/svn-history/r96/data/top50000.sdm

Sen-Mithrarin · 5. Mai 2015 um 23:51

MADE MY DAY

scnr

maki · 6. Mai 2015 um 00:45

Finde auch dass er ruhig mit seinem richtigen Account anstatt mit mehreren Gast Accounts haette posten koennen, vor allem weil man sieht dass er sich Muehe gegeben hatte - inkl. Recherche - um um die Frage zu beantworten.

CyborgBeta · 6. Mai 2015 um 01:00

[QUOTE=Sen-Mithrarin]MADE MY DAY

scnr[/QUOTE]

Nagut, @mymaksimus hat jetzt alles, was sie zum Lösen der Aufgabe braucht. Reihe, Spalte UND Quadrat/Square durchgehen, ist immer etwas Fummelei. Man muss sich nur (gut) überlegen, wie das Sudoku gespeichert ist, welcher int ein leeres Feld ist, und was keine Lösung darstellt.

Sudokus gibt es wie Sand am Meer. Man kann auch zufällig “befüllen”, und solange ein Feld auf 0 setzen, bis es 1, 2 oder 3 Lösungen gibt - je nachdem, wie schwer das alles soll - ähnlich wie Wände in einem Labyrinth/Gefängnis entfernen.

grüße

Edit: Eindeutig lösbar sollte es schon sein, sonst wäre das für den Menschen gemein/fies. Es gibt richtige Sudoku-Freaks.

Sen-Mithrarin · 6. Mai 2015 um 06:32

Ein unlösbares Soduku weist auf einen Fehler bei der Erstellung hin und sollte daher nicht vorkommen.
Klar, auch wenn man als Mensch bei so einigen wirklich verzweifelt weils nicht passt oder man mehrere mögliche (teilweise richtige) Ansätze hat sollte ein maschineller Solver eigentlich immer auf mindestens eine eindeutige Lösung kommen. Sonst könnte man, um im Java-Slang zu bleiben, eine IllegalArgumentException(“error - unsolveable”) werfen.

cmrudolph · 6. Mai 2015 um 11:39

Ein echtes Sudoku hat per Definition exakt eine Lösung.

Eine IllegalArgumentException passt hier nicht, die müsste ja fliegen, bevor der Solver durchläuft: nämlich im Konstruktor des Sudokus. Da ist aber noch nicht bekannt, dass es nicht lösbar ist. Daher würde man eine Exception in der solve-Methode werfen. Aller Wahrscheinlichkeit nach eine domänenspezifische.

CyborgBeta · 6. Mai 2015 um 12:06

Meine Idee, dreimal identische values zu habn, ist doch nicht so gut, das macht das ganze mit 151 ziemlich lang:

 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */
package dasisttest;

import java.util.Arrays;

/**
 * @author CB at
 */
public class Sudoku {

    private int[][] row = new int[9][9];
    private int[][] col = new int[9][9];
    private int[][] sqr = new int[9][9];

    public Sudoku(int[][] x9x9) {
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                row**[j] = x9x9**[j];
                col[j]** = x9x9**[j];
                // System.out.println(i + " " + j + " " + (i / 3 * 3 + j / 3) + "  " + ((i * 3 + j % 3) % 9));
                sqr[i / 3 * 3 + j / 3][(i * 3 + j % 3) % 9] = x9x9**[j];
            }
        }
    }

    public boolean solveOne(int i) {
        if (!richtig(i)) {
            return false;
        }
        if (vollsta(i)) {
            return true;
        }
        int j = i / 9, k = i % 9, l = j / 3 * 3 + k / 3, n = (j * 3 + k % 3) % 9, i2 = i + 1;
        if (row[j][k] == 0) {
            for (int m = 1; m <= 9; m++) {
                row[j][k] = m;
                col[k][j] = m;
                sqr[l][n] = m;
                if (solveOne(i2)) {
                    return true;
                }
            }
            row[j][k] = 0;
            col[k][j] = 0;
            sqr[l][n] = 0;
        } else if (solveOne(i2)) {
            return true;
        }
        return false;
    }

    private boolean richtig(int i) {
        if (i != 0) {
            i--;
        }
        int j = i / 9, k = i % 9, l = j / 3 * 3 + k / 3;
        for (int m = 0; m < 8; m++) {
            if (row[j][m] == 0) {
                continue;
            }
            for (int n = m + 1; n < 9; n++) {
                if (row[j][m] == row[j][n]) {
                    return false;
                }
            }
        }
        for (int m = 0; m < 8; m++) {
            if (col[k][m] == 0) {
                continue;
            }
            for (int n = m + 1; n < 9; n++) {
                if (col[k][m] == col[k][n]) {
                    return false;
                }
            }
        }
        for (int m = 0; m < 8; m++) {
            if (sqr[l][m] == 0) {
                continue;
            }
            for (int n = m + 1; n < 9; n++) {
                if (sqr[l][m] == sqr[l][n]) {
                    return false;
                }
            }
        }
        return true;
    }

    private boolean vollsta(int i) {
        return i >= 81;
    }

    public void printSudoku() {
        for (int i = 0; i < 9; i++) {
            if (i % 3 == 0) {
                System.out.println(" ");
            }
            System.out.println("");
            for (int j = 0; j < 9; j++) {
                if (j % 3 == 0) {
                    System.out.print(" ");
                }
                if (row**[j] != 0) {
                    System.out.print(" " + row**[j]);
                } else {
                    System.out.print(" x");
                }
            }
        }

        System.out.println(""); // Kontrolle
        System.out.println("");
        for (int i = 0; i < 9; i++) {
            System.out.println(Arrays.toString(row**));
        }

        System.out.println(""); // Kontrolle
        System.out.println("");
        for (int i = 0; i < 9; i++) {
            System.out.println(Arrays.toString(col**));
        }

        System.out.println(""); // Kontrolle
        System.out.println("");
        for (int i = 0; i < 9; i++) {
            System.out.println(Arrays.toString(sqr**));
        }
    }

    public static void main(String[] args) {
        Sudoku sudoku = new Sudoku(new int[][]{
            {3, 0, 0, 0, 1, 5, 0, 4, 2},
            {7, 5, 6, 0, 0, 0, 0, 0, 0},
            {0, 0, 0, 0, 9, 0, 0, 0, 8},
            {0, 0, 0, 3, 0, 0, 4, 0, 0},
            {0, 0, 0, 5, 0, 2, 8, 0, 0},
            {1, 7, 0, 0, 0, 0, 0, 5, 3},
            {0, 0, 1, 0, 0, 7, 9, 8, 6},
            {2, 0, 8, 1, 0, 0, 0, 0, 0},
            {0, 0, 0, 0, 3, 6, 1, 2, 5}
        });
        sudoku.printSudoku();
        System.out.println(sudoku.solveOne(0));
        sudoku.printSudoku();
    }
}```


ausgabe
[spoiler]

run:

3 x x x 1 5 x 4 2
7 5 6 x x x x x x
x x x x 9 x x x 8

x x x 3 x x 4 x x
x x x 5 x 2 8 x x
1 7 x x x x x 5 3

x x 1 x x 7 9 8 6
2 x 8 1 x x x x x
x x x x 3 6 1 2 5

[3, 0, 0, 0, 1, 5, 0, 4, 2]
[7, 5, 6, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 9, 0, 0, 0, 8]
[0, 0, 0, 3, 0, 0, 4, 0, 0]
[0, 0, 0, 5, 0, 2, 8, 0, 0]
[1, 7, 0, 0, 0, 0, 0, 5, 3]
[0, 0, 1, 0, 0, 7, 9, 8, 6]
[2, 0, 8, 1, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 3, 6, 1, 2, 5]

[3, 7, 0, 0, 0, 1, 0, 2, 0]
[0, 5, 0, 0, 0, 7, 0, 0, 0]
[0, 6, 0, 0, 0, 0, 1, 8, 0]
[0, 0, 0, 3, 5, 0, 0, 1, 0]
[1, 0, 9, 0, 0, 0, 0, 0, 3]
[5, 0, 0, 0, 2, 0, 7, 0, 6]
[0, 0, 0, 4, 8, 0, 9, 0, 1]
[4, 0, 0, 0, 0, 5, 8, 0, 2]
[2, 0, 8, 0, 0, 3, 6, 0, 5]

[3, 0, 0, 7, 5, 6, 0, 0, 0]
[0, 1, 5, 0, 0, 0, 0, 9, 0]
[0, 4, 2, 0, 0, 0, 0, 0, 8]
[0, 0, 0, 0, 0, 0, 1, 7, 0]
[3, 0, 0, 5, 0, 2, 0, 0, 0]
[4, 0, 0, 8, 0, 0, 0, 5, 3]
[0, 0, 1, 2, 0, 8, 0, 0, 0]
[0, 0, 7, 1, 0, 0, 0, 3, 6]
[9, 8, 6, 0, 0, 0, 1, 2, 5]
true

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

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

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

[3, 8, 9, 7, 1, 5, 6, 4, 2]
[7, 5, 6, 2, 8, 4, 3, 9, 1]
[4, 1, 2, 6, 9, 3, 5, 7, 8]
[8, 2, 5, 3, 7, 1, 4, 6, 9]
[6, 9, 3, 5, 4, 2, 8, 1, 7]
[1, 7, 4, 9, 6, 8, 2, 5, 3]
[5, 3, 1, 4, 2, 7, 9, 8, 6]
[2, 6, 8, 1, 5, 9, 7, 3, 4]
[9, 4, 7, 8, 3, 6, 1, 2, 5]

[3, 7, 4, 8, 6, 1, 5, 2, 9]
[8, 5, 1, 2, 9, 7, 3, 6, 4]
[9, 6, 2, 5, 3, 4, 1, 8, 7]
[7, 2, 6, 3, 5, 9, 4, 1, 8]
[1, 8, 9, 7, 4, 6, 2, 5, 3]
[5, 4, 3, 1, 2, 8, 7, 9, 6]
[6, 3, 5, 4, 8, 2, 9, 7, 1]
[4, 9, 7, 6, 1, 5, 8, 3, 2]
[2, 1, 8, 9, 7, 3, 6, 4, 5]

[3, 8, 9, 7, 5, 6, 4, 1, 2]
[7, 1, 5, 2, 8, 4, 6, 9, 3]
[6, 4, 2, 3, 9, 1, 5, 7, 8]
[8, 2, 5, 6, 9, 3, 1, 7, 4]
[3, 7, 1, 5, 4, 2, 9, 6, 8]
[4, 6, 9, 8, 1, 7, 2, 5, 3]
[5, 3, 1, 2, 6, 8, 9, 4, 7]
[4, 2, 7, 1, 5, 9, 8, 3, 6]
[9, 8, 6, 7, 3, 4, 1, 2, 5]
BUILD SUCCESSFUL (total time: 47 Min.)

[/spoiler]


Wie soll man bitte auf Anhieb das `l = j / 3 * 3 + k / 3, n = (j * 3 + k % 3) % 9,` wissen? Außerdem musste ich mir mit 57-59 etwas behelfen. Richtig, vollständig, sollte doch in den Schleifenrumpf geschrieben werden. Schnell ist es, auch wenn nicht Sets und Iterationen.

Wer das nachspielen möchte: [Sudoku leicht - Für schnelle Runden](http://sudoku.tagesspiegel.de/sudoku-leicht/)

CyborgGamma · 6. Mai 2015 um 12:24

@CyborgBeta Schon mal was von Funktionen gehört?

Habe mir jetzt nicht deinen ganzen Post angeschaut, aber schon beim schnellen überfliegen des unleserlichem Codes (oder jedenfalls Code der mich nicht wirklich zum lesen animiert) ist mir z.b. das hier aufgefallen

CyborgBeta:

//...
        System.out.println(""); // Kontrolle
        System.out.println("");
        for (int i = 0; i < 9; i++) {
            System.out.println(Arrays.toString(row**));
        }

        System.out.println(""); // Kontrolle
        System.out.println("");
        for (int i = 0; i < 9; i++) {
            System.out.println(Arrays.toString(col**));
        }

        System.out.println(""); // Kontrolle
        System.out.println("");
        for (int i = 0; i < 9; i++) {
            System.out.println(Arrays.toString(sqr**));
        }
//...

Fällt dir da was auf?
Du hast dort 3 mal den quasie gleichen Block. Wenn man sowas hat, kann man oder besser sollte man das in eine Methode/Funktion auslagern. Das wird als ein Aspekt von Clean Code gesehen.
Dann würde dein Code bzw dieser Block so aussehen, was es dann auch leserlicher macht.

//...
private void print(int[] array){
	System.out.println(""); // Kontrolle
    System.out.println("");
    for (int i = 0; i < 9; i++) {
       System.out.println(Arrays.toString(array**));
    }
}
//...
		print(row);
		print(col);
		print(sqr);
//...

CyborgBeta · 6. Mai 2015 um 12:29

Also wie man hier behandelt wird…

Streich einfach Zeile 1 bis 20 und Zeile 24, das sind (nur) Kontrollausgaben.

Edit: Sry, es ging um das „Grundgerüst“. Funktionen, ja, funktionierte wahrscheinlich auch in Prolog.

Bei richtig() hab ich zu kompliziert gedacht, jedes Elem wird mit jedem verglichen, aber wenn man davon ausgeht, es sei am Anfang nicht falsch, nur das aktuelle untersuchen.

Wie ich gerade sehe, scheint @mymaksimus das nicht zu interessieren. Naja, ich muss ja nicht für ihn Abi machen.

mymaksimus · 6. Mai 2015 um 13:51

[OT]nö er hat schon recht, aber ich habe noch nie lesbaren code von dir gesehen, beta. siehs ein.
Ach ja: Ich wusste nach dem ersten satz das du es bist XD[/OT]

okay leute, danke euch.

Hm, einfach null zurückgeben… also daaarauf muss man erst mal kommen xD
nein klar, blöd dass es mir nicht selber aufgefallen ist.

auch dir danke rudolph, ich schau mir deinen code mal an, wenn ich zeit hab.
sieht interessant aus ^^

*** Edit ***

[OT]hä? nur weil ich n tag nicht antworte?

Nein… ich bezweifle auch ob ich das wollen würde…[/OT]

CyborgBeta · 6. Mai 2015 um 13:52

Nochmal:
[spoiler]```/*

To change this license header, choose License Headers in Project Properties.
To change this template file, choose Tools | Templates
and open the template in the editor.
*/
package dasisttest;

/**

@author CB at
*/
public class Sudoku {

private int[][] row = new int[9][9];
private int[][] col = new int[9][9];
private int[][] sqr = new int[9][9];

public Sudoku(int[][] x9x9) {
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
row**[j] = x9x9**[j];
col[j]** = x9x9**[j];
sqr[i / 3 * 3 + j / 3][(i * 3 + j % 3) % 9] = x9x9**[j];
}
}
}

public boolean solveOne(int i) {
if (!richtig(i)) {
return false;
}
if (vollstae(i)) {
return true;
}
int j = i / 9, k = i % 9, l = j / 3 * 3 + k / 3, n = (j * 3 + k % 3) % 9, i2 = i + 1;
if (row[j][k] == 0) {
for (int m = 1; m <= 9; m++) {
row[j][k] = m;
col[k][j] = m;
sqr[l][n] = m;
if (solveOne(i2)) {
return true;
}
}
row[j][k] = 0;
col[k][j] = 0;
sqr[l][n] = 0;
} else if (solveOne(i2)) {
return true;
}
return false;
}

private boolean richtig(int i) {
if (i > 0) {
i–;
}
```
 int j = i / 9, k = i % 9, l = j / 3 * 3 + k / 3;
 for (int m = 0; m < 8; m++) {
     if (row[j][m] == 0) {
         continue;
     }
     for (int n = m + 1; n < 9; n++) {
         if (row[j][m] == row[j][n]) {
             return false;
         }
     }
 }
 for (int m = 0; m < 8; m++) {
     if (col[k][m] == 0) {
         continue;
     }
     for (int n = m + 1; n < 9; n++) {
         if (col[k][m] == col[k][n]) {
             return false;
         }
     }
 }
 for (int m = 0; m < 8; m++) {
     if (sqr[l][m] == 0) {
         continue;
     }
     for (int n = m + 1; n < 9; n++) {
         if (sqr[l][m] == sqr[l][n]) {
             return false;
         }
     }
 }
 return true;
```
}

private boolean vollstae(int i) {
return i >= 81;
}

public void printSudoku() {
for (int i = 0; i < 9; i++) {
if (i % 3 == 0) {
System.out.println(" “);
}
System.out.println(”");
```
     for (int j = 0; j < 9; j++) {
         if (j % 3 == 0) {
             System.out.print(" ");
         }
         if (row**[j] != 0) {
             System.out.print(" " + row**[j]);
         } else {
             System.out.print(" x");
         }
     }
 }
```
}

public static void main(String[] args) {
Sudoku sudoku = new Sudoku(new int[][]{
{3, 0, 0, 0, 1, 5, 0, 4, 2},
{7, 5, 6, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 9, 0, 0, 0, 8},
{0, 0, 0, 3, 0, 0, 4, 0, 0},
{0, 0, 0, 5, 0, 2, 8, 0, 0},
{1, 7, 0, 0, 0, 0, 0, 5, 3},
{0, 0, 1, 0, 0, 7, 9, 8, 6},
{2, 0, 8, 1, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 3, 6, 1, 2, 5}
});
sudoku.printSudoku();
System.out.println(sudoku.solveOne(0));
sudoku.printSudoku();
}
}```[/spoiler]

Jetzt mit einer schönen Ausgabe und nur 132 Zeilen.

Ich erkläre jetzt die Variablen, damit das sofort verständlich ist:

j = aktuelle Zeile,
k = aktuelle Spalte,
l = # aktuelles Quadrat (wahrscheinlich heißt das nicht Quadrat),
n = Index innerhalb des aktuellen Quadrats,
i2 = i + 1 = nächster Schritt,
m = aktueller Kandidat (1 … 9), den man einsetzen kann,
Rekursive Methode hat Parameter, Abbruchbedingung, nächster/ Kandidat und rekursiver Aufruf. immer. Überall.^^

Das lässt sich aber weiter beschleunigen, durch die schon angesprochene Iteration oder iterative … oder Sets … oder man zählt.

Einverstanden damit?

Timothy_Truckle · 6. Mai 2015 um 14:23

[quote=CyborgBeta]Ich erkläre jetzt die Variablen, damit das sofort verständlich ist:[/quote]Warum nennst Du die Variablen nicht gleich so?

bye
TT

Sen-Mithrarin · 6. Mai 2015 um 17:42

Ja, ne, äh, ach damn. Ja, an sich haste ja recht, aber so wars nun auch wieder nicht gemeint.

achtung : unterirdisch schlechter Wortwitz ~ vermutlich weil ihm sprechende Variablen unbekannt sind

[ot]ich weis ich bin aktuell i-wie nur am trollen, aber bei den vorlagen kann man einfach nicht anders …[/ot]

cmrudolph · 6. Mai 2015 um 22:01

[quote=mymaksimus]auch dir danke rudolph, ich schau mir deinen code mal an, wenn ich zeit hab.
sieht interessant aus[/quote]
Mein Ansatz bringt dir aber nur was, wenn du dir was zum Thema Exact Cover durchliest, ansonsten wird man ihn wohl nicht verstehen.
Vielleicht finde ich später nocht Material, was auf das Problem der exakten Überdeckung in Bezug auf Sudoku eingeht, frag einfach nochmal nach.

[ot]bitte entweder cmrudolph oder Christian, aber nicht rudolph ;-)[/ot]

CyborgGamma · 7. Mai 2015 um 00:55

@CyborgBeta Tut mir leid, wenn ich versuche Dir zu erklären wie man schöner & leserlicher programmieren kann. So das sich auch mal Leute die Erfahrung mit Programmierung haben Lust haben sich deinen Code mal anzuschauen. Und falls du mal irgendwann In die Softwareentwicklung beruflich gehen willst, ist es auch nicht verkehrt bzw bei uns gefordert, das man ordentlichen Code produziert, der zwar zum einen richtig funktioniert (was deiner vielleicht macht) und auf der anderen Seite lesbar ist, verschiedene Metriken erfüllt (CheckStyle,…)