Rating rules / Puzzles. Ordering the rules

Advanced methods and approaches for solving Sudoku puzzles

Postby denis_berthier » Fri Aug 29, 2008 3:25 am

Allan Barker wrote:I would like to inject my experience with such puzzles, which has left me with a different 'feeling' about SK loops. [...]
At least for EM and Strmckr's puzzle, the SK loops and a few related eliminations are relatively easy first steps after which, both puzzles become much more difficult. In the case of Strmckr's puzzle, the difficulty becomes similar to the more difficult eliminations in GN, making this puzzle much tougher than EM.
It might be that the presence of SK loops (not the loops themselves) indicates the possibility of other eliminations and assignments based on symmetry, which is not reflected in other methods (and in various rating methods).
Just interested because I shiver when I see an SK loop because I know what's next.


The presence of "SK loops" (which are not loops at all) is an "obvious" consequence of the basic and very specific symmetries inherent in the EM family of puzzles.
When I say "obvious", I don't mean to lessen Steve's merit in discovering them. They are "obvious" now that he has found them in EM.
It may be the case that the EM symmetries still hide some other "obvious" patterns. Could you be more precise on "what's next"? Could you formalise this as new patterns?


The problem with such specific patterns as Steve's is that either we put tens or hundreds of them in our solvers/raters (a new one each time a new family of hard puzzles is discovered) or we try to exploit them as much as possible and include them in a well defined family of more general rules that abstracts from the specificities of the puzzles in which they were discovered. Only in this last case can one insert them in a non arbitrary way in an existing hierarchy of rules.
In this last case, one can consider two approaches.

First approach:
In the "x2y2-belts" thread (http://forum.enjoysudoku.com/viewtopic.php?t=5894), I gave two possible (a priori non equivalent) general formalisations of Steve's pattern. I tried to find similar puzzles with longer belts. It doesn't seem to be possible with 9x9 Sudoku, but it is obviously with 16x16 - which may be an indication that we should start considering 16x16 or larger puzzles.
The conclusion is that x2y2-belts don't seem to be general enough to provide a whole family of rules for 9x9 puzzles.

Second approach:
What remains puzzling in Steve's pattern is that it seems to require considering:
- "plugging two candidates at a time" (coloin's vocabulary)
- "paired propagation" (strmckr's vocabulary)
- "double proposition pair technique" (strmckr's vocabulary)
- two simultaneous targets (my vocabulary)
Now, one could try to define general rules based on 2 targets instead of 1 (e.g. nrczt-bi-chains); but such rules are likely to have very high computational complexity (less than the most general nrczt-nets, but still high).


Between the two approaches, one may try to define a restricted type of such chains. This is still open.
denis_berthier
2010 Supporter
 
Posts: 4234
Joined: 19 June 2007
Location: Paris

Postby RW » Fri Aug 29, 2008 6:46 am

champagne wrote:'abi ' produced a chain close to yours, maybe still more difficult to include in a solver. Sorry, this is in chess mode, but I guess you can manage it.


Code: Select all
*7b9/23b9-23ab8/23h8-1579h1238/9h56-9g5/9c5-15c57/15c8-7c8/7b9 et fin.


I am sure that 'abi' is working without any computer, so I find very impressive what she can produce.

That's an interesting alternative solution! Shouldn't be that much harder for a solver program, because the naked quad can be replaced with three consecutive hidden singles:
Code: Select all
... - 23r8c8 = 2r7c8 = 3r5c8 = 4r6c8 = 9r5c7 ...

The main difference from an algorithmic point of view would be that this chain need a naked pair (r57c3 - 15r8c3), whereas the pair my chain used (r8c12 - 23r8c8) also can be viewed as locked candidates.

RW
RW
2010 Supporter
 
Posts: 1010
Joined: 16 March 2006

Postby champagne » Fri Aug 29, 2008 10:57 am

RW wrote:That's an interesting alternative solution! Shouldn't be that much harder for a solver program, because the naked quad can be replaced with three consecutive hidden singles:
. . .
The main difference from an algorithmic point of view would be that this chain need a naked pair (r57c3 - 15r8c3), whereas the pair my chain used (r8c12 - 23r8c8) also can be viewed as locked candidates.



As wrote Denis earlier, a solver will generally not follow the path found by a human player. So you are likely right when you write that an alternative chain, longer but simpler would be used.

I faced the same problem a few years ago when analysis of couples of ALS appeared. In fact, my solver has an equivalent path using AHS/ACs.

Regarding the possibility to include groups like 23r8c8, I am sure it would be difficult in my lay out.

In my basic process, I only consider homogeneous groups (only on digit). I have extended the scope to any group of cells belonging or not to the same unit, but I stick for the time being to one digit.

I have introduced one year ago heterogeneity with couple tags creating super candidates for an AC2, but this is very specific.

I started also a blind heterogeneity two or three month ago considering any couple of tags, and I am publishing examples here

http://forum.enjoysudoku.com/viewtopic.php?t=5752

(first example should come this afternoon)

The problem is that in blind mode, you have to consider more than n² possibilities if ‘n’ is the number of candidates and groups of candidates. This is not feasible. One has to find clues to extract a subset of the overall field. I am working on that concept.

Champagne
champagne
2017 Supporter
 
Posts: 7465
Joined: 02 August 2007
Location: France Brittany

Postby Allan Barker » Sat Aug 30, 2008 1:51 am

Denis wrote:
Could you be more precise on "what's next"? Could you formalise this as new patterns?

"What's next" refers to the fact that my program first finds the SK loops, after which I don't see anything similar or symmetrical, and the eliminations get more difficult but relatively ordinary.

It might be helpful to have a rating, at least for elimination logic, that's independent of solving methods and one preferably with units. The simplest example is size. Any elimination can be described in terms of nodes, sets (Sudoku constraints), and permutations. One could look at various functions F(nodes, constraints, permutations) and correlate with other ratings. permutations also reflect such things as branching and nodes per set, which can also be used. One could also use the current SE ratings and methods (which embody a lot of experience) to help calibrate such a scale, which would be interesting on its own.

Of course, this is only one piece of the problem, to rate a puzzle you still need to apply a method and you are back to square one. However, at least there would be a reference to rate specificities like SK loops. Even if SK loops are implemented into a solver, how do they then relate to that solver's difficulty scale? Without an absolute scale to help, it probably goes back to computation time and or experience.

For example, such a scale might be something like R(absolute) = n*(p-1)+1. or maybe R = sqrt(n*n*(p-1))+1. where n is the number of nodes and p is the average number of nodes per set (strong inferences), p-1 represents difficulty related to branching, and the R = 1 for all singles. If someone estimates n and p for SE methods it would be easy to see how such functions correlate with SE ratings.
Allan Barker
 
Posts: 266
Joined: 20 February 2008

Postby StrmCkr » Mon Sep 01, 2008 12:50 pm

i belive i seen a request for m3 puzzles on here.

{note- i am working on a large conciese responce for this thread at colins request}

heres a few:

Platinum Blonde 003050009400100000080007000030005008000030920000000060005060002700004000810000000

Tungston Rod 020000700006080100700003004000060000300005010008200000005000090000500040900001300

weekender1 020006700006000000708010000040500030010090000600004200004007800000000090000030005
Some do, some teach, the rest look it up.
stormdoku
User avatar
StrmCkr
 
Posts: 1433
Joined: 05 September 2006

Postby champagne » Mon Sep 01, 2008 2:28 pm

StrmCkr wrote:i belive i seen a request for m3 puzzles on here.

{note- i am working on a large conciese responce for this thread at colins request}

heres a few:

Platinum Blonde
Tungston Rod
weekender1 5


Hi strmckr,

these three are part of what coloin just posted in the "hardest" thread.

The ranking seen by my solver (bottom up)

Tungston Rod
Platinum Blonde
weekender1


all of them far form my list of hardest

ps: I have to check the results because I made changes in my process, but I remenber having solved PB months ago with similar ranking.
champagne
2017 Supporter
 
Posts: 7465
Joined: 02 August 2007
Location: France Brittany

Postby StrmCkr » Mon Sep 01, 2008 4:45 pm

yeah i know that:)

champagne

i saw a request of M3 class puzzles (back door size three) frm denis to see if his version of solving. proves something on them he didnt see befor.

. and the hardest thread has all of the ones known to date listed in it.

i grabed the easiest ones to find {edit... on that thread, not easiest ones that are known}

(which happend to be the vary list colin listed last) there is a few more buired in that thread, i didnt have time to look or check for them. colin can you find them?
Last edited by StrmCkr on Tue Sep 02, 2008 7:14 pm, edited 1 time in total.
Some do, some teach, the rest look it up.
stormdoku
User avatar
StrmCkr
 
Posts: 1433
Joined: 05 September 2006

Postby champagne » Tue Sep 02, 2008 1:52 am

StrmCkr wrote:
i saw a request of M3 class puzzles (back door size three) frm denis to see if his version of solving. proves something on them he didnt see befor.

i grabed the easiest ones to find


All three are harder than your's having a very strong SER... and none has the SK loop.

So I suspect they are out of the scope of denis's solver.:(
He likely needs M3 puzzles easier to solve if they can be found.


In each case,my solver works a lot at level 4 (AC2 and "couple tags"/"super candidates") to find a solution.

Let me know what you found when you will have solved the first.
champagne
2017 Supporter
 
Posts: 7465
Joined: 02 August 2007
Location: France Brittany

Postby tarek » Tue Sep 02, 2008 4:55 am

The q2 taxonomy list has all the puzzles you need, choose an M3 puzzle with lowest q2 rating.

tarek
User avatar
tarek
 
Posts: 3762
Joined: 05 January 2006

Postby StrmCkr » Tue Sep 02, 2008 11:17 pm

My questions and argument for rating a puzzle derives from this and many other examples puzzles.

Code: Select all
*-----------*
 |..9|8.6|.3.|
 |684|...|.1.|
 |...|1..|...|
 |---+---+---|
 |.2.|...|98.|
 |4..|...|..3|
 |.76|...|.4.|
 |---+---+---|
 |...|..5|...|
 |.4.|...|725|
 |.3.|7.8|1..|
 *-----------*


{The initial states of this puzzle are comprised of hidden-naked singles with some box line interactions.
Reducing the grid to the following.}

Code: Select all
 *-----------------------------------------------------------*
 | 7     1     9     | 8     5     6     | 4     3     2     |
 | 6     8     4     | 3     7     2     | 5     1     9     |
 | 3     5     2     | 1     49    49    | 8     7     6     |
 |-------------------+-------------------+-------------------|
 | 15    2     3     | 56    146   14    | 9     8     7     |
 | 4     9     18    | 2     18    7     | 6     5     3     |
 | 58    7     6     | 59    389   39    | 2     4     1     |
 |-------------------+-------------------+-------------------|
 | 12    6     7     | 4     12    5     | 3     9     8     |
 | 189   4     18    | 69    1369  139   | 7     2     5     |
 | 29    3     5     | 7     29    8     | 1     6     4     |
 *-----------------------------------------------------------*



How can a person actually surmise a rating of any kind?

When a number of moves or sequences of steps can be used to remove the same clue from any particular cell?

Or perhaps a move can even be used to find something that was overlooked by said player?

A hidden single can be seen not only as its self, but instead could be found or noticed through a list of options:

Perhaps pointed out by a pair of locked cells or triples or quads, quintuples. {That is if the person missed the single}. As they both exists simultaneously.

Take the above puzzle after singles are placed:

Simple sudoku labels the next valid move as a “multi-coloring”

Where R4c1, R5C5, R8C3 <>1

It is in fact not the only move viable to make the same eliminations or similar.

There are several. {Not all are included here}

{A smattering of examples}

Disjointed subset: or this move as Remote pairs, and is also considered a skyscraper: {written as an AIC}

(1=8)R5C3 – (1=8)R5C5 - (1=2) R7C5 – (1=2) R7C1 => R4c1, R5C5, R8C3 <>1,

Disjointed subset: this moves seen as an AIC:

(2=9) R9C1 – (2=9) R9C5 – (2=1) R71C – (2=1) R7C5 =(8)5C5=(1) R5C3= (8)R8C3 => R4c1, R5C5, R8C3 <>1,

Kraken:
(1) R8C6 = (8)R8C3 = (1) R5C3
|
(3) R8C6 = (9) R6C6 = (5) R6C4 =(8)R6C1 =(1) R5C3
|
(9) R8C6 = (4) R3C6 = (1) R4C6 =(8)R5C5 =(1) R5C3

=> R4c1, R5C5, R8C3 <>1,

“Zero solution patterns” * my view of coloring & fish pattern reductions {something similar to forcing chain}

{There are also 4 turbo fish patterns based around the conjugated pairs of 1&8 I have not listed}

(1) R8C3=(8)R5C3=(1) R5C5 =(2) R7C15 contradiction. => R4c1, R5C5, R8C3 <>1,

For any grid:
A person with many refined techniques and skill should be able to find all/ or most of the applicable options then “execute” the one with most affects on a grid to either:

A: Gain a plethora of other moves and perhaps a variance in techniques.

B: opened up a shorten path of steps that are increasing in effectiveness but not necessarily ease of use.

So how do we compare any given puzzle to that of what a human player can see on any particular grid, if the skill of any player is not necessarily identical to another and in conjunction with the fact many different techniques can remove identical clues from identical cells, require different skill levels to utilize or master?

My suggestions for a rating system are a two-fold approach. And also addresses some of the issues I point out above.

Starting with a player:

For me difficulty of a puzzle is caused by a bottleneck of events, As the availability of techniques diminishes the more complex a move is forced to become with a direct limit in operands for it to execute upon.

With increased limitations of available techniques a larger range of potential players are less likely to find the next maneuver to continue onwards in a puzzle. This is apparent in the examples seen above. More viability of move spotting equates to more variance in skill acceptable to solving the puzzle.

The amount of applicable memory storage and recollection required for some techniques also can limit the range of players whom can visually ague the information and process these givens to completion.

The limitation of space has an impact on players as well, if a puzzle requires a technique that only accompanies specific cells at a particular stage of solving: then a player has only one option and it is a question of spotting it that becomes the issue. Fewer people will find the technique and more will not locate it at all.

Computer approach to mimic a range of players:

A computer can list all viable moves for each puzzle, at each step (phase) of subsequent sequences {applied techniques}.

The rating of specific techniques should be based on spatial requirements; {mentioned above: recapped} the more memory it takes to retain data to perform the move directly correlates to difficulty in usage and directly limits the number of people that can utilize the technique equals a more difficult technique.

Simplicity Rating: {Solution with fewest steps}

A computer may be programmed to check all possible paths and choose the one with less steps through comparing # of steps.

First a program must find the shortest sequence of steps, once that sequence of steps are found; it has to look at each phase of the process and list out all the identical/similar techniques that can accomplish the same elimination.

The higher the number of different techniques applicable at each phase can indicate more range of people with a variance in skill to solve this phase, but is limited by skill levels applied through direct relation to the skill required for said techniques.

{[(#Technique * (its rating)] + [(#technique) * (its rating)]+ … }

/ #{Different techniques}


Tabulation at each phases added together /# steps = rating of simplicity:

For example:

5 easy and 5 medium (step 1)
3 hard techniques (step 2)
1 very hard (step 3)
1 very hard (step 4)
1 insane (step 5)
5 easy (done: step 6)

[(5 * 1)+ (5 * 2)]/ 10 = 1.5
(3 * 6) / 3 = 6
(1 * 10) / 1 = 10
(1 * 10) / 1 = 10
(1 * 20) / 1 = 20
(5 * 1) / 5 = 1
Total = 48.5 / 6

Simplistic rating: 6 phases averaging 8.08 per

Complexity Rating: would be calculating the above to all possible variations of solutions then averaging that against number of solution variations.

Comprehension Rating: Comparison between the two ratings:

A comprehension rating would find the rating for any solver on average to find a solution, by noting the variances between the two ratings.

For example: 30 ways to solve the above: with 10 phases {average} each phase averaging 4.52

Would be a longer but less complex way of solving the puzzle compared to the simplistic approach. = Not hard on average.

For example: If there is 30 ways to solve the above: with 7 phases {average} with each phase averaging 9.81.

Would indicate that the puzzle is considerably harder at each phase to the average solver; and directly indicates the average solver will have a lot of difficulty solving as the availably of techniques and memory constraints are applied; but it can be simplistically solved occasionally with short easier steps then the average would indicate. (1 in 30 paths at phase one)

For example: 30 ways to solve the above: with 10 phases {average} each phase averaging 9.81.

Would indicate a puzzle with many complex steps and harder then the 7-step example due to extra phases but identically in the description listed for that example.

For example: 10 possible solutions with 8 phases {average} with each phase averaging 9.81

Would indicate a puzzle with few available solution paths to start with and subsequent steps are difficult.

But its limitation of variance in number of solutions choices would indicate a solver has a 1/10 chance of finding that technique used in the “6” phase completion at phase 1, and potentially solve it easier then the average indicates.

Over view:

Simplicity rating: (steps count) phases; (formula) average per phase

Formula:

{[(#Technique * (its rating)] + [(#technique) * (its rating)]+ … }

/ #{Different techniques}

Complexity Rating: # solutions; (phase) average, (formula2) average per phase

Solution counts: shows how many different paths are available at the start of a puzzle.

Phase count: # of phases required on average

Phase average: Degree of complexity at each step required on average. Larger number = harder techniques required at each phase.

Phase formula:

Sum (Phases) / # solutions

Formula2:

Sum (formula) / # solutions

Comprehension Rating:

Number of Solutions Vs. Simplistic:
Higher # of solutions is a decreased chance of finding the simplistic route at phase one.
Lower # of solutions is an increased chance of finding the simplistic route at phase one.

Phase count Vs. Simplistic: # of phases required on average. Can be more or equal to the Simplistic rating count. Indicates how many phases the average person could require solving the puzzle.

Phase average Vs. Simplistic: can be higher or lower then the average of the simplistic route.

Lower # = wider range of techniques applicable at each phase and wider range of people can solve it.
Higher # = fewer techniques can be used and fewer people will solve.

additioal thoughts:

if the simplist rating of a puzzle has more then one shortest path aplicable

then a solutions count should also be included.
then the average of each of the vible grids should be tabulated the same in the same mannerizm as the complexity rating.
Some do, some teach, the rest look it up.
stormdoku
User avatar
StrmCkr
 
Posts: 1433
Joined: 05 September 2006

Postby denis_berthier » Wed Sep 03, 2008 4:56 am


StrmCkr

Many interesting ideas. I'm looking forward to seeing such an ambitious rating at work.
I think its computational complexity and memory requirements would be very high (if only it was possible to program it). Moreover, it wouldn't correspond to the strategy of many players.
Looking for the really simplest solution would require a full look ahead, not only looking at the next step. (It is the well known problem of a sequence of local optima leading to a global non optimum).
Do you have any implementation plans?

Personally, I don't believe in any universal rating and I'll stick to ratings with more limited goals, as stated in one of my previous posts. Of course, I'll keep aware that any rating has limited validity.

What I observe when I solve puzzles with SudoRules is that, although the basic principles are very different and it has almost no rules in common with SE, the SER rating gives a pretty good indication of how hard it will be to solve it with SudoRules (up to SER 9.3). This "pretty good indication" is measured precisely by the correlation between the 2 ratings (0.73). Now, I also think SER shouldn't be used to rate exceptionally hard puzzles it was obviously not designed to rate.

One problem you don't mention in your post is Uniqueness rules. I've always discarded such rules, because I think they are not necessary and uniqueness is a constraint on the puzzle creator, not on the player. Uniqueness should be proven by the player.
But there is another reason for not using Uniqueness rules in a rater:
the presence of Uniqueness rules makes the whole set of rules non confluent, i.e. an elimination done before a uniqueness rule may make an elimination it would have allowed definitively impossible. (Particular counter-intuitive case: adding a clue to a puzzle may make it more complex). This makes rating much more complex.
In spite of having Uniqueness rules, SER is not so bad. Why?
denis_berthier
2010 Supporter
 
Posts: 4234
Joined: 19 June 2007
Location: Paris

Postby StrmCkr » Wed Sep 03, 2008 2:51 pm

Moreover, it wouldn't correspond to the strategy of many players.


this is true and false, no one can guess at to the skills of a player, or even guess at which move they would choose first.

which is covered by the concepts of these three ratings.

Simplistic:
Complexity:
Comparison:

i believe it comes down to the techniques they can implore. meaning not every player can see the same move.

thats why i developed the complexity rating.(concepts)

which would calculate the total possible number of ways to solve a puzzle then subsequently explore the options at each step generating a rating per phase then give the average rating per phase as well as a solution count.

this would indicate what any player could expect at each level of solving, ranging from easy to hard per given move.

Personally, I don't believe in any universal rating and I'll stick to ratings with more limited goals, as stated in one of my previous posts. Of course, I'll keep aware that any rating has limited validity.


i agree as well. that is why i created the comparison rating

as i too can concede the random finding aspect that some solvers find by accident or randomly and created the comparison aspect. to show that a player could solve a puzzle easier then normal if they found a path of simplicity.

the comparison rating would also indicate that any player with unknown skill could coincidently solve a puzzle easier then the average or faster then the average complexity suggests(less phases,easier steps).

ut there is another reason for not using Uniqueness rules in a rater:
the presence of Uniqueness rules makes the whole set of rules non confluent, i.e. an elimination done before a uniqueness rule may make an elimination it would have allowed definitively impossible. (Particular counter-intuitive case: adding a clue to a puzzle may make it more complex).


i never mentioned if a uniqueness argument is subjective, i would classify the move as a skill level of players and personal choice to use as well.

symmetrical placements also fall in the same category as well as some can be defined by uniqueness as well.

i am neither yeah or nay on the use of many of these concepts. bugs,mugs, UR.

personally i don't like using them, i rather prove uniqueness my self as well.
(i just don't like assuming it does have one solution)

but it is given that a puzzle must only have 1 solution to be a puzzle.
given that notion

uniqueness patterns can be utilized as a tool as well.

Particular counter-intuitive case: adding a clue to a puzzle may make it more complex)


i do have an interesting post on this thread as well. http://forum.enjoysudoku.com/posting.php?mode=quote&p=60754


the problem is how rate moves, i believe a rating system cannot seclude uniqueness arguments because a number of people will still utilize the settings, and other don't use it.

which would create a divide in ratings.

should it be a mechanic that can be deactivate? giving with or without ratings.

i also find that a puzzle solver may find an easier to utilize uniqueness pattern over some complex chain,

and if its not included in phases of solving then the rating of a puzzle can or would increase as well. (shown by those examples in that thread)

which is in the direct relation to number of techniques applicable at a given phase of solving.

Do you have any implementation plans?


not at the moment i lack programing skills.:(

i am mostly a manual solver

the most i have to date is an excel program i written that finds singles/pairs/ fish patterns/blr. {currently working on disjointed subsets and locked sets, simplistic AIC.}

i am suggesting many of these concepts based on personal work.

i found with programing the above that many reductions are a compilation of many reductions at the same moment. meaning many things removed the same clue or pointed out singles at the same time.
Some do, some teach, the rest look it up.
stormdoku
User avatar
StrmCkr
 
Posts: 1433
Joined: 05 September 2006

Postby denis_berthier » Thu Sep 04, 2008 1:40 am


THE CONFLUENCE PROPERTY


Choose a fixed set of resolution rules: T.

Starting from a given puzzle, you can apply different resolution rules from T. For each choice of a rule, you get a new state (values + candidates).
Considering all the states you can get in iterating this process, and putting an arrow between two states if there is a rule leading from the first to the second (a resolution step), you get a graph of "knowledge states". A knowledge state is just what you can see on a grid (values + candidates), what you can know about it, at some point in the resolution process along some resolution path.

A final state is a state in which no rule can be applied. Normally, most puzzles with a unique solution should have a single final state, if T is sufficiently powerful: the solution. But this is not always the case, depending on T.

In the first edition of my book, I've introduced the concept of confluence. I've already mentioned this several times, but let me add a few words in relation with rating.
Definition: a resolution theory T has the confluence property if any two partial resolution paths can be completed to meet at a same knwoledge state.
Consequence: if a resolution theory T has the confluence property, then for any puzzle P there is a single final state and all the resolution paths lead to this state. In particular, if T solves P, you can't miss the solution by choosing the "wrong" rule at any time.

I've also proved that all the resolution theories introduced in my book - based on the xy(z)(t) or nrc(z)(t) chain rules together with a few elementary rules - have the confluence property.

One important consequence of the confluence property is that you can super-impose on T any ordering of the rules you want (giving priorities to the rules is not part of first order logic). It won't change the state you'll finally get to. In pratice, this means that, if you have missed some elimination while you were using a more complex rule (to assert values or eliminate candidates), the rules in T will always allow you to do this elimination later. Still more concretely, it means that you, as a player, don't have to care about the order in which you apply the rules in T. This is a huge simplification in your player's life. And I think it is also a huge simplification if one wants to define a rating based on the rules in T.

One unpleasant property of the rules based on the axiom of Uniqueness is that any theory which contains any of them looses the confluence property. BUGs or URs may be applied in some knowledge state but not later. And there's no guarantee that another rule in T will do the job in their stead.
A practical consequence on rating puzzles is that Uniqueness rules should be applied "as soon as possible", which obliges one to give them a high priority - higher than they should normally have wrt to rules obviously simpler.
I'm neither pro nor anti uniqueness in practice (although I never use it in SudoRules), but it has this objective disadvantage from a theoretical POV.

Thanks StrmCkr for pointing out this thread http://forum.enjoysudoku.com/viewtopic.php?t=3907&postdays=0&postorder=asc&start=0, where extreme cases of this problem are given: puzzles that get harder when one clue is added. "gets harder" implies that: if harder rules are not considered in T, then P can't be solved within T, whereas a puzzle with fewer clues can; this is very counter-intuitive.
See e.g.this very smart example by claudiarabia:

This puzzle:
Code: Select all
. . 7 . 1 . . . .
. 5 . 6 . 9 . . .
8 . . . . . 4 . .
. 6 . 2 . . . 5 .
1 . . . 3 . . . 9
. 9 . . . 7 . 4 .
. . 2 . . . . . 8
. . . 9 . 4 . 6 .
. . . . 5 . 1 . .

has SER = 7,1

If you drop n9r5c9, then the puzzle you obtain:
Code: Select all
. . 7 . 1 . . . .
. 5 . 6 . 9 . . .
8 . . . . . 4 . .
. 6 . 2 . . . 5 .
1 . . . 3 . . . .
. 9 . . . 7 . 4 .
. . 2 . . . . . 8
. . . 9 . 4 . 6 .
. . . . 5 . 1 . .

has SER = 4.7

Remember that SER contains Uniqueness rules.
Of course, the NRCZT rating can't be decreased (in this special case, it is unchanged: 3).
denis_berthier
2010 Supporter
 
Posts: 4234
Joined: 19 June 2007
Location: Paris

Postby coloin » Thu Sep 04, 2008 6:18 am

Very valid points. I believe uniqueness methods are ignored in sx9/sxt. But logically they would appear to be acceptable methods.

If it were possible to analyse/see the unavoidable sets in the [incorrect] solution grids it would be possible to advance all puzzles with uniqueness methods - but this is not feasible.

Perhaps it is only worth rating puzzles which are human-solvable.
Can StrmCkr solve hard puzzles ? If so how does he do it ?

If we can replicate his solving method we can try to devise a program which assesses this. Champagnes solver goes a way doing this.

Chosing the "tagging" entry point of a puzzle I envisage is a sticking point !

C
coloin
 
Posts: 2502
Joined: 05 May 2005
Location: Devon

Postby denis_berthier » Thu Sep 04, 2008 6:46 am

coloin wrote:I believe uniqueness methods are ignored in sx9/sxt. But logically they would appear to be acceptable methods.

I don't know about sx9/sxt.
As for validity, it is not a matter of logic but of choice: EITHER you accept the uniqueness axiom and then you accept the rules based on it OR you don't.
The motives for one's choice may be varied but they can't be based on pure logic. My personal main motives for not using such rules are:
- non confluence (as stated above, this is a real nuisance),
- rarely useful if given a classification consistent with their complexity - i.e. with low priority.

coloin wrote:Perhaps it is only worth rating puzzles which are human-solvable.

It depends on one's goals. People working on the hardest puzzles (to date) may find useful to rate them.
But I'd say that any rating should first of all rate correctly (at least in a statistical sense) the human-solvable puzzles.
denis_berthier
2010 Supporter
 
Posts: 4234
Joined: 19 June 2007
Location: Paris

PreviousNext

Return to Advanced solving techniques