[Maths-Education] Combinatorics and Sudoku

[Alan Rogerson]

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