The Star about Sudoku

Advanced methods and approaches for solving Sudoku puzzles

The Star about Sudoku

Postby Mada » Fri Jun 08, 2007 11:41 am

Please take a look here
http://www.thestar.com/article/222620
Mada
Mada
 
Posts: 5
Joined: 08 January 2007

Postby ravel » Fri Jun 08, 2007 2:36 pm

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

Postby m_b_metcalf » Fri Jun 08, 2007 2:47 pm

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
User avatar
m_b_metcalf
2017 Supporter
 
Posts: 8777
Joined: 15 May 2006
Location: Berlin

Postby ravel » Fri Jun 08, 2007 4:39 pm

Ah, you are right, thats great:)

But what about this ?
... 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

Postby ravel » Fri Jun 08, 2007 10:09 pm

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

Postby udosuk » Sat Jun 09, 2007 4:05 am

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

Postby ravel » Sat Jun 09, 2007 12:52 pm

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


Return to Advanced solving techniques