Jump to content
  • Advertisement
Sign in to follow this  
prinzessin

Suduko Pattern : magical id formula ?

This topic is 3624 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

Hello Everyone, I have recently implemented a Sudoku generator and solver. My question is: Is there some kind of magical number that uniquley represents a solved Sudoku-pattern? a mathematical formula that represents a unique id of the puzzle. Here is why: my program generates n different puzzles and solutions... i would like to compare these puzzles to check if the same one was generated twice (to eliminate it) without actually having to compare the values of the array one by one? In other words is there a number that identifies a sudoku ?

Share this post


Link to post
Share on other sites
Advertisement
Compare the grids: a grid is only 81 digits long, which (when you put two digits in every character) can easily fit in about 30 characters. Comparing 30 characters for equality is extremely fast, given that the probability of stopping after the first character is higher than 99%!

Share this post


Link to post
Share on other sites
Thanks but I'm afraid I cant do that. I am generating about 10,0000 text files each containing the puzzle followed by the solution.
The puzzle is identified by the file name (from 1 to 10,0000) and it is this number that i store in my database.
The idea was to add each puzzle's magic identifier (if it exists) to a hash set and therefore make duplication of puzzles impossible.

i cant compare the grids : what would I do ? Compare each grid with all the existing ones ??

Share this post


Link to post
Share on other sites
you can do something simple like, a godel numbering type trick (raise the primes to the appropriate powers and multiply)

but interestingly it might be tough if you really want the lowest entropy system. the minimum amount of information should be stored. so you might need to know the maximum amount of numbers that can be taken off the puzzle so that it is still solvable into only one final pattern. but then it might turn out that those numbers are related in yet another way outside the bounds of sodoku puzzle rules.

i dont know.. there is definitly easy ways to hash it so that you dont get the same puzzle twice, but now you have me curious about how much info is actually stored in sodokus... i wrote a generator for the mma math modeling competition and haven't touched soduku since (3 days straight of work)

Share this post


Link to post
Share on other sites
It is certainly possible to associate a unique natural number with each sudoku puzzle (as the number of sudoku puzzles is finite), but converting such an ID to puzzle or vice versa is probably nontrivial.

If your only concern is avoiding duplicates, you could get away with just using hashes. If the hashes are different, it is certain the puzzles are different. However, if the hashes are equal, the puzzles might be equal, but that doesn't really cause trouble: if they have the same hash, you can just assume they're the same puzzle, throw one away and generate a replacement. So, it is a conservative approach in the sense that you'll be rejecting sets of 50 puzzles with no duplicates, but at least you're sure you'll have no 50 puzzles with duplicates.

As a hash number, you could use some operation on the upper row of the grid. If [n] stands for the position of n in the first row, i.e. a number from 0 to 8, then you could create a hash as sum([i+1] * i ^ 9, i=0..8) or something. The hash fits in a 32-bit integer (as it could not be larger than 9^9 = 387,420,489), and you'll have 362880 different possible hash values, which is certainly enough to guarantee that you won't end up in a long loop when trying to generate a new sudoku puzzle different from 8 others as there is only 2.76E-6 chance of a collision.

Share this post


Link to post
Share on other sites
Quote:
Original post by SamLowry
It is certainly possible to associate a unique ID with each sudoku puzzle, but converting such an ID to puzzle or vice versa is probably nontrivial.

I dont want to convert back and forth... I will actually store this number in a hash set. But how do I reach this number?

Share this post


Link to post
Share on other sites
Quote:
Original post by prinzessin
Quote:
Original post by SamLowry
It is certainly possible to associate a unique ID with each sudoku puzzle, but converting such an ID to puzzle or vice versa is probably nontrivial.

I dont want to convert back and forth... I will actually store this number in a hash set. But how do I reach this number?


I updated my previous post. (Sorry, I tend to do that a lot, because often posters as not as quick as you :))

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!