Sudoku Programmers Forum Index

 
 FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister   ProfileProfile   Log inLog in          Games  Calendar

Log in to check your private messagesLog in to check your private messages   

[backtrack] I need some help with my algorithm

 
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Programming sudoku
View previous topic :: View next topic  
Author Message
drowne

Joined: 02 Jun 2009
Posts: 1
:
Location: Italy

Items
PostPosted: Tue Jun 02, 2009 10:24 am    Post subject: [backtrack] I need some help with my algorithm Reply with quote

I'm sorry to bother you, but I can't figure out why my backtrack algorithm is not working properly...

Code:
   private boolean solveSudoku(int i, int j, int[] p) {
       
      // limits
      if (i == 9) {
            i = 0;
            if (++j == 9)
                return true;
           
        }
      
      // if cell is not empty, jump over
        if (getTile(i, j) != 0) {
           return solveSudoku(i+1, j, getActualPuzzle());
        } else {
           // if this is the first cell to fill, save the coords
           if(first) {
              first=false;
              fx = i;
              fy = j;
           }
           
        }

       
        for(int x=1; x <= 9; x++) {
           
           if(setTileIfValid(i, j, x)) {
              
              // Log.d("SUDOKU: ", "set["+i+"]["+j+"] at value: "+x);
              
              if(solveSudoku(i+1, j, getActualPuzzle())) {
                 return true;
                 
              }
           }
        }
       
        // backtrack
        Log.d("SUDOKU: ", "***************** BACKTRACK *******************");
        backtrack++;
        setTile(i, j, 0);
        Log.d("SUDOKU: ", "*** setTile "+i+" "+j+" a 0 ***");
       
        if(i==fx && j==fy && !is_Solved()) {
           
           int value = getTile(fx, fy);
           
           
           if(setTileIfValid(fx, fy, value++)) {
              first=true;
              solveSudoku(fx, fy, getActualPuzzle());
           }
           
           
        }
     
       return false;
   }


Can you help me please?
Back to top
View user's profile Send private message
Lunatic

Joined: 11 Mar 2007
Posts: 166
:
Location: Ghent - Belgium

Items
PostPosted: Tue Jun 02, 2009 6:51 pm    Post subject: Reply with quote

Assuming the use of two seperated arrays, one with the sudoku clues (Example: Sudoku[row][col]) and a second one for the solving progress (Example: Solution[row][col]) starting as a copy of Sudoku[row][col] and who will eventually hold the solution, and assuming that changes only occur in the second array, this is how it might work...

Code:
private boolean solveSudoku(int i, int j, int[] p)
{
// limits
if (i == 9)
   {
   i = 0;
   if (++j == 9) return true;
   }

// skip clues
while (getTile(i, j) != 0)
   {
   i++;
   // limits
   if (i == 9)
      {
      i = 0;
      if (++j == 9) return true;
      }
   }

for(int x=1; x <= 9; x++)
   {
   if(setTileIfValid(i, j, x))
      {
      Log.d("SUDOKU: ", "set["+i+"]["+j+"] at value: "+x);
      if(solveSudoku(i+1, j, getActualPuzzle()))
         {
         return true;
         }
      else
         {
         // backtrack
         Log.d("SUDOKU: ", "***************** BACKTRACK *******************");
         setTile(i, j, 0);
         Log.d("SUDOKU: ", "*** setTile "+i+" "+j+" a 0 ***");
         }
      }
   }
       
return false;
}

GetTile must return the value from Sudoku[row][col]
SetTile must set the value at Solution[row][col]
SetTileIfValid must set the value at Solution[row][col] if value is valid for the adressed cell and return true, or else return false

Don't know why you pass the reference of an array you don't use within the scope of SolveSudoku...
_________________
Marc
~~~<><~~~<><~~~<><~~~<><~~~
Back to top
View user's profile Send private message Send e-mail Visit poster's website
Display posts from previous:   
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Programming sudoku All times are GMT
Page 1 of 1

 
Jump to:  
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
Sudoku Programmers topic RSS feed 


Powered by phpBB © 2001, 2005 phpBB Group

Igloo Theme Version 1.0 :: Created By: Andrew Charron