17 givens... How???

The Ostrich · Posted: Sun Apr 23, 2006 1:10 am Post subject: 17 givens... How???

Hi,

It seems to me that among the corpus of possible sudokus, minimal sudokus with only 17 givens are, for want of a better word, INCREDIBLY rare. I mean, earlier this evening I generated 360,000 random sudokus. Not a one of them had 17 givens. So I have to ask, how does one go about generating them?

Some ideas that spring to mind:

1) Local search - remove one number from a valid sudoku, and replace it with any other number from the solution that leaves a valid sudoku. Then try removing each given in turn. If you don't find one that can be removed, repeat... You can do a complete 1-neighbourhood search, and then extend this to the 2-neighbourhood etc...

2) Identification of critical cells. Perhaps some cells are more important than others for a particular solution grid with few givens. Find cells which are shared between multiple solutions of an indeterminate grid, then DON'T use them as givens.

3) Solution space search. Add 17 random givens to your grid. Estimate the number of solutions, and remove each given in turn. Kill the given which leads to the smallest increase in the number of solutions when removed. Add an new random given and continue...

I'd like to know if any of these ideas have been tested, or perhaps if anyone knows Gordon Royle's secret... I haven't found any answers as to how to tackle this problem from Google (my number one stop), so I'm just putting this out there.

I have to say that my main interest in this is to find a way of reliably, in a single pass, producing a sudoku with a reasonably small number of givens (e.g. 22, as seems to be the average with the Times puzzles - even with 4-way reflected symmetry). But the problem of generating minimals seems interesting in its own right, of course...

Ruud, have you got any info on this one?

Ruud · Site Admin

Hi,

I have generated 1.3 million sudokus and 3 puzzles with 19 clues are the best I found. Gordon does not have any secrets. He started collecting 17's from various sources, and by adding/removing clues he found more 17 and 18 clue puzzles. He not only has more than 30,000 17's, he also has millions of 18's.

A more scientific approach can be found if you read this post by coloin on the player's forum: http://www.sudoku.com/forums/viewtopic.php?p=26335#26335. Go hunt the unavoidable sets and cover them with the minimal set of clues you can find.

To hunt for 17's forget random generation. they are simply too rare.

Ruud.

fermat · Posted: Sun Apr 23, 2006 10:29 pm Post subject:

The Ostrich

Basically, the result is:

Puzzle generation to a difficulty is now about 20 times faster, or I can
get rid of about 2 givens at no extra cost.

1-Neighbourhood search can't be used for generating 17 givens. It
doesn't beat 20 in a reasonable time.

-----------------------------------------------

I pretty much figured that random generation wouldn't do it. In fact, that was the gist of my post. I was rather interested in knowing if anyone HAS done it, or what people might know about algorithms for doing it.

I have implemented 1-neighbourhood search as a part of my DLX generator now.

The algorithm works by tentatively adding a symmetry group (either a single cell if no symmetry, or 2 cells if rotational etc...). It then removes every other symmetry group, and sees if the puzzle can be made smaller than its initial size. If it can, then it accepts the changes; if not, it moves on to the next symmetry group and tentatively adds it. So it does N times the work of puzzle generation.

The result of all this is an increase by upwards of 300% the frequency of 20 and sub-20 puzzles that are generated in a given time. Basically, I can get a 20 given "Easy" rated puzzle in under 15 seconds. However, 19 and below are still incredibly rare, so I don't think this is the technique either.

Amusingly, though, the 1-neighbourhood search has fixed my initial problem of not being able to generate high-quality (i.e. few givens) puzzles fast enough. Although it is a dog of an algorithm, that without symmetry takes 30 times longer than random puzzle generation, it turns out that the difficulty categorisation before 1-neighbourhood search is almost never changed by the search. Because most of the algorithm's rejects are on the basis of difficulty, this means that when it has a puzzle of the appropriate difficulty, only then does it reduce the givens.

So it doesn't actually cost more than a few milliseconds of running time to reduce the number of givens by 2 in my resultant puzzles (or speed the program up by a factor of 20).

Papy · Posted: Tue Aug 15, 2006 12:43 pm Post subject: 17 ??? 16 ???

Sorry if my english is not good but I'm french
I don't want to attaq every one so if my words are bad for any one I'm sorry.

The problem of the number of Reveled is not wath you say.
Every Latin square can have million (yes millions) of 17 sudoko
The number of reveled doesn't depends from the original grid!
If you want I can give you 5 millions of 17 sudoku!!!(50 if you want!)

Why 17 grids are rare? Only because generators uses , in general, random functions to choose and after try to solve the grid
But 17 reveled combinations are more than 30 reveled

Of course every one try to optimize the andom generation but is's not easy

Choose 17 into 81 or 30 into 81 is very different!

If you use a mathematic logic to generate revels no problem with the number. The computer can generate millions in aminute.

It's more hard to determine quickly if a grid have a unic solution
starting with the grid Not control it during the generation after!

Jérôme Shocked