Wenn Ihr Browser keine Applets anzeigt, gehen Sie zu Sudoku lösen mit JavaScript.
English version of this page with slightly simplified code
Das Applet auf dieser Seite löst ein Sudoku-Rätsel mit Hilfe von Rekursion und Backtracking.
Der Algorithmus verwendet keine genialen Strategien, sondern arbeitet mit simplem Ausprobieren:
Das Applet wird nach jedem Zug durch ein sleep( 1000 ) ausgebremst, damit die Betrachter mitbekommen was läuft...
Das ist ein ziemlich typisches Applet. Der Server liefert nur den Code aus, danach läuft das Programm im Browser
Die englische Version dieser Seite zeigt einen leicht vereinfachte Implementation des Codes
/*********************************************************/
/* */
/* An applet to demonstrate recursion and backtracking */
/* =================================================== */
/* */
/* V0.2 13-NOV-2006 P. Tellenbach www.heimetli.ch */
/* */
/*********************************************************/
import java.applet.* ;
import java.awt.* ;
/**
* Solves a sudoku puzzle by recursion and backtracking
*/
public class Sudoku extends Applet implements Runnable
{
/** The model */
protected int model[][] ;
/** The view */
protected Button view[][] ;
/** Creates the model and sets up the initial situation */
protected void createModel()
{
model = new int[9][9] ;
// Clear all cells
for( int row = 0; row < 9; row++ )
for( int col = 0; col < 9; col++ )
model[row][col] = 0 ;
// Create the initial situation
model[0][0] = 9 ;
model[0][4] = 2 ;
model[0][6] = 7 ;
model[0][7] = 5 ;
model[1][0] = 6 ;
model[1][4] = 5 ;
model[1][7] = 4 ;
model[2][1] = 2 ;
model[2][3] = 4 ;
model[2][7] = 1 ;
model[3][0] = 2 ;
model[3][2] = 8 ;
model[4][1] = 7 ;
model[4][3] = 5 ;
model[4][5] = 9 ;
model[4][7] = 6 ;
model[5][6] = 4 ;
model[5][8] = 1 ;
model[6][1] = 1 ;
model[6][5] = 5 ;
model[6][7] = 8 ;
model[7][1] = 9 ;
model[7][4] = 7 ;
model[7][8] = 4 ;
model[8][1] = 8 ;
model[8][2] = 2 ;
model[8][4] = 4 ;
model[8][8] = 6 ;
}
/** Creates an empty view */
protected void createView()
{
setLayout( new GridLayout(9,9) ) ;
view = new Button[9][9] ;
// Create an empty view
for( int row = 0; row < 9; row++ )
for( int col = 0; col < 9; col++ )
{
view[row][col] = new Button() ;
add( view[row][col] ) ;
}
}
/** Updates the view from the model */
protected void updateView()
{
for( int row = 0; row < 9; row++ )
for( int col = 0; col < 9; col++ )
if( model[row][col] != 0 )
view[row][col].setLabel( String.valueOf(model[row][col]) ) ;
else
view[row][col].setLabel( "" ) ;
}
/** This method is called by the browser when the applet is loaded */
public void init()
{
createModel() ;
createView() ;
updateView() ;
}
/** Checks if num is an acceptable value for the given row */
protected boolean checkRow( int row, int num )
{
for( int col = 0; col < 9; col++ )
if( model[row][col] == num )
return false ;
return true ;
}
/** Checks if num is an acceptable value for the given column */
protected boolean checkCol( int col, int num )
{
for( int row = 0; row < 9; row++ )
if( model[row][col] == num )
return false ;
return true ;
}
/** Checks if num is an acceptable value for the box around row and col */
protected boolean checkBox( int row, int col, int num )
{
row = (row / 3) * 3 ;
col = (col / 3) * 3 ;
for( int r = 0; r < 3; r++ )
for( int c = 0; c < 3; c++ )
if( model[row+r][col+c] == num )
return false ;
return true ;
}
/** This method is called by the browser to start the applet */
public void start()
{
// This statement will start the method 'run' to in a new thread
(new Thread(this)).start() ;
}
/** The active part begins here */
public void run()
{
try
{
// Let the observers see the initial position
Thread.sleep( 1000 ) ;
// Start to solve the puzzle in the left upper corner
solve( 0, 0 ) ;
}
catch( Exception e )
{
}
}
/** Recursive function to find a valid number for one single cell */
public void solve( int row, int col ) throws Exception
{
// Throw an exception to stop the process if the puzzle is solved
if( row > 8 )
throw new Exception( "Solution found" ) ;
else
{
// Skip cells which are not empty
while( model[row][col] != 0 )
{
if( ++col > 8 )
{
col = 0 ;
row++ ;
// Throw an exception to stop the process if the puzzle is solved
if( row > 8 )
throw new Exception( "Solution found" ) ;
}
}
// Find a valid number for the empty cell
for( int num = 1; num < 10; num++ )
{
if( checkRow(row,num) && checkCol(col,num) && checkBox(row,col,num) )
{
model[row][col] = num ;
updateView() ;
// Let the observer see it
Thread.sleep( 1000 ) ;
// Delegate work on the next cell to a recursive call
if( col < 8 )
solve( row, col + 1 ) ;
else
solve( row + 1, 0 ) ;
}
}
// No valid number was found, clean up and return to caller
model[row][col] = 0 ;
updateView() ;
}
}
}