Sudoku Programmers Forum Index

 
 FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister   ProfileProfile   Log inLog in          Games  Calendar

Log in to check your private messagesLog in to check your private messages   

basic beginner's question

 
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Setting sudoku
View previous topic :: View next topic  
Author Message
mistermac

Joined: 03 May 2008
Posts: 10
:

Items
PostPosted: Sat May 03, 2008 11:52 am    Post subject: basic beginner's question Reply with quote

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
View user's profile Send private message
Adak

Joined: 27 Feb 2008
Posts: 87
:

Items
PostPosted: Sun May 04, 2008 7:33 am    Post subject: Re: basic beginner's question Reply with quote

No one has yet found a unique 16 given value, Sudoku puzzle. The reasons why:

1) There may be none to find! Smile

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 non-isomorphically 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
View user's profile Send private message
coloin

Joined: 05 May 2005
Posts: 97
:

Items
PostPosted: Tue May 06, 2008 5:20 pm    Post subject: Reply with quote

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 17-puzzles - we will never know that we have got them all. Generating 17-puzzles is no mean feat. Generating a new 17-puzzle now is an exceptional feat.

Finding a 17-puzzle from a complete grid [known to have a 17-puzzle] is also challenging.

All the 17-puzzles found have been checked for non-minimality. [ie a 16-puzzle within]

Checker program can check an 81-clue grid for a 16-puzzle, or a 17-puzzle - 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 17-puzzle collection share a set of 12 equivalent clues with at least one other 17-puzzle. It is feasible to do a 15-plus-2 complete search [it has been probably been achieved] but a complete 14-plus-3 is beyond our capabilities at present.

C
Back to top
View user's profile Send private message
mistermac

Joined: 03 May 2008
Posts: 10
:

Items
PostPosted: Fri May 09, 2008 9:03 am    Post subject: Reply with quote

Quote:
Finding a 17-puzzle from a complete grid [known to have a 17-puzzle] 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
View user's profile Send private message
mistermac

Joined: 03 May 2008
Posts: 10
:

Items
PostPosted: Fri May 09, 2008 9:05 am    Post subject: Reply with quote

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
View user's profile Send private message
coloin

Joined: 05 May 2005
Posts: 97
:

Items
PostPosted: Fri May 09, 2008 2:29 pm    Post subject: Reply with quote

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 16-core supercomputors working over a few weeks !

C
Back to top
View user's profile Send private message
mistermac

Joined: 03 May 2008
Posts: 10
:

Items
PostPosted: Mon May 12, 2008 3:32 am    Post subject: Reply with quote

Quote:
I believe he employed spare IBM 16-core 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
View user's profile Send private message
Display posts from previous:   
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Setting sudoku All times are GMT
Page 1 of 1

 
Jump to:  
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
Sudoku Programmers topic RSS feed 


Powered by phpBB © 2001, 2005 phpBB Group

Igloo Theme Version 1.0 :: Created By: Andrew Charron