Message Boards Message Boards

0
|
7171 Views
|
3 Replies
|
3 Total Likes
View groups...
Share
Share this post:

Combinatorial Math problem (sudoku)

Posted 10 years ago

In Sudoku, there is an NxN matrix of integers from one to N. This has the property that no column or row has an integer repeated.

question: How many UNIQUE puzzles exist?

Some analysis:

The TOP row has N! has possible permutations.

For a 5X5 matrix, there are 44 second rows for each of the 120 permutations of the top row.

I did an exhaustive count of 5x5 puzzles, the total is 262180. This number is factorable, but the factors are not obvious. For each Row 2, you can either 12 or 13 row 3's, And for each row 3, you can get either 2 or 4 row 4's. Row 4 gives EXACTLY one choice for row 5.

It is tempting to say " It is a combination of ALL permutations of rows and columns," but this answer (120*120 = 14400 ) is not correct.

I am offering a cash prize for the correct formula. Maybe you know a math whiz that can provide it?

POSTED BY: William Sinclair
3 Replies

It's not clear (at least to me) whether you're asking the number of unique puzzles and the number of unique solutions to puzzles.

POSTED BY: Frank Kampas
Posted 10 years ago

You might read about Latin Squares: http://en.wikipedia.org/wiki/Latin_square

POSTED BY: Jim Baldwin

In Sudoku, there is an NxN matrix of integers from one to N. This has the property that no column or row has an integer repeated.

This description ignores the block structure of sudoku. As far as the sudoku is concerned the question generated a considerable body of literature, see The Math Behind Sudoku.

Your question sets out to count another set. Do you consider matrices m1 and m2 which agree after m2 was transformed by one of the following operations

  • transposition
  • transposition on the anti-diagonal
  • rotation bei a multiple of Pi/4 (but not by 2 Pi)

as equivalent?

POSTED BY: Udo Krause
Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.
Reply Preview
Attachments
Remove
or Discard

Group Abstract Group Abstract