# Sudoku-Löser



## faraday (14. Dez 2015)

Hallo Leute,
ich hoffe, ich bin hier im richtigen Forum. ich würde gerne für ein kleines Projekt einen Sudoku-Löser schreiben. Mein erster Schritt war eine Klasse "Sudoku", die mir Sudokus produziert. Hier der Code:


```
import java.util.Arrays;


/**
* @author faraday
*
*/
public class Sudoku {

    // Definiere Attribute
    private int [][]             entries = new int[9][9];    // Einträge können Inhalt von 0-9 haben.
    public static final Sudoku     ZEROS     = new Sudoku();        // Gibt ein leeres (mit Nullen besetztes) Referenzsudoku aus
  
  
    /**
     * constructor with entries
     *
     * @param entries
     */
    public Sudoku ( int [][] entries ) {
        setZero();
        setEntries( entries );
    }
  
    /**
     * constructor without entries
     */
    public Sudoku() {
        setZero();
    }
  
    /**
     * copy constructor
     *
     * @param Sudoku    sudoku to copy
     */
    public Sudoku( Sudoku su ) {
        this( su.getEntries() );
    }
  
    /**
     * setZeros
     *
     * reset the sudoku to zero
     *
     */
    private void setZero() {
        this.entries = new int [][] {    {0,0,0,0,0,0,0,0,0},
                                        {0,0,0,0,0,0,0,0,0},
                                        {0,0,0,0,0,0,0,0,0},
                                        {0,0,0,0,0,0,0,0,0},
                                        {0,0,0,0,0,0,0,0,0},
                                        {0,0,0,0,0,0,0,0,0},
                                        {0,0,0,0,0,0,0,0,0},
                                        {0,0,0,0,0,0,0,0,0},
                                        {0,0,0,0,0,0,0,0,0}    };
    }
  
    /**
     * setEntries
     *
     * @param entries    entries to set.
     */
    public void setEntries( int [][] entries ) {
        // Prüfe, ob eingegebene Einträge 9x9 entsprechen, andernfalls Fehlermeldung
        if ( entries.length == 9 && entries[0].length == 9 ) {
          
            // Initialisiere for-Schleife, um einzelne Einträge zu überprüfen
            for( int row=0; row < 9; row++ ) {
                for( int col=0; col < 9; col++ ) {
                  
                    // Prüfe, ob Ziffer 0-9 ist, andernfalls Fehlermeldung
                    if( isDigit(entries[row][col]) ) {
                        this.entries[row][col] = entries[row][col];
                    } else {
                        // Fehlermeldung!!!
                    }
                }
            }
        } else {
            // Fehlermeldung!!!
        }
    }
  
    /**
     * getEntries
     *
     * @return    the entries of this sudoku as quadratic array of ints
     */
    public int[][] getEntries() {
        return this.entries;
    }
  
    /**
     * getRow
     *
     * @param row
     * @return    the actual row as array of ints
     */
    public int[] getRow( int row ) {
      
        // Falls Reihe zwischen 0-8, gib Reihe aus, ansonsten Fehlermeldung bzw. Nullreihe
        if( row < 9 && isDigit(row) )
            return this.entries[row];
        else
            // Fehlermeldung!!!
          
        return ZEROS.getRow( 0 );
    }
  
    /**
     * getCol
     *
     * @param col    actual col to look at
     * @return    the actual col as array of ints
     */
    public int[] getCol( int col ) {
        // Falls Spalte zwischen 0-8, gib Spalte aus, ansonsten Fehlermeldung bzw. Nullspalte
        if( col < 9 && isDigit(col) ) {
            int [] colArray = new int[9];
          
            for( int row = 0; row < 9; row++ ) {
                colArray[row] = entries[row][col];
            }
          
            return colArray;
        } else {
            // Fehlermeldung!!!
        }
      
        return ZEROS.getRow( 0 );
    }
  
    /**
     * getSingleEntry
     *
     * @param row    requested row
     * @param col    requested column
     * @return    requested entry
     */
    public int getSingleEntry( int row, int col ) {
        return this.entries[row][col];
    }
  
    /**
     * getBlock
     *
     * @param num    From left to right enumerate blocks
     * @return    the requested block as array of 9
     */
    public int[] getBlock( int num ) {
      
        // Prüfe, ob Eingabe zwischen 0-8 liegt
        if( num < 9 && isDigit(num) ) {
          
            int [] block         = new int [9];
            int [][] entries     = this.getEntries();
          
            // Bestimme Reihe und Spalte des Blocks (in 3x3)
            int bRow = num/3;
            int bCol = num%3;
          
            for( int i=0; i < 9; i++ ) {
                // Schreibe jeweiligen Eintrag von links nach rechts in Array
                block[i] = entries[3*bRow+i/3][3*bCol+i%3];
            }
          
            return block;
          
        } else {
            // Fehlermeldung!!!
        }
      
        return ZEROS.getBlock(0);
    }
  
  
    /**
     * setSingleEntry
     *
     * @param row    row to set
     * @param col    col to set
     * @param entry        content to set in row and col
     */
    public void setSingleEntry( int row, int col, int entry ) {
      
        // Prüfe, ob Eintrag zwischen 0 und 9, sonst Fehlermeldung
        if ( isDigit(entry) ) {
            entries[row][col] = entry;
        } else {
            // Fehlermedlung!!!
        }
    }
  
    /**
     * setRow
     *
     * @param row    row to set
     * @param rowArray    content to set in row
     */
    public void setRow( int row, int [] rowArray ) {
      
        // Prüfe, ob zu beschreibende Reihe 0-8, ansonsten Fehlermeldung
        if( row < 9 && isDigit(row) ) {
            // Initialisiere for-Schleife, für Zeilenüberprüfung und -setzung
            for( int col = 0; col < 9; col++ ) {
                if( isDigit(rowArray[col]) ) {
                    this.entries[row][col] = rowArray[col];
                } else {
                    // Fehlermeldung!!!
                }
            }
        } else {
            // Fehlermeldung!!!
        }
      
    }
  
    /**
     * setcol
     *
     * @param col    col to set
     * @param colArray    content to set in col
     */
    public void setCol( int col, int [] colArray ) {
      
        // Prüfe, ob zu beschreibende Spalte 0-8, ansonsten Fehlermeldung
        if( isDigit(col) && col < 9 ) {
            // Initialisiere for-Schleife, für Spaltenüberprüfung und -setzung
            for( int row = 0; row < 9; row++ ) {
                if( isDigit(colArray[row]) ) {
                    this.entries[row][col] = colArray[row];
                } else {
                    // Fehlermeldung!!!
                }
            }
        } else {
            // Fehlermeldung!!!
        }
      
    }
  
    @Override
    public boolean equals( Object obj )
    {
        if( !(obj instanceof Sudoku) )
            return false;

        if ( obj == this )
            return true;
      
        // Objekt zu Sudoku casten
        Sudoku that = (Sudoku) obj;
      
        // Vergleiche Arrays, falls gleich gib "true" zurück
        if( java.util.Arrays.deepEquals(this.getEntries(), that.getEntries()) )
            return true;
      
        // Falls keine der obigen Bedingungen zutrifft, gib "false" zurück
        return false;
    }
  
    @Override
    public String toString() {
      
        // StrinBuilder starten
        StringBuilder sb = new StringBuilder();
      
        int[][] entries = this.getEntries();
      
        for( int row=0; row < 9; row++ ) {
            for( int col=0; col < 9; col++ ) {
              
                // Eintrag in StringBuilder konkatenieren
                sb.append( entries[row][col] );
              
                // Alle 3 Spalten einen Tab setzen, ansonsten Leerzeichen
                if( col == 2 || col == 5 )
                    sb.append( '\t' );
                else
                    sb.append( ' ' );
            }
          
            // Nach jeder Zeile eine neue beginnen
            sb.append( '\n' );
          
            // Alle 3 Zeilen eine Leerzeile einfügen
            if( row == 2 || row == 5 )
                sb.append( '\n' );
        }
      
        return sb.toString();
      
    }
  
    /**
     * isAprioriSolvable
     *
     * @return    is that sudoku apriori solvable?
     */
    public boolean isAprioriSolvable() {
      
        // Gehe alle 9 Reihen, Spalten, Blöcke durch
        for( int i=0; i < 9; i++ ) {
            // Prüfe, ob zwei Einträge gleich sind, falls ja, persée nicht lösbar
            if( hasEqualEntries( this.getRow( i ) ) || hasEqualEntries( this.getCol( i ) ) || hasEqualEntries( this.getBlock( i ) ) )
                return false;
        }
      
        // Ist die Überprüfung negativ ausgefallen, gib "true" zurück
        return true;
    }
  
    /**
     * hasEqualEntries
     *
     * @param entries    the array to check
     * @return    has the array equal entries?
     */
    static boolean hasEqualEntries( int[] entries ) {
      
        // Klone Eingangsvariable, damit diese nicht verändert wird
        int[] sEntries = entries.clone();
      
        // Sortiere geklontes Array
        Arrays.sort(sEntries);

        for( int i=0; i < sEntries.length - 1; i++ ) {
            if( sEntries[i] != 0 && sEntries[i] == sEntries[i+1] )
                return true;
        }
      
        return false;
    }
  
    /**
     * isComplete
     *
     * @return    is that sudoku complete?
     */
    public boolean isComplete() {
        return ( this.isAprioriSolvable() && this.getZeros() == 0 );
    }
  
    /**
     * isSolvable
     *
     * @return    is that sudoku solvable?
     */
    public boolean isSolvable() {
        return Solver.solve(new Sudoku(this));
    }
  
    /**
     * getZeros
     *
     * @return    counted zeros in Sudoku
     */
    public int getZeros() {
      
        int sumZeros     = 0;
        int[][] entries = this.getEntries();
      
        for( int row=0; row < 9; row++ ) {
            for( int col=0; col < 9; col++ ) {
                if( entries[row][col] == 0 )
                    sumZeros++;
            }
        }
      
        return sumZeros;
    }

  
    /**
     * isDigit
     *
     * @param digit
     * @return  boolean, wether input is digit between 0-9
     */
    static boolean isDigit ( int digit ) {
        if( digit >= 0 && digit <= 9 )
            return true;
        return false;
    }
}
```

Als zweites folgt der eigentliche Löser:


```
import java.util.ArrayList;


public class Solver {
  
    /**
     * solve
     *
     * @param su    input sudoku, which will be modified, until it has finished
     * @return    was there a solution?
     */
    static boolean solve( Sudoku su ) {
      
        // Prüfe, ob das Sudoku legal ist
        if( !su.isAprioriSolvable() )
            return false;
      
        // Prüfe, ob Soduko vollständig
        if( su.isComplete() )
            return true;

        // Setze Kubus, letztes Feld indifferend
        int[][][] possField = new int [9][9][];

        // Definiere Hilfsvariablen
        int minRow = -1;
        int minCol = -1;
      
        for( int row=0; row < 9; row++ ) {
            for( int col=0; col < 9; col++ ) {
                possField[row][col] = getPossible( su, row, col );
              
                if( possField[row][col].length > 0 ) {
                    minRow = row;
                    minCol = col;
                }
            }
        }
      
        // Falls keine Möglichkeiten vorhanden gib "false" zurück
        if( minRow == -1 || minCol == -1 ) {
            return false;
        }
      
        // Falls Möglichkeiten vorhanden, finde Minimum
        for( int row=0; row < 9; row++ ) {
            for( int col=0; col < 9; col++ ) {
                if( possField[row][col].length < possField[minRow][minCol].length && possField[row][col].length > 0 ) {
                    minRow = row;
                    minCol = col;
                }
            }
        }
      
        // Setze Minimum
        int[] minPoss = possField[minRow][minCol];
      
        // Prüfe Minimum
        do {
            // Falls alle Möglichkeiten ausprobiert wurden, und keine Lösung gefunden wurde,
            // setze entsprechenden Eintrag wieder auf 0 zurück und gib "false" als Rückgabe.
            // Das "false" wird nach oben weitergeleitet und diese Möglichkeit wird aus dem Array gestrichen,
            // während die nächste Zahl ausprobiert wird
            if( minPoss.length == 0 ) {
                su.setSingleEntry(minRow, minCol, 0);
                return false;
            }
          
            // Setze den nächsten Eintrag
            su.setSingleEntry(minRow, minCol, minPoss[0]);
          
            // Falls Schleife weiterläuft, entferne den ersten Eintrag
            minPoss = removePoss( minPoss );
        } while( !solve(su) );
      
        return solve(su);
      
    }
  
    static int[] removePoss( int[] poss ) {
      
        int[] rPoss = new int[poss.length - 1];
      
        for( int i=0; i < rPoss.length; i++ )
            rPoss[i] = poss[i+1];
      
        return rPoss;
    }
  
    /**
     * getPossible
     *
     * @param su    input Sudoku
     * @param row    row to check
     * @param col    column to check
     * @return    how much possibilities are there for requested row and column?
     */
    static int[] getPossible( Sudoku su, int row, int col ) {
      
        if( !( Sudoku.isDigit(row) && row < 9 ) || !( Sudoku.isDigit(col) && col < 9 ) )
            return new int[0]; // Fehlermeldung??!
      
        // Falls Eintrag ungleich null, gibt es keine Möglichkeiten
        if( su.getSingleEntry(row, col) != 0 )
            return new int[0];
      
        ArrayList<Integer> poss = new ArrayList<Integer>();      
      
        // Setze Eintrag in Reihe und Spalte und prüfe auf Legalität
        for( int i=1; i <= 9; i++ ) {
            su.setSingleEntry(row, col, i);
          
            if( su.isAprioriSolvable() ) {
                poss.add( i );
            }
        }
      
        // Setze Eintrag auf 0 zurück
        su.setSingleEntry(row, col, 0);
      
        // Deklariere Rückgabearray
        int[] values = new int[poss.size()];
      
        // Schreibe Möglichkeiten in Array
        for( int i=0; i < poss.size(); i++ ) {
            values[i] = poss.get( i );
        }
      
        return values;
    }
  
}
```

Sofern ich nun ein allgemein lösbares Sudoku angebe, hat das Programm absolut keine Probleme eine Lösung zu finden. In weniger als 1 Sekunde. Ebenso gibt es keine Probleme, wenn das Sudoku ganz offensichtlich nicht lösbar ist (zwei gleiche Einträge in Zeile/Spalte/Block). Problematisch wird es bei den subtileren, nicht so offensichtlich lösbaren Sudokus. Zum Beispiel:

0 0 5 | 0 0 0 | 0 0 0
0 0 0 | 0 5 0 | 0 0 0
0 0 0 | 0 0 0 | 1 2 0

0 0 0 | 0 0 0 | 0 0 5
0 0 0 | 0 0 0 | 0 0 0
0 0 0 | 0 0 0 | 0 0 0

0 0 0 | 0 0 0 | 0 0 0
0 0 0 | 0 0 0 | 0 0 0
0 0 0 | 0 0 0 | 0 0 0

In diesem Fall rechnet er ohne Fehlerverursachung und hört nicht auf. Es kommt nichtmal ein Stack-Overflow. Eigentlich sollte er das ursprüngliche Sudoku angeben und ein "false" zurückgeben. Wo ist der Fehler? Danke für eure Hilfe!

Liebe Grüße
fara


----------



## strußi (14. Dez 2015)

das gezeigte soduko ist nicht lösbar (5er sind falsch) und es gibt glaub ich mehr als eine lösung, wenn die 5er korregiert sind


----------



## faraday (14. Dez 2015)

Danke, das ist mir - wie bereits erwähnt - schon klar. Aber der Löser soll mir ja ausgeben, dass das Sudoku eben *nicht *lösbar ist! (Rückgabewert "false"). Und eben dies tut er nicht...


----------



## Joose (14. Dez 2015)

Hast du schon versucht ein paar Debugausgaben einzubauen in deiner "solve" Methode, damit du siehst was er die ganze Zeit macht?
Da solltest du dann auch sehen können wo er "hängen bleibt". Da die Bedingung deiner do/while-Schleife der Aufruf der "solve" Methode ist, ist es schwer zu sagen wann diese Schleife endet.


----------



## faraday (14. Dez 2015)

Ja, aber es passiert zuviel und ist zu undurchsichtig. Wie du schon sagst, ist es schwer zu erkennen, in welcher "Ebene" der Rekursion er sich gerade befindet. :-/

Hast du vielleicht ein paar Tipps, wo und wie man ein paar Debugausgaben einbauen kann?


----------



## faraday (14. Dez 2015)

Ich habe mir mal in kleinen Zeitschritten jeweils die Lösungsvorschläge ausgeben lassen und festgestellt, dass eine Abbruchbedingung gefehlt hat:


```
if( possField[row][col].length == 0 && su.getSingleEntry(row, col) == 0 )
    return false;
```

Danke für eure Hilfe!

Liebe Grüße
fara


----------



## erdmann (22. Dez 2015)

Auch wenn Dein Problem jetzt gelöst ist, könnte Prolog für Dich interessant sein. Man kann Sudokus sicher auch in Java lösen, aber für Probleme dieser Art ist Prolog deutlich besser geeignet. 

In "Sieben Wochen, sieben Sprachen" von Bruce A. Tate findest Du nicht nur eine kleine Einführung in Prolog (und in sechs weitere Sprachen), sondern als Beispiel wird sogar ein Soduku-Löser für kleine Sodukus mit vier Ziffern programmiert. 

Das geht überraschend einfach mit 20 Zeilen Code! Der Clou ist das es genügt die Regeln zu beschreiben, die Lösung ermittelt dann Prolog für Dich. 

Das Lösen richtiger Sodukus (d.h. mit 9 Ziffern) ist dann eine Übungsaufgabe im Buch. Das wird dann ein wenig Länger sein, ist aber nicht wirklich schwer. Vielleicht hast Du ja Lust es damit mal zu versuchen.


----------

