basic beginner's question

mistermac · 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!

Adak · 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! 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.

coloin · 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 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

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

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

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

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