The New Sudoku Players' Forum

[hobiwan]

In experimenting with templates in ver 1.1, I see the entries for "Template Set" in the batch solution log output, but there is no indication of which cell(s) have been assigned some specific value, at least on that specific output line. "Template Delete" gives the exact candidate eliminations.

Yes unfortunately this is a bug. Thanks for your help!

[PIsaacson]

Request for Enhancement:

I'm currently running an awk script against batch output, scanning the text to get as accurate of a count as possible for determining the efficacy of various techniques. While better than nothing, awk'ing is far from perfect.

If you track statistics internally on the number of eliminations/assignments per technique, is there some way to extract this information? Could you add this as an option in a future release?

Thanks,
Paul

[hobiwan]

I could replace the normal step output with the output used in the all steps dialog or a combination of both (which should be easier to parse). Example:
Instead of

Code: Select all

Skyscraper: 9 in r1c2,r9c3 (connected by r19c8) => r3c3,r8c2<>9

it could say:

Code: Select all

9 (2):r3c3,r8c2<>9 (Skyscraper)

(read: eliminated digits + number of eliminations in parenthesis).

For setting a digit it would be:

Code: Select all

Forcing Net Verity: r9c8=4

If you want more of a statistic thats can probably done rather easily too, but I would need a more detailed request.

[Draco]

Does tracking number of eliminations really help? It seems that there are many puzzles out there (just posted something on StormNorm's puzzle today) that are cracked by a single elimination, even though there are other techniques that might apply (and get you there, but require additional steps).

Seems like you'd need a scoring mechanism (a la SE ratings) to see how much your move simplifies the puzzle overall vs. how many eliminations are made to find an efficient path. As noted in the HoDoKu manual, such a scoring altorithm needs to be a stable/"absolute" measure of overall puzzle difficulty.

Of course, at that point the efficient path is tied closely to your scoring algorithm and the choices it makes, no?

Overall, Hobiwan, do you see value in features that try all possible moves at any given point and pick the one that most simplifies the puzzle? I've done something like that for forcing chains and have thought about applying it to the puzzle overall, but it would no doubt be slow (REALLY slow). Certainly could help one find the "elegant" path (i.e. quickest to singles) through a puzzle if your scoring algorithm is consistent enough.

Thoughts?

Cheers...

- drac

[hobiwan]

Draco,

I didnt spend much time on the rating mostly because I dont believe in ratings. A SE 10 will of course be much harder than a SE 5 but nevertheless I dont think such a thing as an "absolute measure" of the difficulty of a puzzle does exist.

Besides the obvious dependency on personal preferences (which techniques are applied in which order) there will always be the back door problem (as you already noted). A move with one elimination that unlocks the back door will of course be much more effective than a move with lots of eliminations that leave the back door closed. But I think for a large amount of average puzzles the number of eliminations will have an influence on the length of the solution (but I dont have a proof for that).

For finding the shortest possible path: I think a real brute force approach will work but will be to slow. We discussed the possibility of taking the number of singles unlocked by a move as a measure a while back (daj suggested something similar). A tradeoff would probably be to systematically attack back doors. This probably wont give the shortest path possible but a significantly shorter one than a standard algorithm (but we will have stopped even trying to mimick the behaviour of human solvers).

[daj95376]

I post puzzles for the members of another forum. I recently posted a puzzle where my solver used an X-Wing, XY-Wing, XYZ-Wing, and some basics mixed in for good measure. I informed them that an XYZ-Wing was present in the solution found by my solver. The first person to reply said that the XYZ-Wing was sufficient by itself. Sure enough, (s)he was correct ... and I had egg all over my face.

I have a backdoor checker for chains/SINs in my solver. I was hoping that hobiwan would see the value of adding it to HoDoKu.

As for speed, there was a reason why I suggested a limited number of techniques be offered for use in the backdoor checker.

[tarek]

The number of unlocked singles by a technique can be used to choose a suitable step from group of similar steps ....

If the look ahead depth is increased then you will get beter options ... It would then look similar to a chess program.

tarek

[Draco]

It is interesting that we (and our solvers) can get into a rut in terms of which techniques we look for/apply and in what order. Whether using my solver or trying by hand, I'll always look for patterns before locked sets/claiming before fish... unless (by hand) one happens to just jump out at me. More common when I solve by hand is to see a pattern of 2 or 3 while scanning for singles.

Of course my solver nails all singles first. One of the many kewl things about HoDoKu is the configurability that lets you change the order of things.

I finally settled on an "absolute" scoring scheme when I started adding many different puzzle sources into my solver (i.e. for direct downloading) and found the ratings varied so much it was hard to explain what to expect when users downloaded different puzzles (UClick and SudokuPuzz are especially bad). It gave me a way let users have a semi-consistent idea of how one puzzle compares to another.

Once I did that, it wasn't too long before I started applying that to searching for a better chain/net (a la Daj's SIN/chain search); my search is rewards the largest "reduction" in the difficulty score (when there is a tie there are other criteria). It made a huge diference in the number of chains/nets I needed to crack a puzzle that exhausted my solver's other techniques.

Then I used the scoring code as a coarse (and fine grained, as desired) measure to generate puzzles of specific difficulty overall or (akin to HoDoKu) with specific features present (or not) regardless of level. Much more fun than just randomly generating puzzles.

This discussion happened along just as I started thinking about whether or not it would make sense to apply this scoring to SSTS moves instead of taking them blindly (as I do now). But that would mean for any given grid state looking at each potential pattern, locked set, fish, etc and scoring the result (scoring is expensive), then taking the move that reduced the score the most. It would not guarantee the shortest path, but if my experience with chains/nets is any indication, it will be a shorter path than counting eliminations.

Slow? Probably though not as much as you might think for single moves (i.e. what is my next, best move?).

Not trying to convert you, Hobiwan. Just looking for input on the idea

Cheers...

- drac

[hobiwan]

I have a backdoor checker for chains/SINs in my solver. I was hoping that hobiwan would see the value of adding it to HoDoKu.

As for speed, there was a reason why I suggested a limited number of techniques be offered for use in the backdoor checker.

Slow? Probably though not as much as you might think for single moves (i.e. what is my next, best move?).

Not trying to convert you, Hobiwan. Just looking for input on the idea

I do see a value in adding a backdoor checker (and it is on my ToDo list, but that list get's larger every day ).

I think we have to differentiate between a standard solving algorithm that is executed every time a puzzle is loaded (solver1) and an extra analyzation feature (solver2).
For solver1 speed is essential: Since the algorithm kicks in every time a puzzle is loaded and the user is blocked until it is finished it has to solve average puzzles in under 1s.
For solver2 speed is not necessarily an issue as long as some kind of progress bar is displayed and the solving can be interrupted.
A second distinction lies in the difficulty of a puzzle: If it is only medium to hard (in HoDoKu's terms) solving will still be fast enough but since the solutions are normally rather short the gain will be minimal.
For really hard puzzles every kind of look ahead logic will probably be too slow for solver1.

That said: What I have in mind for HoDoKu are two things:

A backdoor checker that indicates which candidates/cells to attack when manually tuning solutions
A kind of "progress measure" for all steps found in an all steps search (danny's idea)

Everything else will have to wait longer. A few thoughts though:
I still see two ways to shorten the solution paths (and both have been mentioned by other forum members in this and other threads - not my idea):

Choose steps that attack backdoors
Use the "progress measure" before applying steps

Besides the obvious speed problems (even when using danny's restricted set of techniques) most medium hard puzzles will get an "optimized" solution with SSTS plus one Forcing Chain/Net. To avoid that techniques would have to be grouped: After Singles find all Medium Steps (Locked Candidates, Hidden/Naked Subsets) and take the best one. If none of those advances the puzzle try the rest of SSTS (plus things like turbot Variants, Finned Fish and the likes). After that chains...

All that would have to be configurable and would need a lot of testing so this looks more like a summer assignement to me than a short fix.

[daj95376]

Using your terminology:

* I have a backdoor checker in my old solver, and it turned out to be of marginal advantage. More often than not, knowing that [r5c5]=5 leads to a simple SSTS solution isn't much help in determining what to attack. All too often, it's better to attach 5s in peer cells than to attack the other candidates in [r5c5].

* I have a progress measure value for each chain/SIN in my new solver. I check to see how far the eliminations can be extended through Naked/Hidden N-tuples and Locked Candidate 1/2. This is often very effective in choosing a chain/SIN, but I still encounter situations where using two chains (with small progress measure values) is better than a single chain (with a large progress measure value).

As for difficult puzzles, my best luck has been to reduce a tri-value cell to a bivalue cell or to use an elimination to force a strong link. But this is based on a very small observation base. However, it cracked a puzzle recently posted by storm_norm.

Danny

[PIsaacson]

The problem of how to attack a difficult sudoku puzzle in a solver is an extremely interesting topic, and one that probably deserves a separate thread.

I think we can make significant improvements. For instance, I recently adopted a chaotic search algorithm for doling out cells in my subset counting engine, and it's reduced think time from hours to minutes for various puzzles.

Computer chess was once thought to never be capable of playing at a grand master's level and look where it stands now, even for PC chess games. I'm not trying to equate sudoku and chess, and game theory is beyond me, but I think there are some really smart people out there who enjoy sudoku and who could give us ideas on how to use AI (or whatever) in order to advance computer based sudoku solvers beyond collections of techniques.

Wouldn't you like to hear a HAL 9000 say someday, "Hello Dave. Would you like me to teach you how to play a game of sudoku?"

[hobiwan]

daj95376, thanks for sharing your experiences!

PIsaacson, yes solver heuristics and strategies are a fascinating topic for sure, but one that will need a great deal of trial and error (and a lot of time).

[wintder]

I still see two ways to shorten the solution paths (and both have been mentioned by other forum members in this and other threads - not my idea):

Choose steps that attack backdoors
Use the "progress measure" before applying steps

Another thought is to look at the last required "hard step" and see if it is the only one needed. Less trivial but similar is to look at the nth "hard step" and see if it could be done as the n-1th step, etc.

Just tossing pennies.

[hobiwan]

wintder, certainly worth a try!

[StrmCkr]

the nth hardest step is the intresting topic.

( i also have my views on this subject with my ideas posted on one of denis threads... have to find the link later at home)

it can be applicable at the start or superseeded by somethign else at the same time. (mutiple views at each phase or step in the solvign process)

a combination of moves equates to a solution, or a singluar move can solve a puzzle instead of many singular phases.

or its a depth nth move in which case x many specific cycles reduce the grid enough to express the n-th move.

in which cases its a full spectrum and how many of each varation a given move is applicable at each step and how many of them damage the puzzle enought to expose n faster.

i can explain this more in detail if you wish hobi wan.


i solve all applicable techniques at each given phase.
as everything is applicable.

(if a puzzle has 20 singles i find all of them and induce the reductions.)

i can count how many of each exsits.
how many actually do a reduction.

mnaually i can identify
which moves expose the n-th move.
and sepcifically what is needed to reach it.

and i can show that a n-th move is applicable. (the final blow).

and i can show that a singluar thecnique can solve the puzzle with out depth.(nth move from the get go)

(the solver limit in programing)

the only thing i cant do acuratly is depth search applictions of the same move sets one after another.

forcasting that far or to that depth takes way to much time!