Advanced methods and approaches for solving Sudoku puzzles

http://www.thestar.com/article/222620

Posts: 5
Joined: 08 January 2007

Is it possible to get a link to this paper published by the American Mathematical Society ?

Sometimes i am getting angry, when people pretend to have found interesting new results, but i did not read here something but long known or trivial stuff.

Just one comment to this statement:
But the professors are still stumped by some Sudoku characteristics, like the absolute minimum number of initial numbers that will produce a puzzle with only one solution. It could be 16 or even smaller, says Murty, and computers simply aren't up to the job of running the necessary calculation.
We all know here, that it is most unprobable, that there is a 16 clue. But i bet those people would not even be capable to prove, that a 12 clue is not possible.
ravel

Posts: 998
Joined: 21 February 2006

ravel wrote:We all know here, that it is most unprobable, that there is a 16 clue. But I bet those people would not even be capable to prove, that a 12 clue is not possible.

But wait, they've proven the astounding result that you need at least eight distinct values in the clues. That's really impressive for a maths professor

Regards,

Mike Metcalf

m_b_metcalf
2017 Supporter

Posts: 9463
Joined: 15 May 2006
Location: Berlin

Ah, you are right, thats great

... and puzzles with as many as 29 starting entries can still have more than one correct solution.
Would say 77 ....

Or this one:
And there are more than enough squares to feed the obsession: the researchers say there are 5,472,730,538 different and valid Sudoku games.
There are about 10^26 different and valid (unique) and minimal Sudoku games. 5.47..*10^9 is the number of non equivalent sudoku grids (solutions) - and it was not found with graph theory methods (rather combinational theory).
ravel

Posts: 998
Joined: 21 February 2006

Ok, i have read the paper now, i found it at the end of this description, which i also would call pure promotion raising wrong expectations.

Theorems 1 (the number of solutions is a polynomial) and 6 (an upper bound for the number of grids of nxn sudokus) are interesting for mathematicians, but concerning 9x9 sudokus there is nothing new (some things are trivial for members of this forum).
ravel

Posts: 998
Joined: 21 February 2006

ravel wrote:But i bet those people would not even be capable to prove, that a 12 clue is not possible.

I think I've read an elegant proof (impossibility of 12-clue puzzles) some time ago in this forum, but I can't find it now. Could you provide a link please? Thanks!
udosuk

Posts: 2698
Joined: 17 July 2005

AFAIK it is not even proved, that an 11 clue with one solution is not possible ( )
[Edit:]I did some search now here, but i could not even find a complete proof for 9 clues. Here is, where one was tried (but not finished). And there was this red herring by the famous DrZ, who presented a proof for Minimum Clue >= 17. I dont remember something later (since i joined this forum).

Another question related to the statement above, that a puzzle with 29 givens can still have more than one solution (of course you can remove an unavoidable set/deadly pattern of size 4 from a grid and get a puzzle with 77 givens and 2 solutions):
When we say that a multi solution puzzle is minimal, if the removal of each given leads to a puzzle with more solutions - what is the maximum number of clues for minimal puzzles with multiple solutions ?
I think to remember, that this question already was discussed (long time ago, when tso still posted here), but i also cant find it.
ravel

Posts: 998
Joined: 21 February 2006