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 ?

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 ??

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)

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.

So you mean hashing the grid values?

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?

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 :))

No problem :) Thanks I will give this a try and let you know how it works out :)