Difficulty level

Lummox JR · Posted: Wed Sep 07, 2005 6:39 pm Post subject: Difficulty level

I've been trying my hand at a sudoku generator, using dancing links to find a valid unique-solution board. My first pass at this found that while I could easily and quickly generate sudoku, the resulting puzzle was almost invariably too hard, requiring one of the stickier techniques like coloring or trial-and-error. Basically I'd start out with a few random clues, remove some if the board was insoluable, add clues as needed until the solution was unique, and then in random order try to remove each of the clues in turn to see if the constraints still held.

So I implemented a human-style solver, and added the constraint that any board generated had to be solvable with my set of techniques (which basically goes up to swordfish, but not coloring or Nishio). If the board generated from the above approach was not solvable in this way, more clues would have to be added. Once enough clues were added, then I would go through a loop removing clues at random to see if the result was still a unique solution and solvable by a human.

The down side is, the resulting puzzles are now too easy! I ran them through a difficulty rating system similar to the first one in this thread, but stripped down and with a much lower weight for naked/hidden singles. Singles, pointing pairs, and box-line reduction are the techniques I see most, with subsets appearing hardly at all. (I've played with counting difficulty per unfilled cell, too, which gives me slightly different numbers but more or less the same result.)

Since it takes a short time to generate each puzzle in the interpreted language I'm using, generating a bunch of puzzles and hoping for a rare difficult one is not good enough. Instead I tried another approach, which is very slow and yields poor results. I set a target difficulty range, and then from the set of unfilled squares, I do the following:

Rate difficulty and store this as a benchmark.
Add an untested clue from one of the original unfilled squares. If none left, finish.
Remove other clues one by one to look for higher difficulty. Reject unsolvable or multiple-solution puzzles. Reject anything too high, or lower than the benchmark. If the new difficulty is in range, finish.
Add the removed clue back in; if its difficulty level was an improvement, mark it as the best candidate to remove permanently. Move on to the next clue.
Remove the best candidate, if any. If there were none, remove the clue added in step 2 and return to step 2.
Continue removing clues as long as the result has a unique solution and is human-solvable, and does not exceed the maximum difficulty.

As you can tell, this algorithm is lengthy. It'd be worth it if it would always guarantee a sufficiently difficult result, but it does not. So my question before the group is: What ways do you have of ensuring a certain difficulty level, besides generating huge batches of puzzles and hoping for a good one?

Another question: Would it be better if, after generating the grid via dancing links, I simply tested all potential unused clues for human-solubility and difficulty in the target range? I can well imagine such an algorithm being a lot faster than the tweaking I'm doing now, and returning a better result.

angusj · Site Admin

Lummox JR · Posted: Thu Sep 08, 2005 12:03 am Post subject:

It's step #2 I don't get there. How can you be sure of having a certain technique included in the solve path?

So far my only good results have come from adding and deleting clues ad nauseum until a puzzle achieves the difficulty rating I want. Basically it has to cast about at random to achieve this: If difficulty is too low it deletes any clues it can to keep a unique solution, and if it can't do that it adds a clue just so one of the others can be deleted later; then if difficulty is too high it will add clues. It's ridiculously slow-going, more or less the equivalent of casting about in the dark.

Is there perhaps some method of choosing where clues appear (or which clues, such as not including a certain digit or having it appear just once) that could improve my results? Once I get a unique board, I can choose from any numbers in the solution for the clue; perhaps a different means of placement is what I need most.

dukuso · Posted: Fri Sep 09, 2005 4:59 am Post subject:

did I understand correctly, you have a method to generate
hard sudokus, but you rejected it because you wanted
easier ones ?

What I've heard so far is that most people prefer to generate
lots of (almost)random sudokus quickly and then filter them.

Lummox JR · Posted: Fri Sep 09, 2005 5:33 am Post subject:

The dancing links algorithm, followed by aggressive pruning, most of the time produces puzzles that either are very easy or can't be solved by my human-style solver (despite having a unique solution). The solver can get more advanced later, to include XY-wing, perhaps coloring, and the uniqueness test (found here), but I'm concerned that even medium and semi-hard puzzles are almost never showing up by this method.

Because I'm working with an interpreted language, generating a huge number of puzzles and rating each is surely not the way to go. The generator is decent enough timewise at churning out a single puzzle, but hundreds is another matter. I do have the questionable option of using JavaScript, but I doubt it will be appreciably faster.

Right now my best idea is that puzzles seem to have greater difficulty when the clues are 1) spaced away from boxes/columns/rows so as to leave most near-empty and perhaps one each entirely empty, and 2) sparse for certain digits. Starting from a completed grid, if I have a rough idea of what sort of statistical layout a hard board has, and working from these clues, I'm hoping I can force a level of difficulty that's playable but not easy.

dukuso · Posted: Fri Sep 09, 2005 6:42 am Post subject:

I don't think it has to do with your solver ("dancing links")
I don't have the feeling that the generated puzzles are biased.

You can also just move in again 1 clue in the generating process if
you are not satisfied with the result and try again.
I mean, instead of starting from a full grid.
I also tried to find hard puzzles with hillclimbing, but that
was before I noticed how much puzzle hardness (=running time)
depends so much on the ordering of the rows and columns
in the exact-cover matrix.

I'm surprised that you use exact-cover method but yet
have all these sudoku-rules like XY-wing etc.

Hmm, I remember Jaap replaced them with just 2
exact-cover-rules in another thread.
I'll search for it, if you want and can't find it

Lummox JR · Posted: Sat Sep 10, 2005 5:10 am Post subject:

Changing one clue at a time is about what I've been doing with such a poor result. When this method can find a hard puzzle, it usually takes a long time to do so.

Regarding your comment about row/column ordering in the DLX matrix, have you found any particular order to be preferable to others?

I don't currently have XY-wing implemented in my human solver, nor Nishio nor coloring. I use the human solver only for telling if a unique-solution board can be attempted by a human with the techniques I already have, and in turn to rate the puzzle's difficulty. (Actually there are two forms of the solver: The one that rates difficulty will also focus on easier clues.) DLX is only used to generate the board and then to test for unique solutions. However, my human solver does use DLX's rows and columns in some interesting ways. Pointing pairs and box-line reductions, for example, are trivial when comparing clues in an exact-cover matrix. Finding subsets, X-wings, and swordfish are also fairly easy.

dukuso · Posted: Sat Sep 10, 2005 6:37 am Post subject:

Lummox JR · Posted: Sat Sep 10, 2005 3:51 pm Post subject:

By human solver I don't mean I have an actual human try to solve them, although when my human solver says one is solvable, I do often try it myself just so I can test whether it works, and whether it's picking the easiest clues. This is a human-style solver, meaning it uses rules a human would use to try to complete the puzzle. In this way I can rate the puzzle's difficulty and also tell if it's anything a human could attempt. Currently the tests are broken down into 3 forms which use the DLX matrix. In the following explanation, I refer to the groups of DLX columns as xy (a value must fit at {x,y}), bd (digit d fits in box b), cd (digit d in column c), and rd (digit d in row r).

1) Single solving looks for columns for which just a single row applies. Currently the algorithm focuses on naked singles (found in the xy columns) as the easiest, although I may modify this as well as the difficulty setting because I've found that hidden singles in a box (the bd columns) are much easier for a human, and can be solved by scanning alone.

2) Pointing pairs/triples and box-line reduction work more or less the same way. For each unmarked bd column in DLX, the algorithm examines the available rows. On the first row, it takes note of the cd and rd columns. Then it looks through the other available rows for this bd column; if there are more than 3 choices (the width of each box in a 9x9 grid), it gives up on this column. However if there are only 2 or 3 row choices available in this bd column, and they all have the same cd or rd column, then all other rows for that cd or rd column can be marked invalid. The box-line reduction tests work much the same way, except that the bd algorithm tested both cd and rd at the same time, whereas this test just goes through the cd and rd columns and keeps track of only bd. In all cases if no elimination is possible, the test will return no result.

3) Subsets, X-Wings, and Swordfish are all done in much the same way. A set of 9 DLX columns with some relationship is chosen, and then for each column a set of bit flags is built up by going through each row and turning on bits for all unmarked rows. (Note: This requires that the rows be in numerical order. My DLX solver shuffles the rows for a random result, so before human solving begins they must be unshuffled.) Then the set of bits is sent to a subset-finding algorithm. The subset algorithm will send back a list of which choices of the 9 columns had a subset, and which bits were included; it does not count a subset for which no elimination can be done. Looping through the other columns, rows with bit flags matching the subset can be eliminated.

And this is the extent of my human-style solver at present.

dukuso · Posted: Sun Sep 11, 2005 7:09 pm Post subject:

I use s (symbol) instead of d (digit).

your 2) , is it the same the if a column is a suberset of
another column then it can be truncated to the intersection ?

your 3.) is it "hyper-arc-consistency" ? Hall's theorem ?
Jaaps rule 2)

some older posts, which maybe you haven't seen:

------------------------------------------------------------------

My second rule is this:
Suppose there are 2 columns A and B, each with exactly two entries, say A1, A2, and B3,B4.
Suppose also that A1 conflicts with B3 (there is some column that has entries in rows 1 and 3) and similarly that A2 conflicts with B4.
Then we must have one of the moves 1 or 3, and also have one of the moves 2 or 4.
Any column with entries in 1 and 3 can have its other entries eliminated. Similarly, any column with entries in 2 and 4 can have its other entries eliminated.

This rule does things like this:
If one cell in row 1 has candidates {1 2}, another has candidates {1 2 3}, and no other cell in row 1 has 1 or 2 as a candidate, then the second cell has candidate 3 removed.

or like this:
If two cells in row 1 have only candidates {1 2}, then any other cell in row 1 can have 1 and 2 removed as candidates.

or like this (rectangular x-wings):
If the only placements of digit 7 in row 1 are in columns 4 and 5, and the only placements of digit 7 in row 8 are also in columns 4 and 5, then any other cells in columns 4 and 5 can have 7 removed as a candidate.

or even like this (other kind of x-wings):
If the only placements of digit 7 in box 1 are at (1,1) and (2,1), and the only placements of digit 7 in box 2 are (1,4) and (2,6), then any other cells in rows 1 and 2 can have 7 removed as a candidate.
(Actually this would most likely be caught by application of the first rule - restricting the 7 in row 3 to box 3, but occasionally things like the above do come up.)

Jaap

---------------------------------------------------------------------------------------------

Here is my own interpretation of some logic rules in the context of dancing links. Anyway, the good thing with dancing links is that most rules get naturally "generalized". For example, X-Wings with intersecting rows & columns also holds for intersecting rows & blocks, but you don't have to hard-code it, the algorithm does it automatically.

Below, "constraints" and "candidates" stand for the columns and rows of the dancing links matrix (that avoids confusion with the rows and columns of the sudoku grid.)

Transposal of Single sector, Locked pair, X-Wing, Swordfish, Jellyfish, some disjoint subsets:
Choose any constraint. Select (one after another) each candidate for it, look at which constraints can be solved by recursively solving sum-1 constraints only (stop when there are none left). If a constraint has been solved in all cases, you can discard any candidate for it, except the candidates you solved it with.
Notes:
- a constraint always solved within the first recursion is an X-Wing; within the first 2 recursions a Swordfish, etc.
- a constraint always solved before any recursion is a locked pair (if initially chosen constraint is sum-2) or a single sector. This means that the constraint has at least the same candidates as the chosen one.

Remote locked pair:
Choose any constraint. Select in turn each of its candidates, look at which candidates are discarded when you recursively solve sum-1 constraints. If a candidate has been discarded in all cases, you can discard it.

Forcing chains:
Choose any constraint. Select in turn each of its candidates, look at which others candidates are discarded or selected when you recursively solve sum-1 constraints. If a candidate has been discarded in all cases, you can discard it (one candidate down). If a candidate has been selected in all cases, it is part of the solution (that's one cell solved!)

Nishio:
Apply any candidate. Recursively solve sum-1 constraints only. If you end up with a sum-0 constraint, you can discard the candidate.

I still miss a satisfactory method for transposing Disjoint Subsets and Unique Subsets...

I don't know if it's accurate. Hoping it makes sense
Regards

[Added: if anyone is interested in a Java Dancing Links (with links) solver, I rewrote my C++ class:
http://jpboucher.free.fr/antony/DLXSolver.java.zip ]

jaap · Posted: Mon Sep 12, 2005 9:48 am Post subject: