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   

Solving example

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

Joined: 13 Jun 2005
Posts: 31
:

Items
PostPosted: Mon Jun 13, 2005 5:01 am    Post subject: Solving example Reply with quote

Just putting in a solving example for those who want to see how to solve sudokus by brute force. (Probably only for those people randomly dropping by this forum. Not ment for the members here who can do this by themselves Smile This is an implementation in java but I'm sure everyone will understand it. I'm only posting the solving logic. The 2 function FindNextSpot() and FindPossibleNumbers() are the ones you need to code yourself.

If you want you can first do some logic solving to reduce the grid. And then you can put a lot of logic into FindNextSpot() and FindPossibleNumbers() to reduce the final brute force.

Chosing FindNextSpot() wisely you'll get a fast solving brute force even without using logic. The max number of iterations I've seen so far to solve a sudoku is less than 1000 using a medium smart FindNextSpot() function.

Code:

   protected boolean Solve() {
      // Trying to keep the created variables to a minimium for speed
                // It's recursive so the less we have the faster it will be
      int[] coord;     // The cell we will be investigating
      int[] numbers;   // The legal numbers for the cell

      // Find the next empty cell
      coord = FindNextSpot();
      
      // No more cells, it must be a solution
      if (coord[0] == -1) {
         return true;
      }

      // Get the legal numbers for our new empty cell
      numbers = FindPossibleNumbers(coord);
      
      // And now we check all the numbers for the cell
      for (int number=0;number<numbers.length;number++) {
         // Set the cell to the number
         grid[coord[X]][coord[Y]] = numbers[number];
         // Counting iterations to find the solution
         // Can be removed for faster solutiontime
         solvecount++;
         // Call it recursively to check next number
         if (Solve()) {
            // We found a solution. Recursively return true
            return true;
         }
      }
      // The number wasn't correct. Set it to 0 again
      grid[coord[X]][coord[Y]] = 0;
      // Couldn't find any solutions for the legal numbers for this cell
      // in this recursion
      return false;   
   }


So there you go. Now go out at create your own sudoku solver.
Back to top
View user's profile Send private message
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