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:
Als zweites folgt der eigentliche Löser:
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
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:
Java:
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:
Java:
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
Zuletzt bearbeitet:
