# Backtracking Sudoku Solver

Page 1 of 1

## 4 Replies - 9423 Views - Last Post: 27 February 2013 - 05:03 PMRate Topic: //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'http://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=313763&amp;s=3eb88f3b8f09b2d876650d27a929814f&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

### #1 Buttertoast

Reputation: 1
• Posts: 60
• Joined: 10-January 13

# Backtracking Sudoku Solver

Posted 27 February 2013 - 02:56 PM

Hello, I created a Sudoku with a working Backtracking solving method, but i want the method to show if the
given sudoku can be solved or not. if the sudoku can not be solved it always gets into a loop and doesnt get out.

for example if the given sudoku isnt possible to solve because there are already two even numbers in the same row

this is my method:

```public void solve( int row, int col ) throws Exception
{
// Throw an exception to stop the process if the puzzle is solved
if( row > 8 ){
//Gelöst
}
// If the cell is not empty, continue with the next cell
if( sudo[row][col] != 0 ){
next( row, col ) ;
}
else
{
// Find a valid number for the empty cell
for( int num = 1; num < 10; num++ )
{
if( checkHorizontal(row,num) == false && checkVertikal(col,num)== false&& checkBox(row,col,num)== false )
{
sudo[row][col] = num ;

// Delegate work on the next cell to a resudosive call
next( row, col ) ;
}
}

// No valid number was found, clean up and return to caller
sudo[row][col] = 0 ;
}

}

```

```   public void next( int row, int col ) throws Exception
{
if( col < 8 )
solve( row, col + 1 ) ;
else
solve( row + 1, 0 ) ;
}

```

This post has been edited by Buttertoast: 27 February 2013 - 02:58 PM

Is This A Good Question/Topic? 0

## Replies To: Backtracking Sudoku Solver

### #2 pbl

• There is nothing you can't do with a JTable

Reputation: 8378
• Posts: 31,956
• Joined: 06-March 08

## Re: Backtracking Sudoku Solver

Posted 27 February 2013 - 03:04 PM

A valid Sudoku can always be solved
If you end up that it can't be solved you have to backtrack 1 row
if cannot be solved 2 rows... worst case 3 rows

Have a look at my first 2 of my 7 Sudoku tutorials

http://www.dreaminco...-i-basic-tools/
http://www.dreaminco...he-brute-force/

### #3 Buttertoast

Reputation: 1
• Posts: 60
• Joined: 10-January 13

## Re: Backtracking Sudoku Solver

Posted 27 February 2013 - 03:06 PM

yes, and valid sudokus are always getting solved, but i made a sudoku where you can enter your own sudoku and if the user puts 2 even numbers into for example the same row it isnt possible to solve this sudoku.
And if this happens i want the method to put out a textfield with an error or something like that.
For example the two 3s in the first row

This post has been edited by Buttertoast: 27 February 2013 - 03:38 PM

### #4 GregBrannon

• D.I.C Lover

Reputation: 2250
• Posts: 5,340
• Joined: 10-September 10

## Re: Backtracking Sudoku Solver

Posted 27 February 2013 - 04:48 PM

If your solver follows a logical solution path, eliminating each possible value for a specific cell one at a time, then it should become obvious when the solution begins to repeat. Even before that, the program should know when all possible solutions for a given cell have been tried and failed so that a valid solution does not exist.

For example, imagine a solution in progress has a small number of cells remaining to fill. The solver determines the possible values for each cell, fills any cells with only one possible value, recalculates possible values and repeats until no cells with only one possible value remain. The solver then selects cells with the fewest possible values and tries each value one at a time, recalculating possible values for the remaining cells each time. If all possible values are tried but a valid solution does not result so that the only option for the backtracking algorithm is to repeat solutions already tried, then there is no valid solution.

You should be able to detect the "no valid solution" condition and stop the solver.

### #5 Buttertoast

Reputation: 1
• Posts: 60
• Joined: 10-January 13

## Re: Backtracking Sudoku Solver

Posted 27 February 2013 - 05:03 PM

```public void solve( int row, int col ) throws Exception
{
// Throw an exception to stop the process if the puzzle is solved
if( row > 8 ){
//Gelöst
}
// If the cell is not empty, continue with the next cell
if( sudo[row][col] != 0 ){
next( row, col ) ;
}
else
{
// Find a valid number for the empty cell
for( int num = 1; num < 10; num++ )
{
if( checkHorizontal(row,num) == false && checkVertikal(col,num)== false&& checkBox(row,col,num)== false )
{
if(test ==0){
row2 = row;
col2 = col;
num2 = num;
}
test = test+1;
sudo[row][col] = num ;

if(row2 == row && col2 == col && num2 == num){
next(9,0);
}

// Delegate work on the next cell to a resudosive call
next( row, col ) ;
}
}

// No valid number was found, clean up and return to caller
sudo[row][col] = 0 ;
}

}

```

like this? but it still doesnt work