Re: Uniquely identifying Sudoku grids


"Gerard Schildberger" <Gerard46@xxxxxxx> wrote in message news:J76dnUyPX4_AWLPZRVn-uw@xxxxxxxxxxxx
| Oliver Wong wrote:
|> Another way to look at it: Your encoding system should be able to
|> uniquely specify every possible sudoku. So just take the number of sudokus
|> in existence, and take its logarithm base 2, and that's how many bits
|> you'd need to uniquely identify each one. Alternatively, take its
|> logarithm base 10, and that's how many digits you'd need to uniquely
|> identify each one.

|From wikipedia: http://en.wikipedia.org/wiki/Sudoku
|<quote>
|the number of valid Sudoku solution grids for the standard 9×9 grid was
|calculated by Bertram Felgenhauer in 2005 to be
|6,670,903,752,021,072,936,960
|</quote>
|
|So you'd need 22 digits to uniquely specify a sudoku puzzle.

Ok, so what would the 6,670,000,000,000,000,000,960th puzzle
look like?

..71.....4
...3..2.8.
89..7..56
...9237.68
...5...4..
38.4159..
14..9..25
..6.7..8..
5.....61.

, obviously. ;)


An easier way to look at this question is, given a standard
deck of 52 cards +2 jokers, how many poker hands (5 cards) are
possible? 54 x 53 x 52 x 51 x 50
(which equals 379,501,200), so it would take 9 digits to specify
any particular poker hand.... so hand # 379,000,001 is ... ?

It would, of course, be just easier to specify something like
6d,Ah,Js,2c,2h ... or some such encoding that can be easily
transcribed to those cards. That way, no table is needed to
translate the 379,000,001st hand to a particular poker hand.

That's an "easier to encode/decode" encoding, but it's not nescessarily the shortest encoding, where I'm defining shortest encoding as the length of the string you get by concatenating all legal strings within that encoding. But it's all moot, as I later realized that this wasn't what the OP was asking for anyway.


Similarly, the same for a sudoku puzzle, one only needs to
specify the minimum number of cells (assuming the sudoku
puzzle has a unique solution --- if not, then more cells would
need to be specified). ________________________________Gerard S.

Yes, that's closer to what the OP was asking for than the answer I provided.

- Oliver

.

Relevant Pages

  • Re: Data source not "sticking"
    ... First, as far as I am aware, when the data source is a text file and you ... have to specify the encoding, Word does not store the information about the ... encoding when it saves the mail merge main document. ... XML format (i.e. not the sort of simple XML format doucment you might ...
    (microsoft.public.word.docmanagement)
  • Re: =?UTF-8?B?77u/V2hlbg==?= X.ZIP downLoads a post or eMail, Windows-1252 is the default.
    ... It's very common for a newsReader to specify ISO-8859-1 ... doesn't fit into the ISO standards. ... | When a user agent would otherwise use an encoding given in the ... mis-identified as using ISO standard character encodings. ...
    (news.software.readers)
  • Re: Print Spanish characters in Perl?
    ... and ensure that your file is saved in the UTF-8 format. ... encoding then your display device expects. ... forgetting to specify UTF-8 as charset. ... To avoid this kind of problem, make sure that all the characters are ...
    (comp.lang.perl.misc)
  • Re: Why doesnt strrstr() exist?
    ... > Unicode is a character set, not an encoding. ... > AFAIK the language doesn't specify how to deal with Unicode ... I am not *that* familliar with Java. ...
    (comp.lang.c)
  • Re: Uniquely identifying Sudoku grids
    ... |> Another way to look at it: Your encoding system should be able to ... |> uniquely specify every possible sudoku. ... |So you'd need 22 digits to uniquely specify a sudoku puzzle. ... Similarly, the same for a sudoku puzzle, one only needs to ...
    (rec.puzzles)
Loading