Mark Brader wrote some weeks ago:
Some puzzles in the latest Games Magazine are based on a 9x9 array of >digits chosen from 1 to 9, with the following properties:
* each row contains each digit exactly once
* each column contains each digit exactly once
* if the 9x9 array is divided in thirds, forming a 3x3 array of
3x3 subarrays, then each subarray contains each digit exactly once
For example:
3 8 4 1 2 6 5 7 9
9 2 6 5 7 3 4 1 8
1 5 7 8 9 4 6 3 2
2 6 3 9 8 7 1 4 5
5 7 1 4 6 2 8 9 3
8 4 9 3 5 1 7 2 6
4 9 8 7 3 5 2 6 1these are called "number place puzzles" .
7 3 2 6 1 8 9 5 4
6 1 5 2 4 9 3 8 7
They are popular in Japan where they are called "Sudoku" .
I have three questions that people might be interested in answering.
I don't know the answers myself.
[1] How many distinct arrays are there that meet the conditions? 6670903752021072936960 = 9!*2^13*3^4*27704267971 = 6.67e21about 2.8e9 , I don't know exactly.
[2] How many *essentially* distinct arrays -- as defined below --
are there that meet the conditions?
[3] Does each of the essentially distinct arrays in [2] contribute thenot. Most of them contribute 46656*2*2*6*6*9! , but not all.
same number of distinct arrays to the total in [1], or not?
Arrays are essentially distinct if it is NOT possible to generate one from >the other by a reasonably simple transformation -- either geometricalI define two solved number place puzzles as equivalent , iff one can be transformed into the other by a finite sequence of transformations ,
(such as rotating the whole array) or numerical (such as complementing
the values in the whole array) -- or a combination of these.
--
Mark Brader | "...given time, a generally accepted solution to
which include :
permuting the three rows 1,2,3
permuting the three rows 4,5,6
permuting the three rows 7,8,9
permuting the three 3*9-blocks consisting of rows 1+2+3,4+5+6,7+8+9
mirroring along the main diagonal
permuting the 9 symbols
--qscgz
Sysop: | Keyop |
---|---|
Location: | Huddersfield, West Yorkshire, UK |
Users: | 325 |
Nodes: | 16 (2 / 14) |
Uptime: | 64:19:29 |
Calls: | 7,124 |
Calls today: | 2 |
Files: | 12,524 |
Messages: | 5,521,185 |