The fastest method of creating unique puzzles

kudosu · Site Admin

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

rubylips

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:

rubylips · Posted: Fri Apr 08, 2005 10:43 pm Post subject:

I ought to point out that all of the puzzles referred to in the previous post had 21 initially-filled cells.

shakers

rubylips · Posted: Sun Apr 10, 2005 1:55 am Post subject:

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.

Tony

rubylips · Posted: Thu Apr 14, 2005 11:53 pm Post subject:

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.

upsidedownface · Posted: Mon May 30, 2005 1:04 pm Post subject: Generate new puzzles

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.

rallveird · Posted: Mon Jun 13, 2005 2:29 am Post subject:

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.

jaap · Posted: Tue Jun 14, 2005 6:28 am Post subject:

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).

jimmyt · Posted: Wed Jun 15, 2005 3:09 pm Post subject: Looking for compiler/author

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

Nick70

Simes · Posted: Mon Jul 04, 2005 9:39 pm Post subject:

and so does forcing chains.
_________________
Simes
www.sadmansoftware.com/sudoku

antony · Posted: Fri Jul 22, 2005 1:17 am Post subject: dancing links efficiency

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

tilps · Posted: Fri Jul 22, 2005 4:28 pm Post subject:

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