[Maths-Education] Combinatorics and Sudoku
Alan Rogerson
alan at rogerson.pol.pl
Mon Dec 8 13:33:45 GMT 2008
David H Kirshner wrote:
> At the risk of distracting us further, here's a psychological question
> related to Sudoku that has bugged me since I started doing the daily
> puzzle in the newspaper a couple of years ago. Somewhere I read a CLAIM
> to the effect that if you approach the puzzle effectively you'll NEVER
> have to make a blind guess. For any configuration, there is ALWAYS a
> valid reasoning path that enables you to definitively determine some
> number location.
Dear David,
The claim you mention is very interesting, if we forget about the very
simple sudoku versions and concentrate on the very hard (the most recent
we saw had NO numbers at all in it, but the clues were that the 9
sub-squares, each contained the digits 1-9 AND there were inequality
signs linking each small square to the next, quite fiendish even for
Margaret my wife and Sudoku addict. For the hardest levels she, and
everyone else we have seen, use a pencil to put in the invariable 2-3
possibilities once they have started on the grid, and then move along by
guess and check until they identify a definite digit, and then repeat
the guess and check. There may be super-experts who can logically work
out every digit one by one with no guessing, and maybe there is a neat
proof that they CAN, assuming obviously that each problem has a unique
solution (which I believe is one of the rules of the game, but see
later), but life is too short I suspect for the addicts and they all
seem to use guess and check, sometimes the whole grid can be covered
with such pencilling provisional possibilities until a definite digit
pops up! Experience in the puzzle obviously helps guide solvers as to
where to start and what to do.
The other thing is that the electronic versions Margaret has used also
have this facility for guess and check so you can change previous
selections, etc. My impression as a non-addict is that it would take
maybe a long time and certainly a very clever brain indeed to work out
the digits one by one without any guessing, unless we count some kind of
subconscious guessing and checking, otherwise what are we doing (?), if
it is possible to do the puzzle without guessing presumably *there is a
deterministic algorithm to do it*, and that would immediately ruin the
game and make it no fun at all?
Maybe someone like Neil can helpfully point us to the webpage with all
this worked out already to avoid any sleepless nights, of course the
obvious thing to do is Google sudoku but I am too afraid of being sucked
in to risk that...... wait...
I have just checked Wikapedia and they give a very full and
comprehensive discussion of the whole puzzle including this
"The maximum number of givens provided while still not rendering a
unique solution is four short of a full grid; if two instances of two
numbers each are missing and the cells they are to occupy form the
corners of an orthogonal rectangle, and exactly two of these cells are
within one region, there are two ways the numbers can be assigned. Since
this applies to Latin squares in general, most variants of /Sudoku/ have
the same maximum. The inverse problem---the fewest givens that render a
solution unique---is unsolved
<http://en.wikipedia.org/wiki/Unsolved_problems_in_mathematics>,
although the lowest number yet found for the standard variation without
a symmetry constraint is 17, a number of which have been found by
Japanese puzzle enthusiasts,^[11]
<http://en.wikipedia.org/wiki/Sudoku#cite_note-seventeen1-10> ^[12]
<http://en.wikipedia.org/wiki/Sudoku#cite_note-seventeen2-11> and 18
with the givens in rotationally symmetric cells. Over 47,000 examples of
Sudokus with 17 givens resulting in a unique solution are known."
I couldn't find any mention of a way to *solve* a grid by deterministic
logic or algorithm! But came across this frightening statistic related
to the Number of grids:
^
"The standard 3×3 calculation can be carried out in less than a second
on a PC. The 3×4 (= 4×3) problem is much harder and took 2568 hours to
solve, split over several computers. solution is
"81171437193104932746936103027318645818654720000 = c. 8.1×10^46"
Whow.
Best wishes
Alan
More information about the Maths-Education
mailing list