4 Replies - 9817 Views - Last Post: 27 February 2013 - 05:03 PM Rate Topic: -----

#1 Buttertoast   User is offline

  • D.I.C Head

Reputation: 1
  • View blog
  • 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   User is offline

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

Reputation: 8378
  • View blog
  • 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/
Was This Post Helpful? 0
  • +
  • -

#3 Buttertoast   User is offline

  • D.I.C Head

Reputation: 1
  • View blog
  • 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
Posted Image

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

Was This Post Helpful? 0
  • +
  • -

#4 GregBrannon   User is offline

  • D.I.C Lover
  • member icon

Reputation: 2250
  • View blog
  • 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.
Was This Post Helpful? 0
  • +
  • -

#5 Buttertoast   User is offline

  • D.I.C Head

Reputation: 1
  • View blog
  • 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
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1