puzzle generation

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

puzzle generation

Postby Vechietto » Fri Jan 20, 2006 9:33 pm

Would anyone be kind enough to give me some basic info. on how puzzles are generated?

Given the vast numbers of puzzles that appear all over the place it is either very simple or peraps not! Nodoubt there is a computer program at the back of it all?

Vechietto
Vechietto
 
Posts: 2
Joined: 19 January 2006

Postby PaulIQ164 » Fri Jan 20, 2006 9:41 pm

Most puzzles are indeed generated by computer programs. But not all of them - Nikoli puzzles, as published in The Guardian, are handmade.

The actual ins and outs of generating puzzles are, I think, not really supposed to be discussed here, since it's how Pappocom makes its money. Though it's largely irrelevant as I don't know the first thing about it anyway.
PaulIQ164
 
Posts: 533
Joined: 16 July 2005

Postby gfroyle » Sat Jan 21, 2006 12:18 am

PaulIQ164 wrote:The actual ins and outs of generating puzzles are, I think, not really supposed to be discussed here, since it's how Pappocom makes its money. Though it's largely irrelevant as I don't know the first thing about it anyway.



I think the confidential part of Pappocom's software is the RATING of puzzles.

Generating a valid puzzle is easy

- pick a random completed grid
- delete clues randomly (or systematically) testing at each stage that the resulting grid can ONLY be completed back to the original grid (ie has just one solution)
- optionally add clues to make it symmetric or make it easier

The tricky part is to then ensure that the resulting puzzle is of reasonable difficulty and reasonably interesting for solvers.

So as not to step on Pappocom's toes, I will not even speculate on how this might be done, except to note that one of the recent articles in either New Scientist or American Scientist (I forget which) said that "15 to 20 different factors were involved".

Gordon
gfroyle
 
Posts: 214
Joined: 21 June 2005

Puzzle generation

Postby Vechietto » Sat Jan 21, 2006 6:00 pm

To: Paul IQ164

Thankyou for your reply.

I had a notion about deleting entries from a completed grid but I'm not sure about generating a random completed grid. A computer program could do this fairly simply I suppose, otherwise, by hand, it would be just as difficult as completing a puzzle?
Still, I don't wish to labour the point. Thanks again.
Vechietto
Vechietto
 
Posts: 2
Joined: 19 January 2006

Postby coloin » Sat Jan 21, 2006 6:11 pm

This is a page with available computor software

http://magictour.free.fr/sudoku.htm

I can recommend http://magictour.free.fr/suexg.exe to generate sudokus as a "pastable" line of numbers.

C
coloin
 
Posts: 1638
Joined: 05 May 2005

none

Postby Chessmaster » Sun Jan 22, 2006 4:23 am

i make some puzzles and what i do is is i make the final product and take numbers out of the puzzle until i get it the way i want.
Chessmaster
 
Posts: 191
Joined: 21 December 2005

Postby ab » Mon Jan 23, 2006 2:32 am

I wrote my own solve (in qbasic) specifically so I could create puzzles. If you have a solver, you can start filling in the grid until you have a completed puzzle or the solver says there is no solution.

I have made a couple of puzzles by hand. I decided where I wanted the clues then started by picking one number and placing that maybe 3 times to generate another place where that number will appear and then continuing with other numbers. Each time it took about 4 hours to generate the puzzle and I had to backtrack a couple of times.

With the compuer aided designs it takes me 5-30 minutes to make a puzzle.
ab
 
Posts: 451
Joined: 06 September 2005


Return to General