Puzzle design method, all handcrafted

Everything about Sudoku that doesn't fit in one of the other sections

Puzzle design method, all handcrafted

Postby Thierry Moreau » Sat Dec 24, 2011 11:16 am

Hi!

From my sudoku solver algorithm http://sudoku.connotech.com, I made a puzzle design method, all handcrafted in the sense that it uses no computer generated random numbers. This method is still unpolished, but I guess I am getting a reasonable scheme.

Here is the latest outcome (my first use of the latest refinement in the method):

....6...4..........5.3.98..8....3...4......2....1.7.........7.9.1......5.3.62.1..

with only 20 clues, I feel the puzzle generation method is refined enough (sorry, I didn't rate the puzzle myself).

Merry Christmas!

- Thierry Moreau
Thierry Moreau
 
Posts: 6
Joined: 20 December 2011

Re: The hardest sudokus (new thread)

Postby champagne » Sat Dec 24, 2011 11:38 am

Thierry Moreau wrote:Hi!

From my sudoku solver algorithm http://sudoku.connotech.com, I made a puzzle design method, all handcrafted in the sense that it uses no computer generated random numbers. This method is still unpolished, but I guess I am getting a reasonable scheme.

Here is the latest outcome (my first use of the latest refinement in the method):

....6...4..........5.3.98..8....3...4......2....1.7.........7.9.1......5.3.62.1..

with only 20 clues, I feel the puzzle generation method is refined enough (sorry, I didn't rate the puzzle myself).

Merry Christmas!

- Thierry Moreau


Welcome in that forum Thierry.

I am not 100% sure this is the right place to publish that puzzle.

It is rated 2.6, by Sudoku Explainer and skfr, nearly the lowest existing rating.

If you want to exchange on puzzle generation and puzzle solving on a soft view point, you have a software entry in the forum.

basically, as far as I know, existing generators are of 3 main kinds:

random generators
generators scanning a pattern
generators using a seed and working in the vicinity of a seed

choosing between these different ways to generate puzzles is much depending on what your intend to do.

I did not catch in which family would be your generator.

Merry Christmas

champagne
champagne
2017 Supporter
 
Posts: 5653
Joined: 02 August 2007
Location: France Brittany

Re: The hardest sudokus (new thread)

Postby JasonLion-Admin » Sat Dec 24, 2011 1:06 pm

champagne wrote:I am not 100% sure this is the right place to publish that puzzle.
I moved these two posts into a new topic.
User avatar
JasonLion-Admin
Site Admin
Site Admin
 
Posts: 72
Joined: 17 April 2010
Location: Silver Spring, MD, USA

Re: Puzzle design method, all handcrafted

Postby Thierry Moreau » Sat Dec 24, 2011 5:43 pm

Thanks for the feedback and promotion as a new topic initiator!

A quick reply to champagne.

The generation strategy would not fit in any of the three categories.

The designer starts with a blank grid, fills in clues incrementally reducing the set of solutions from
1) huge to many, and then either
2a) from many to one or
2b) from many to none.
3) Once the step 2a) is completed, it may be useful to remove extra clues (if any) from the puzzle.

Clues selection is manual, the software reports data (presumably) having the potential to assist the designer in selecting clues depending on what is intended.

In the above first noteworthy experiment (with new step 2a-2b), I just wanted to complete the design cycle. Thus, a small number of clues was a favorable outcome.

Now online is the solver and the step 3) which can be used to turn a puzzle with extra clues into a harder one. The step 1) is somehow on-line but lacks relevant summary statistics.

Transition from step 1 to 2a-2b may require an intermediate step 1.5. It's a matter of making things not too compute-intensive. The step 2a-2b computes every possible solutions for the puzzle-in-progress, yet it is not too compute-intensive for samples from the hard puzzle list from which two or three clues are removed (the exploit would be to remove three clues, then add only two and get a valid puzzle).

Bye,

- Thierry
Thierry Moreau
 
Posts: 6
Joined: 20 December 2011

Re: Puzzle design method, all handcrafted

Postby champagne » Mon Dec 26, 2011 7:34 am

Hi Thierry,

Just a small comment.

Such process can help somebody to get a feeling on the structure of valid puzzles.

Most of the persons working in that field are considering millions of puzzles (I commonly generate 10 millions of puzzles in a day)

This can not be done in a manual process.

May be it would be necessary to identify clearly who can be interested buy such a process knowing that all solvers gives already some possibilities to build a valid puzzle just using the validity check.

You can, for example fill manually a grid using Sudoku Explainer an check, step by step if you got a valid puzzle.

champagne
champagne
2017 Supporter
 
Posts: 5653
Joined: 02 August 2007
Location: France Brittany

Re: Puzzle design method, all handcrafted

Postby Thierry Moreau » Tue Dec 27, 2011 4:18 pm

champagne wrote:Hi Thierry,

Such process can help somebody to get a feeling on the structure of valid puzzles.


Intuitively, I was thinking this way too.

Now, the "design parameters" checkbox on-line capability is at par with my internal experiments.

The intriguing feature is to show the structure of an ideal puzzle (i.e. no extra clue) by removing any clue. Some hard puzzles seems to always have a unique way of coming back to a valid puzzle (re-inserting the removed clue), but other puzzles may be quite different. For instance, starting from this multiple-solution-clue-set

.......961...4...3..6.1......7..6......2.9..4.3......5.4.....8.5.8...........1.3.

you have 12 options to come up with a valid puzzle.

champagne wrote:Hi Thierry,

May be it would be necessary to identify clearly who can be interested buy such a process knowing that all solvers gives already some possibilities to build a valid puzzle just using the validity check.


Basically, I developed an efficient sudoku solver core and I used it as an example/milestone in the web server project. Since a sudoku solver is not attractive these days, I felt the need to include this puzzle characterization slant. But at the same time, I do not want to give away cpu cycles, thus I refrain from e.g. automated searches for fewer clues in a given puzzle.

So, the basic answer is puzzle generation algorithm designers may use the characterization capability as an ad-hoc investigation tool.

I have currently no incentive to release the core algorithm (and some minor variations of it) for inclusion into other sudoku software.

Regards,

- Thierry
Thierry Moreau
 
Posts: 6
Joined: 20 December 2011


Return to General