
View previous topic :: View next topic 
Author 
Message 
 mistermac
 Joined: 03 May 2008  Posts: 10  :   Items 

Posted: Sat May 03, 2008 11:52 am Post subject: basic beginner's question 


I posted at length in another thread and was advised to start a new one. The original is one down in the Forum section if you are interested.
Has anyone found a viable 16 clue Standard Sudoku?
If not, why not?
Is it too hard, or are the main people interested not gun Mathematicians?
No reflections on all of you, perhaps it is too hard to solve easily even for a maths wizard, which I am not.
The "canonical" idea I read about presumably means basically a puzzle with 123,456,789 as the first three rows in the left top square, which sort of standardises the thing to some extent.
I know you can swap to produce certain rows and columns without upsetting the basic pattern.
How much definition do you need before rotation does not become a problem?
Perhaps some kind soul will point me in the direction of the basic theory, which seems to me to be a part of group theory.
I would think that Rubik's Cube has similar aspects to sudoku.
Thanks for the welcome. Hope I will be of some use, and will learn a bit.
Best! 

Back to top 


 Adak
 Joined: 27 Feb 2008  Posts: 87  :   Items 

Posted: Sun May 04, 2008 7:33 am Post subject: Re: basic beginner's question 


No one has yet found a unique 16 given value, Sudoku puzzle. The reasons why:
1) There may be none to find!
2) It's a hugely computationally intensive task to create all the possible 16's grids, and from that insanely huge number of grids, remove the large number of nonisomorphically unique grids (all the rotations, etc.)
And then check all the grids that remain, to see if any of them have a unique solution. There is a way to canonicalize the entire grid set, reducing it's size, immensely. I'm not sure why this hasn't been done for the 16's.
Gordon, gsf, and several others, are quite capable, but the main focus of their work has been in finding the 17's, not the 16's. They are doing some searching in the 16's area, however.
You'd enjoy reading the Sudoku papers of Frazier Jarvis  head of the pure mathematics dept of a uni in Sheffield, UK. Give him a google, and also "canonical sudoku".
Fun reading. 

Back to top 


 coloin
 Joined: 05 May 2005  Posts: 97  :   Items 

Posted: Tue May 06, 2008 5:20 pm Post subject: 


many of the answers you may find "Quest for THE 16 GIVEN SUDOKU"
I think now even Adak realizes that putting all the ways to insert 16 clues isnt a feasible method.
But neither is trying to generate all the 17puzzles  we will never know that we have got them all. Generating 17puzzles is no mean feat. Generating a new 17puzzle now is an exceptional feat.
Finding a 17puzzle from a complete grid [known to have a 17puzzle] is also challenging.
All the 17puzzles found have been checked for nonminimality. [ie a 16puzzle within]
Checker program can check an 81clue grid for a 16puzzle, or a 17puzzle  but this takes even longer.
gsf can generate all the essentially different grids [5*10^9] There are possibly ~10^14 different minimal puzzles per grid.
Any transformation of row swapping or relabelling or reflection  keeps the puzzle the same essentially  there are ~ 10^12 isomorphs per puzzle.
Of note  all the puzzles in the 17puzzle collection share a set of 12 equivalent clues with at least one other 17puzzle. It is feasible to do a 15plus2 complete search [it has been probably been achieved] but a complete 14plus3 is beyond our capabilities at present.
C 

Back to top 


 mistermac
 Joined: 03 May 2008  Posts: 10  :   Items 

Posted: Fri May 09, 2008 9:03 am Post subject: 


Quote:  Finding a 17puzzle from a complete grid [known to have a 17puzzle] is also challenging. 
This raises an interesting question in my mind.
Given all valid completed puzzles, what is the largest maximum of seeds ever found to be just sufficient to solve the puzzle? 

Back to top 


 mistermac
 Joined: 03 May 2008  Posts: 10  :   Items 

Posted: Fri May 09, 2008 9:05 am Post subject: 


Quote:  gsf can generate all the essentially different grids 
Are some of these "harder" than others?
Does "essentially different" imply a "template" which can only be rotated, put in a mirror, or have the numbers swapped, or subject to the usual swapping devices for squares, rows and columns? 

Back to top 


 coloin
 Joined: 05 May 2005  Posts: 97  :   Items 

Posted: Fri May 09, 2008 2:29 pm Post subject: 


mistermac wrote:  Given all valid completed puzzles, what is the largest maximum of seeds ever found to be just sufficient to solve the puzzle? 
It was 35 for a long time, untill Havard with progressive exponentially increasing effort he found 2 minimal 39s.
Havards 39s
It was a massive effort to find a 38.
Only Havard knows how hard he really tried with the 39s.
I believe he employed spare IBM 16core supercomputors working over a few weeks !
C 

Back to top 


 mistermac
 Joined: 03 May 2008  Posts: 10  :   Items 

Posted: Mon May 12, 2008 3:32 am Post subject: 


Quote:  I believe he employed spare IBM 16core supercomputors working over a few weeks 
That is rivalling the kind of time devoted to cracking large, and I mean large, prime numbers.
A deterministic method for them, which most seem to agree is valid, indicates log of the log of number size as being the time required to solve
them.
I did not realise until i joined about a week ago just how complex Sudokus are.
Thanks to all, esp. C, for the answers so far.
Has anyone tried to popularise this subject.
Dr. Knott, with his Fibonacci Site, and Martin Gardner of Scientific American did much to popularise various problems like Sudokus, and complex mathematics.
Sudoku, easy to define, hard to solve! 

Back to top 




You cannot post new topics in this forum You cannot reply to topics in this forum You cannot edit your posts in this forum You cannot delete your posts in this forum You cannot vote in polls in this forum

Powered by phpBB © 2001, 2005 phpBB Group
Igloo Theme Version 1.0 :: Created By: Andrew Charron
