Jump to content
  • Advertisement
Sign in to follow this  
DaveA

sudoku

This topic is 4819 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

hey im working on a sudoku algorithm but keep finding i need to do another check and then another check etc and finding more problems Does anyone have any code or know of a generic algorithm? Cheers Dave

Share this post


Link to post
Share on other sites
Advertisement
Quote:
Original post by DaveA
Does anyone have any code or know of a generic algorithm?
A backtracking solution to the problem is straightforward. Visit the empty squares in order, assigning new numbers to them (in order 1 through 9). After having set a number, check if the puzzle is in an illegal state. If it is not, continue to the next empty square, setting a new tentative number there.

If the puzzle is in an illegal state, increment the last number you set, and try again. If the last number you set was 9, you have to go _back_ (backtrack) to the previous square and try a new number there before you can continue again. Rinse and repeat.

If you're not familiar with backtracking, you can read about it here:
http://en.wikipedia.org/wiki/Backtracking

In order to speed up the process you want to additionally have a system that will exclude certain numbers from being tested at given squares. For example, if you have the number 5 in a square somewhere, then for the other squares in the horizontal and verical rows containing the 5 mark those squares as not being able to contain 5. Same for each 3x3 grid of numbers. This process is called 'pruning' (of the search space).

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!