Re: Sudoku question

"Randy Poe" <poespam-trap@xxxxxxxxx> wrote in message
news:1152723428.457615.79780@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx

Frank Palmer wrote:
In the June Scientific American, there was an article on Sudoku. The
puzzle has attracted me for some time. One statement in the article
puzzled me. The author, Jean-Paul DeLahaye, identifies one full grid as
"strangely familiar." He tells that there are 29 clue sets of 17 digits
each. Anyone of those can be solved.

The problem is that if a particular grid can be solved by a particular
clue set, than so can a remarkable number of other grids. In the first
place, onoe can replace the integers by any other ordering of integers,
that's 9! [factorial] grids.

Then, instead of suc algebraic transforms, one can look at geometrical
ones. Call a row of nine digits a "minor row" and a row of three boxes
(what the author calls "smaller squares") a "major row." Then any
exchange of two minor rows within a particular major row will be a
solution (if you start with a solution); so will an exchange of major
rows. That gives 6^4 [exponentiation] transforms. And a sufficient clue
set is transformed into another one. Moreover, the transform is
identified by what happens to the 9s (or any other particular digit).

So, there are 6^4*8! grids which each has 29 inequivalent sufficient
clue sets.

Clearly, the argument I gave for rows can be given word-for-word for
columns. But I can't see whether this generates any more grids with
this particular quality. In particular, any exchange of rows can be
matched by an exchange of columns which puts all the 9s in the same
positions. Is that possibly followed by an algebraci transform which
yields the same results?

I think your question is related to one I've wondered about
before Sudoku became so universal, having to do with
latin squares. A latin square is one in which every digit
occurs exactly once in each row and column. There is no
"small box" requirement, so obviously completed Sudokus
are special cases of latin squares.

The number of unique latin squares of size n is known
(for many n? all n?). "Unique" means it can't be obtained
from another square by exchanging rows, exchanging
columns, rotating, or reordering the digits. I always
wondered how they got the count right and made sure
they were only counting unique squares.

- Randy



Inequivalent sudokus:
http://www.research.att.com/~njas/sequences/A109741


Inequivalent latin squares:
http://www.research.att.com/~njas/sequences/A040082


.

Relevant Pages

  • Sudoku question
    ... He tells that there are 29 clue sets of 17 digits ... than so can a remarkable number of other grids. ... Then, instead of suc algebraic transforms, one can look at geometrical ... solution; so will an exchange of major ...
    (sci.math)
  • Re: Sudoku question
    ... than so can a remarkable number of other grids. ... Then, instead of suc algebraic transforms, one can look at geometrical ... solution; so will an exchange of major ... are special cases of latin squares. ...
    (sci.math)
  • Re: Visualization of Fourier transform
    ... of their 2D Fourier transforms on the other. ... It seems the patterns were quite small in real life, ... dots close together, 2 dots far apart, grids of dots, grids of dots ...
    (sci.optics)