# 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.

## 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 on other sites
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 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 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 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 on other sites
So you mean hashing the grid values?

##### Share on other sites
Quote:
 Original post by SamLowryIt 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 on other sites
Quote:
Original post by prinzessin
Quote:
 Original post by SamLowryIt 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 on other sites
How does one store a set of 30-character strings while detecting duplicates? Use a trie. O(1) search, O(1) insert.

##### Share on other sites
No problem :) Thanks I will give this a try and let you know how it works out :)

1. 1
2. 2
Rutin
20
3. 3
JoeJ
17
4. 4
5. 5

• 37
• 23
• 13
• 13
• 17
• ### Forum Statistics

• Total Topics
631704
• Total Posts
3001822
×