de.hska.java.aufgaben.backtracking
Class Sudoku

java.lang.Object
  de.hska.java.aufgaben.backtracking.Sudoku

public class Sudoku
extends java.lang.Object

Sudoku lößt Sudoku-Rätsel mit einem Backtracking Algorithmus. Der Suchraum für eine Lösung ist sehr gross - insbesonders, wenn nur wenige Zahlen vorgegeben wurden. In diesen Fällen kann es sein, dass der Algorithmus zu lange braucht.

Um den Suchraum klein zu halten, wird pro Zeile, Spalte und jede von den 3 x 3 Boxen eine bereits gesetzt Zahl vermerkt: Ein Schritt (neue Zahl z) ist nur dann gültig, wenn sie noch nicht in der Zeile, Spalte oder Box vorhanden ist. Dieser Ansatz ist ähnlich zur Lösung des Acht-Damen-Problems und sehr effektiv.

Zurück zum Aufgabentext

Author:

pape

Field Summary

static int

LEERES_FELD

Constructor Summary

Sudoku(int[][] teilloesung)
Erzeugt ein neues Sudoku mit der übergebenen Teillösung.

Method Summary

void	addSudokuListener(SudokuListener sudokuListener)
void	erzeugeSudoku(int anzahlVorgaben) Erzeugt ein Sudoku auf Basis zufälliger Vorgabezahlen.
int[][]	getTeilloesung()
int	getZahl(int zeile, int spalte)
static void	main(java.lang.String[] argv)
void	print() Gibt den Inhalt des Spielfelds am Bildschirm aus.
void	printBoxNummern()
void	remoeSudokuListener(SudokuListener sudokuListener)
boolean	sucheLoesung(int zaehler) Sucht mit Backtracking rekursiv nach einer Lösung für das Sudoku.
void	zahlHatSichGeaendert(int zeile, int spalte)

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

LEERES_FELD

public static final int LEERES_FELD

See Also:

Constant Field Values

Constructor Detail

Sudoku

public Sudoku(int[][] teilloesung)

Erzeugt ein neues Sudoku mit der übergebenen Teillösung.

Method Detail

print

public void print()

Gibt den Inhalt des Spielfelds am Bildschirm aus.

sucheLoesung

public boolean sucheLoesung(int zaehler)

Sucht mit Backtracking rekursiv nach einer Lösung für das Sudoku.

Parameters:

zaehler - Gibt die Anzahl bisher belegter Zellen an - Startwert ist 0

Returns:

true, falls eine Lösung gefunden wurde

erzeugeSudoku

public void erzeugeSudoku(int anzahlVorgaben)

Erzeugt ein Sudoku auf Basis zufälliger Vorgabezahlen.

Parameters:

anzahlVorgaben - Anzahl der Vorgabezahlen

zahlHatSichGeaendert

public void zahlHatSichGeaendert(int zeile,
                                 int spalte)

addSudokuListener

public void addSudokuListener(SudokuListener sudokuListener)

remoeSudokuListener

public void remoeSudokuListener(SudokuListener sudokuListener)

getZahl

public int getZahl(int zeile,
                   int spalte)

getTeilloesung

public int[][] getTeilloesung()

printBoxNummern

public void printBoxNummern()

main

public static void main(java.lang.String[] argv)