Sudoku Programmers Forum Index

 
 FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister   ProfileProfile   Log inLog in          Games  Calendar

Log in to check your private messagesLog in to check your private messages   

The fastest method of creating unique puzzles
Goto page 1, 2  Next
 
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Setting sudoku
View previous topic :: View next topic  
Author Message
kudosu
Site Admin
Joined: 04 Apr 2005
Posts: 20
:
Location: London

Items
PostPosted: Fri Apr 08, 2005 9:46 am    Post subject: The fastest method of creating unique puzzles Reply with quote

If I may, I'd like to pick up the discussion about setting puzzles.

IJ wrote:

My original idea was to start with a solution, and remove cells
symmetrically in pairs, testing each time that a move is possible (i.e.
one of the known rules can make a reduction).  Keep removing cells
until no move is possible, and put the last ones back - simple (you
could iterate here to see if other cell choices would get you further).
 I feel that just testing for a single reduction at each stage should
be sufficient to ensure it is solvable, but I'm less certain of this
than I was.  The problem is that this metthod doesn't really offer any
way to ensure a particular rule will be needed.


rubylips wrote:

I simply create lots of puzzles (I start with an empty grid and
populate it rather than remove cells from a completed grid - though I
have no proof that my method is better) then solve them and, if they
are valid, classify them. I'll add a major post on the topic as soon as
I've resolved Swordfish to my satisfaction. Interestingly, the key
algorithm used to decide where to place cells on the grid is precisely
that I use to calculate where best 'to guess'.

One point - it's critical to have a very high-performance solver in
place if you're to create puzzles - because you end up with thousands
of near-puzzles that have to be filtered out.


On reflection, I think that starting with an empty grid might be a good idea. The big problem with the other method is that you first have to generate a finished puzzle, and it is a tricky problem in itself to tap the entire set of legal sudoku solutions.

Also, since considerably less than half of the cells are initially filled with clues, it should be faster to start from an empty grid.

However, an interview I read with Wayne Gould seems to suggest that he starts from a full grid:

Wayne Gould wrote:

You can set Su doku puzzles “by hand”, if you want to, though I haven’t done it much myself. You use much the same skills you do when solving a puzzle, but backwards.


Any thoughts?
Back to top
View user's profile Send private message Send e-mail AIM Address
rubylips

Joined: 07 Apr 2005
Posts: 62
:
Location: London

Items
PostPosted: Fri Apr 08, 2005 12:54 pm    Post subject: Frequency of various Sudoku patterns Reply with quote

As explained in the previous post, as things stand I create a whole stack of puzzles then filter out the interesting ones. I've just run a 30 hour batch job that's created 18831 random puzzles. Here's the feature count.

First, I divide the puzzles according to the number of 'unwinds' necessary in order to establish that the puzzle has a unique solution. This figure is one even for a 'purely logical' puzzle because the solver has to unwind from the completed solution in order to search for possible alternative solutions. Different solvers will calculate different numbers of unwinds for puzzles that aren't purely logical, depending upon the quess strategy implemented.

# Unwinds : # Instances

1: 14768
2: 2039
3: 955
4: 480
5: 263
6: 141
7: 64
8: 44
9: 34
10: 16
11: 6
12: 2
13: 4
14: 4
15: 2
16: 3
17: 3
21: 1
22: 1
48: 1

For the record, here's the 48-unwind puzzle. Don't try it at home unless you have a brand new bottle of Tipp-Ex to hand:

Code:
 . . . | . . 3 | . 6 .
 . . . | . . . | . 1 .
 . 9 7 | 5 . . | . 8 .
----------------------
 . . . | . 9 . | 2 . .
 . . 8 | . 7 . | 4 . .
 . . 3 | . 6 . | . . .
----------------------
 . 1 . | . . 2 | 8 9 .
 . 4 . | . . . | . . .
 . 5 . | 1 . . | . . .

The 'purely logical' puzzles have been further subdivided according to the strategy types that had to be invoked in order to solve them. (The multi-guess puzzles haven't been categorized because my current code sometimes counts, say, a Nishio in a thread that is later unwound). The key to the strategy types is as follows:

SSC: Single Sector Candidates
DS: Disjoint Subsets
X: X-Wings
S: Swordfish
N: Nishio

The numbers don't sum to 14768 because (i) many puzzles didn't invoke any of the listed strategies and (ii) many puzzles invoked multiple strategies and have been counted twice.

SSC: 6218
DS: 2791
X: 39
S: 9
N: 546

It has already become clear how difficult it is to create a puzzle that features an X-Wing or a Swordfish. However, given that, ideally, our X-Wing and Swordfish puzzles shouldn't have to be completed by a Nishio, I've recategorized the 'X' and 'S' firgures from above:

X-Wings:

SSC:DS:X 15
SSC:DS:X:N 12
SSC:X 4
DS:X:N 2
SSC:X:N 2
X:N 2
DS:X 1

Swordfish:

SSC:DS:S:N 5
S:N 2
SSC:DS:X:S 1
SSC:S:N 1

It follows that from 18831 original puzzles, we have just 20 'ideal' X-Wings examples and a solitary 'ideal' Swordfish.
Back to top
View user's profile Send private message Visit poster's website
rubylips

Joined: 07 Apr 2005
Posts: 62
:
Location: London

Items
PostPosted: Fri Apr 08, 2005 10:43 pm    Post subject: Reply with quote

I ought to point out that all of the puzzles referred to in the previous post had 21 initially-filled cells.
Back to top
View user's profile Send private message Visit poster's website
shakers

Joined: 09 Apr 2005
Posts: 1
:

Items
PostPosted: Sat Apr 09, 2005 9:29 pm    Post subject: Re: Frequency of various Sudoku patterns Reply with quote

rubylips wrote:
For the record, here's the 48-unwind puzzle. Don't try it at home unless you have a brand new bottle of Tipp-Ex to hand:

Code:
 . . . | . . 3 | . 6 .
 . . . | . . . | . 1 .
 . 9 7 | 5 . . | . 8 .
----------------------
 . . . | . 9 . | 2 . .
 . . 8 | . 7 . | 4 . .
 . . 3 | . 6 . | . . .
----------------------
 . 1 . | . . 2 | 8 9 .
 . 4 . | . . . | . . .
 . 5 . | 1 . . | . . .


From what you said I took this to be a logic based puzzle... however I just fed it into Pappocom program and it refuses to verify it, which I understand to mean that it cannot be solved using logic.

It's a little too late on a Saturday evening to try doing this by hand so it will have to wait... but I'd be interested to know whether you believe it should be logic solvable.
Back to top
View user's profile Send private message
rubylips

Joined: 07 Apr 2005
Posts: 62
:
Location: London

Items
PostPosted: Sun Apr 10, 2005 1:55 am    Post subject: Reply with quote

Sorry - I should have been a little clearer. Any puzzle reported by my solver to be soluble with a single unwind is soluble by 'pure logic' - though my solver, unlike Pappocom, counts the 'Nishio' technique as pure logic. Those puzzles reported to be soluble with multiple unwinds could conceivably be solved by pure logic - but only if my solver has missed the necessary logical trick. It's almost certain that a puzzle reported to be soluble only with many unwinds will require guesses (though I haven't seen a definite proof of the fact that there are puzzles that can't be solved by 'logic' - whatever that is - alone).

The main purpose of such puzzles is to test solver performance.
Back to top
View user's profile Send private message Visit poster's website
Tony

Joined: 11 Apr 2005
Posts: 6
:
Location: West Sussex

Items
PostPosted: Mon Apr 11, 2005 3:33 am    Post subject: Re: Frequency of various Sudoku patterns Reply with quote

Code:

 . . . | . . 3 | . 6 .
 . . . | . . . | . 1 .
 . 9 7 | 5 . . | . 8 .
----------------------
 . . . | . 9 . | 2 . .
 . . 8 | . 7 . | 4 . .
 . . 3 | . 6 . | . . .
----------------------
 . 1 . | . . 2 | 8 9 .
 . 4 . | . . . | . . .
 . 5 . | 1 . . | . . .


Hi,
As a relative newcomer to this, can you help with a definition of the 'Rules'. X-Wing I understand. My own solver program already includes this and other rules on Pairs etc, solves virtually every published puzzle, but yeah - this one has stopped it in its tracks !!

Time therefore to implement the 'N-Set Rule' ie N digits, occupy N Cells.

SSC is what I have termed 'Unique' to cell ??
X- Wing I know
DD = N-Cell rule ??
Swordfish ??
Nishio ??

look forward to your reply.
Back to top
View user's profile Send private message
rubylips

Joined: 07 Apr 2005
Posts: 62
:
Location: London

Items
PostPosted: Thu Apr 14, 2005 11:53 pm    Post subject: Reply with quote

I'd first like to emphasize that guesses - lots of them - are necessary in order to solve this puzzle. It can't be solved solely by the 'purely logical' rules familiar to readers of The Times.

'Single Candidature' is my name for the rule that governs trivial placements, i.e. when just a single candidate value exists for a cell or when a single candidate position in a row, column or box exists for a value.

'Single Sector Candidates' governs situations where, for instance, all the possible candidate position for a given value in a given box ('sector' is my generic term for a row, column or box) lie on a single row, so the other candidates on that row are able to be eliminated.

'Disjoint Subsets' governs situations where some subset of values is certain to occupy an equivalently-sized subset of cells on a sector, which allows other candidate values to be eliminated.

I've posted definitions of 'X-Wings', 'Nishio' and 'Swordfish' to the 'Solving Sudoku' topic in this forum.
Back to top
View user's profile Send private message Visit poster's website
upsidedownface

Joined: 27 May 2005
Posts: 5
:
Location: Leeds

Items
PostPosted: Mon May 30, 2005 1:04 pm    Post subject: Generate new puzzles Reply with quote

You can make an existing problem (or solution! ) into what looks like a new one, but I think is really the same; by applying transformations that can not violate the Sudoku conditions.i
The allowable transformations for 9x9 are :-
1. any cyclic permutation of the numbers like 1>5>8>3> etc, so that each number remains used once in each block,row and column.
2. any two rows may be swapped as long as they are both in the same block, and the column order is unchanged. This means any pair of rows 1,2,3 may be interchanged among themselves, but not with any of rows 4,5,6,7,8,9; and similarly for 4,5,6 excluding 1,2,3,7,8,9 and also 7,8,9 etc.
3. any two columns may be swapped with the same conditions as for rows
4. any two columns of blocks may be swapped.
5. any two rows of blocks may be swapped

So swapping column blocks 1&2; rows 4&5 and 4>1>5>2>6>7>3>9>8>4

.96|4..|... 1..|.87|...
..2|.59|4.. .28|..6|1..
..5|...|.2. ...|..2|.6.
----------- ------------
...|92.|... 5.2|.1.|.4.
.4.|1.5|.8. 86.|...|...
...|.68|... .74|...|...
----------- -----------
.3.|...|2.. .9.|...|6..
..9|27.|6.. ..8|63.|7..
..|..3|57. ...|..9|23.

I think these two are really the same problem !!!
But how do you tell?

What I would really like is a metric which shows how many solutions exist for a given incomplete square.
When you start with an empty square and add numbers, there should be a stage when the number of solutions drops from huge to one. Then you have got a valid problem, or the number of solutions drops from two or more, to zero; you havent got a valid problem
Equally when you start with a full valid square, at some stage the number of solutions will increase from one, to two or more. This is the stage where you have removed one too many and need to put it back for a valid problem.
The only way I can think of to calculate this metric is to examine all possibilities and count how many are valid sudoku squares.
Back to top
View user's profile Send private message
rallveird

Joined: 13 Jun 2005
Posts: 31
:

Items
PostPosted: Mon Jun 13, 2005 2:29 am    Post subject: Reply with quote

I would like to see some numbers from people on which type of solving is fastest. I'm not interested in the "best" way to solve it. As pointed out in first post, the crusial point in creating sudokus is how fast can you check if it's legal (only 1 solution).

I've skipped a lot of logic solving in my solver and I solve the unwind 48 sudoku here in what I call 1007 iterations (947 if you remove the starting numbers), using 25ms to solve it with my standard solver (java). If I use the most optimal solver for that sudoku I solve it in 403 (343) iterations using 22ms.

I'm not sure I could solve it that fast if I put in a lot more logic to solve them. I will perhaps some day implement some logic methods just to check the result.

My solving code basically try to find the spot with least possible numbers and iterate from there (over the possible numbers). The difference in iterations comes from different implementations to pick the spot to check if there are more than 1 spot with the same amount of least numbers.
Back to top
View user's profile Send private message
jaap

Joined: 13 Jun 2005
Posts: 24
:
Location: NL

Items
PostPosted: Tue Jun 14, 2005 6:28 am    Post subject: Reply with quote

Hi,

This is my first post here.
I have also made a Sudoku solver/generator. I'd be interested to hear what you guys think of it, and how it compares to others.

http://www.geocities.com/jaapsch/sudoku.htm

The solver uses a clever brute force method, essentially the Dancing Links algorithm by Don Knuth (without the links but with the full matrix instead).

rallveird wrote:
I would like to see some numbers from people on which type of solving is fastest.


I don't have any numbers on mine, but the solver does use two solving modes - a fast one for checking solvability, and one with extra logical rules that generates a log and judges difficulty more accurately.

rallveird wrote:
My solving code basically try to find the spot with least possible numbers and iterate from there (over the possible numbers).


The fun part of the dancing links algorithm is that all the constraints that need to be satisfied are treated equally. A cell with only one possible digit, or a row/column/box with only one placement for a particular digit, are both treated in the same way. If none of these constraints have only one possibility, then (in fast mode) it makes a guess for one of the constraints that has only 2 possibilities. This can be a cell with two possible values, or a row/column/box with two possible placements for a particular digit.

I implemented two extra deduction rules for slow but more human solving. The first is a 'single sector candidates' rule:

1. If all possibilities for satisfying one constraint also satisfy a second constraint, then any other possibilities for the second constraint may be discarded.

The second rule is this:

2. If a pair of constraints can be satisfied in only two interdependent ways, then any other constraint that is satisfied by both those solutions can have its other possibilities discarded.

This reads like a kind of x-wings rule, but due to the equal treatment of the constraints, many cases of the 'disjoint subsets' rule also get caught by this one.

Let me know what you think.
_________________
Jaap
--
Jaap's Puzzle Page:
http://www.geocities.com/jaapsch/puzzles
Back to top
View user's profile Send private message Visit poster's website
jimmyt

Joined: 15 Jun 2005
Posts: 1
:

Items
PostPosted: Wed Jun 15, 2005 3:09 pm    Post subject: Looking for compiler/author Reply with quote

My name is Jimmy Topham - I am commissioning editor at Quantum Publishing, part of the Quarto Publishing group, which is based in London.

My company is interested in producing books on Sudoku and we are looking for a potential compiler/author. If you are interested and think you are up to the challenge, I'd be very interested to speak to you about this.

Your main job would be to compile the puzzles, but we'd also like you to write a short introductory chapter to the game.

You can contact me by sending an email to JimmyT@quarto.com

Many thanks for your time.

Kind regards

Jimmy

Jimmy Topham
Commissioning Editor
Quantum Publishing
Back to top
View user's profile Send private message
Nick70

Joined: 08 Jun 2005
Posts: 160
:

Items
PostPosted: Mon Jul 04, 2005 7:38 pm    Post subject: Re: Frequency of various Sudoku patterns Reply with quote

rubylips wrote:
For the record, here's the 48-unwind puzzle. Don't try it at home unless you have a brand new bottle of Tipp-Ex to hand:

Code:
 . . . | . . 3 | . 6 .
 . . . | . . . | . 1 .
 . 9 7 | 5 . . | . 8 .
----------------------
 . . . | . 9 . | 2 . .
 . . 8 | . 7 . | 4 . .
 . . 3 | . 6 . | . . .
----------------------
 . 1 . | . . 2 | 8 9 .
 . 4 . | . . . | . . .
 . 5 . | 1 . . | . . .


Interestingly, I just found that advanced coloring happily finds the logical step needed to solve this one:

Code:
.      8      .       | .      .      3       | .      6      .     
.      3      .       | .      .      .       | .      1      .     
.      9      7       | 5      .      .       | 3      8      .     
----------------------+-----------------------+----------------------
.      67     .       | .      9      .       | 2      357    .     
159   [26]    8       |[23]    7      15      | 4     [35]    169   
1459  [27]    3       | 248    6      1458    | 19    [57]    189   
----------------------+-----------------------+----------------------
.      1      6       | .      .      2       | 8      9      .     
.      4      9       | .      .      .       | .      2      .     
.      5      2       | 1      .      9       | 6      4      .     
Back to top
View user's profile Send private message
Simes

Joined: 08 Apr 2005
Posts: 71
:
Location: North Yorkshire, UK

Items
PostPosted: Mon Jul 04, 2005 9:39 pm    Post subject: Reply with quote

and so does forcing chains.
_________________
Simes
www.sadmansoftware.com/sudoku
Back to top
View user's profile Send private message Visit poster's website
antony

Joined: 22 Jul 2005
Posts: 13
:

Items
PostPosted: Fri Jul 22, 2005 1:17 am    Post subject: dancing links efficiency Reply with quote

Hi all,
This is my first post too. I've been experimenting with Knuth's Dancing Links algorithm. Using it, my small solver in C++ solves the "48 unwinds" grid in 0.7 milliseconds. Other grids take about 0.12 ms.

Here is the app with source code. It can be modified to run even faster for grid generation (where creating constraints is incremental).

Regards,
Antony
Back to top
View user's profile Send private message
tilps

Joined: 19 Jun 2005
Posts: 44
:

Items
PostPosted: Fri Jul 22, 2005 4:28 pm    Post subject: Reply with quote

With thanks to antony's example dancing links, i've finally got my 'ideal' generator running at an acceptable speed.
Code:

while (true)
{
  Randomly add a rotationaly symetric pair or the single in the middle  to the list of points to be processed, if they have not already been added.
  Run dancing links with current point set.
  If solution count > 1
    continue
  if solution count == 1
    break
  if solution count == 0
    remove pair/single just previously added 
}
'Optional step' remove a pair/single which doesn't stop the puzzle from being solved, at random. Repeat until none can be removed.
Rate with a slower 'rating' solver.


With this I can generate about 1000 sudoku a minute in C# (not using the optional step), which is plenty to test whether my rating solver cant solve stuff and find new even higher rated sudokus.
Back to top
View user's profile Send private message
Display posts from previous:   
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Setting sudoku All times are GMT
Goto page 1, 2  Next
Page 1 of 2

 
Jump to:  
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
Sudoku Programmers topic RSS feed 


Powered by phpBB © 2001, 2005 phpBB Group

Igloo Theme Version 1.0 :: Created By: Andrew Charron