dailysudoku.com

[alanr555]

I have been tackling puzzles for nearly ten years now. Throughout that
time I have had admiration for those who CREATE the puzzles.

Is there a forum that explains HOW to generate a puzzle?

Clearly 28 cells need to be filled.
Some cells could be inconsistent.
Many combinations would give non-unique solutions.
Puzzles would warrant different gradings for difficulty.

As the "best" puzzles are "hand made", how are such hands
trained to give the best results?

Does one need to be an expert solver in order to be competent
at generation? If so, I may as well quit now!

[Pat]

few puzzles are hand-made

we now have plenty of software
(much of it free)
to generate puzzles


rating them is a tougher question

try the other forum --
The New Sudoku Players' Forum

[nataraj]

How do I create Sudokus ?

The process of creating Sudokus is much closer to farming than it is to engineering.

How do you create a grade 1 / class A carrot?
Answer is: you don't.

All you do is prepare the ground, throw a few seeds in.
Monitor the growth of your crop, maybe water or prune some. Takes time and experience. Need a few tools, too.

Then harvest and take a good look at the carrots:
The bent and ugly ones still are very nutritious, but can only be sold as low quality.
The "good" ones go to the grocery stores and supermarkets.
The exceptionally beautiful ones are sold as "Premium" quality in special markets or stores.

There's your basic Sudoku "creation" process.

The soil, that's a set of programs that "let the sudoku grow": start with a few random clues, add more random clues if too many solutions, remove clues if no solution. The "random" clues are not random at all, they follow a strictly determined pseudo-random generation pattern derived from that one initial "seed" (and yes, it is really called a seed in programming jargon). This is the water and prune phase.

In order to find out if there is a solution, and - if yes - how many, we need a program that "knows" the rules of Sudoku puzzles (e.g. "only one of each number per row") and very efficiently applies these rules to test every possible position that is compatible with the randomly generated clues.

That is called a "brute force" approach, but works surprisingly well thanks to a paper published by Donald Knuth, a professor emeritus at Stanford, called "Dancing Links". Even my five year old business notebook, using javascript in the Safari browser, could find out one to a few hundred solutions to a given Sudoku in mere 3-5 milliseconds. And the algorithm is not hard to code, either.

No, I do not believe that there are ANY hand-crafted sudokus. I also do not believe that there are any hand-crafted carrots. It is so much easier to let them grow by themselves.

When the Sudoku stops growing (i.e. there is exactly one solution), the interesting part starts. Remember: look at the carrots and decide where they go: garbage dump or Premium store. This process is called "grading", or "rating".

Unfortunately, one cannot - by merely looking at a Sudoku - decide whether it is an "easy", "hard" or "impossible" one. Different people use different approaches. Myself, I use an approach that closely follows the way a real person solves a Sudoku: look at the grid, maybe add a little markup here and there, detect patterns like naked pairs or xy-wings. Easy puzzles use only very basic techniques, hard puzzles need a little more, like pairs, for example. Again, to each their own - what some people call advanced, others call intermediary.

Or "impossible": many puzzles, even if they have a garanteed unique solution, cannot be solved by "conventional means". And that is where I draw the line: if I need a computer to solve a Sudoku, why not apply the Dancing Links algorithm? Five milliseconds, far shorter than a heartbeat, and there you have it: the solution. Fun? Seriously, I throw away more puzzles because they are "too hard" than I publish as "very hard" or "advanced" taken together.

What is interesting in those "impossible" ones (at least for me) is how we could find a workable procedure to make a few more patterns available to the human Sudoku solver? There is a good example to illustrate the grading dilemma: the BUG+1 (2,3) ("Bivalue Universal Grave") pattern is usually regarded as rather advanced, although it is one of the easiest pattern to recognize, much easier than a humble XY-wing. Same for the UR (Unique rectangle) type 1. I use those simple URs for shortcuts before I even attempt to find a wing. Still, I do not (yet) dare to publish a puzzle as "very hard" if it needs a UR or BUG+1.

On to the final question: "Does one need to be an expert solver in order to be competent at generation?". Not necessarily. But you have to be a programmer or can afford to hire programmers/designers. It does not take a gourmet to grow carrots. But you must be able to work with the tools. And - it takes a lot of expertise to assess the quality of food or to decide which dishes to serve at different occasions.

And given the fact that MOST people only want the easiest of all Sudokus, the ones they can solve in 5 minutes on a subway train and then throw away, all the people who come looking for "good" puzzles on the internet already have very high expectations. It is for those people that I farm and grade my Sudokus.

Helmut

edit: Pat, I only realized this question was posted almost a year ago when I had already finished my answer. But thanks for bumping it

[alanr555]

Thank you , Nataraj, for this comprehensive response.
I like the analogy with the carrots. The concept of creating them all
and then deciding which to keep for which purpose was one of my
thoughts - more mundane than arcane - and I am pleased to have
received confirmation that it is the basic approach.

Are there any statistics on how many of say 1000 generated fall
into which categories?

[nataraj]

[nataraj]

Frequencies of graded Sudokus in test run

The number of sudokus requested was:
- 61 each for Easy, Mild, Hard
- 44 Very Hard
- 17 Advanced

The "Farm" creates at least 50% more than what is needed, so it stopped when 67 Very Hard were generated.

This is the result:

[keith]

Helmut,

An interesting discussion. Your generation process is not what I would have imagined.

How do you do the symmetry of the starting cells?

I imagine a random symmetric starting pattern overlaid on a valid solution to see if it generates a valid puzzle.

That is sort of what the old "patterns game" is all about, no?

Keith

[nataraj]

Keith,

throughout the whole process, there are many places where the way to go is not obvious at all. When I began to think about generating puzzles myself, I thought about my emotional reaction to different kinds of puzzle layouts and I realized two things:

1 - I like symmetrical puzzles better. Horizontal symmetry is more pleasing to my eyes than vertical symmetry, and I like point symmetry best. So in fact when I generate a clue, it is either the central cell r5c5 or a pair of cells (x,y) and (10-x,10-y). I usually start with pairs, it is only at the very end that I fill the center cell.

2 - Squiggly puzzles look much nicer if bulky shapes are avoided. Dailysudoku's Squigglies used to be outright ugly for that same reason (maybe still are)
So out of all the possible nonominoes, I use only the "nice" ones.

Starting cells:
there is no "overlay" whatsoever. Aside from the restriction that the pattern must be symmetrical (see last paragraph) the whole process is random, but it follows an iterative pattern.

First, I create 9 pairs of cell coordiantes. Those are the starting cells. Fill with random numbers until there is at least one solution. (Phase C1)

Add more pairs. After every random throw, check for valid/invalid position. Too few clues (more than one solution): add more clues. Too many (or "bad") clues (no solution): try other clues for the same new pair or throw a new cell coordinate and try again. (Phase C2)

When the position has fewer then 30 solutions I stop adding random clues but instead select clues for the pairs out of the solution set. That is why Phase C3 is so fast.

Sorry, don't know about the patterns game. I do remember ravel posting puzzzles that said "patterns game" but I did not know what it referred to.

This is what the parameters for generation look like:

[Pat]

[nataraj]

Hi Pat !

Thanks for the link to the Patterns Game on the New Players Forum. I signed up there only a few days ago and have not had time to look into the various sections. Good to know the Patterns Game still exists.

As to your question, without having solved the puzzle by hand, the rating given by the Sudoku Farm would be a 0: do not consider for publication.

This is what the program finds:

[Pat]

thanks!

but perhaps someone (keith?)
would try it without "pencilmarks"?

[nataraj]

[keith]

Helmut,

The patterns game went something like this. Make a puzzle that meets a given stencil for the initial clues. Here is one stencil I remember for Valentine's day:

[nataraj]

sweet, a <3 for Valentine's Day

Now I think I want to experiment with patterns after all. Not for competition, not necessarily for the daily Sudok-o-Rama puzzles, but for a Special Edition maybe. Let's see if I can find the catalogue of patterns that have already been tried in the Patterns Game. From Pat's post I assume that there are at least 260 "layouts"...

Ah, how exciting - so much to do, so little time. Thank you Pat and Keith for setting me on this track.

Cheers
Helmut

Edit 0949 CET: found it. Patterns Game Results.

[Pat]

[nataraj]

[Pat]

[keith]

[nataraj]

Patterns Puzzles - interim report

Finally, this being Saturday and all, I got around to work on the patterned puzzles.

During that process I searched for old design documents, and lo and behold, I found one of the earliest notes from August 2010, when the Helper already existed and the Sudok-o-Rama began.

[Pat]