Convert the backtrack search procedure into a decision procedure which returns 1
ID: 3773144 • Letter: C
Question
Convert the backtrack search procedure into a decision procedure which returns 1 if the puzzle has only one solution; returns 0 if the puzzle has no solution; and returns 2 if the puzzle has more than one solution. Use this decision procedure to create a new puzzle as follows:
- Start with an empty 9x9 board, randomly choose 17 cells of the board and fill them with a feasible value. Run the decision procedure to see if the current board allows at least one solution. If not, repeat this step; if it has exactly one solution, you are done; if not, continue to the next step.
- Repeat the following two steps until the board allows only one solution:
- Randomly choose an empty cell and fill it with a feasible value.
- Run the decision procedure to see if the current board allows at least one solution. If not, undo and repeat the previous step.
- A filled cell is said to be critical if we empty that cell, the board will allow more than one solution. For the puzzle obtained in the previous step, check if every filled cell is critical. If not critical, just empty that cell. Once this step is done, output the puzzle.
Explanation / Answer
import java.applet.* ;
import java.awt.* ;
public class SimplifiedSudoku extends Applet implements Runnable
{
protected int model[][] ;
protected Button view[][] ;
protected void createModel()
{
model = new int[9][9] ;
for( int row = 0; row < 9; row++ )
for( int col = 0; col < 9; col++ )
model[row][col] = 0 ;
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 ;
}
protected void createView()
{
setLayout( new GridLayout(9,9) ) ;
view = new Button[9][9] ;
for( int row = 0; row < 9; row++ )
for( int col = 0; col < 9; col++ )
{
view[row][col] = new Button() ;
add( view[row][col] ) ;
}
}
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( "" ) ;
}
public void init()
{
createModel() ;
createView() ;
updateView() ;
}
protected boolean checkRow( int row, int num )
{
for( int col = 0; col < 9; col++ )
if( model[row][col] == num )
return false ;
return true ;
}
protected boolean checkCol( int col, int num )
{
for( int row = 0; row < 9; row++ )
if( model[row][col] == num )
return false ;
return true ;
}
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 ;
}
public void start()
{
(new Thread(this)).start() ;
}
public void run()
{
try
{
Thread.sleep( 1000 ) ;
solve( 0, 0 ) ;
}
catch( Exception e )
{
}
}
public void solve( int row, int col ) throws Exception
{
if( row > 8 )
throw new Exception( "Solution found" ) ;
if( model[row][col] != 0 )
next( row, col ) ;
else
{
for( int num = 1; num < 10; num++ )
{
if( checkRow(row,num) && checkCol(col,num) && checkBox(row,col,num) )
{
model[row][col] = num ;
updateView() ;
Thread.sleep( 1000 ) ;
next( row, col ) ;
}
}
model[row][col] = 0 ;
updateView() ;
}
}
public void next( int row, int col ) throws Exception
{
if( col < 8 )
solve( row, col + 1 ) ;
else
solve( row + 1, 0 ) ;
}
}