Rating rules / Puzzles. Ordering the rules

Advanced methods and approaches for solving Sudoku puzzles

Postby champagne » Thu Sep 04, 2008 10:02 am

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


A small remark regarding Denis's point. We usually (including my solver) only consider remaining candidates to work out UR clearing. I guess adding if necessary the "dummy" missing candidates to fill the UR potential pattern would make the path independant of the order (basically, you can freely add any candidate in a cell without disturbing the logic).

So the way we are working leads to the point raised by Denis, but we could overcome that difficulty.

coloin wrote: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.
.


I just started working on strmckr proposal to solve "tugston rod". A quick reading shows something very new to me, but I have to go deeper.

I had another experience with "abi" also a very skilled player. She started fighting against Golden Nugget.
She was highly surprised that her first clearing was the same as mine, using a completely different approach.
My answer has been very simple. Every process is working against weaknesses of a puzzle. No surprise if the same clearing is frequently done out of completely different paths.
The problem is that you don't move easily from one process to another one. My solver works with a limited set of rules but cover all the field, Players use a much wider set of rules, but focus on what they foresee as a potential weakness of the puzzle.


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

C


I would not say that there is no entry point in full tagging, but this is not "visible".
Denis wrote a lot about confluence.
I could say that at any time, the solver has the full confluence state with the set of rules used. (which means I experienced exactly what he describes).


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

Postby denis_berthier » Thu Sep 04, 2008 11:25 am

champagne wrote:We usually (including my solver) only consider remaining candidates to work out UR clearing. I guess adding if necessary the "dummy" missing candidates to fill the UR potential pattern would make the path independant of the order (basically, you can freely add any candidate in a cell without disturbing the logic). So the way we are working leads to the point raised by Denis, but we could overcome that difficulty.

Adding candidates requires adding rules that would add candidates.
Not only does this disturb the logic, in the sense that it changes the theory T initially considered.
It completely disrupts it, in the sense that it introduces cycles in the set of knowledge states. In the normal situation, when candidates can only be eliminated, the graph of knowledge states is a DAG (directed acyclic graph). This is a fundamental property.

champagne wrote:Denis wrote a lot about confluence.
I could say that at any time, the solver has the full confluence state with the set of rules used. (which means I experienced exactly what he describes).

The expression of a "confluence state" has no meaning. Confluence is a property of a set of resolution rules, not of a state.
denis_berthier
2010 Supporter
 
Posts: 4197
Joined: 19 June 2007
Location: Paris

Postby champagne » Thu Sep 04, 2008 1:37 pm

denis_berthier wrote:
champagne wrote:We usually (including my solver) only consider remaining candidates to work out UR clearing. I guess adding if necessary the "dummy" missing candidates to fill the UR potential pattern would make the path independant of the order (basically, you can freely add any candidate in a cell without disturbing the logic). So the way we are working leads to the point raised by Denis, but we could overcome that difficulty.

Adding candidates requires adding rules that would add candidates.
Not only does this disturb the logic, in the sense that it changes the theory T initially considered.
It completely disrupts it, in the sense that it introduces cycles in the set of knowledge states. In the normal situation, when candidates can only be eliminated, the graph of knowledge states is a DAG (directed acyclic graph). This is a fundamental property.

champagne wrote:Denis wrote a lot about confluence.
I could say that at any time, the solver has the full confluence state with the set of rules used. (which means I experienced exactly what he describes).

The expression of a "confluence state" has no meaning. Confluence is a property of a set of resolution rules, not of a state.


No comment
champagne
2017 Supporter
 
Posts: 7454
Joined: 02 August 2007
Location: France Brittany

Postby denis_berthier » Thu Sep 04, 2008 2:34 pm

champagne wrote:No comment

Very informative post.
But you may be right to make no comments. As you have rules for BUGs and URs, your system couldn't have the confluence property if it was merely the implementation of a set of resolution rules.
denis_berthier
2010 Supporter
 
Posts: 4197
Joined: 19 June 2007
Location: Paris

Postby champagne » Thu Sep 04, 2008 2:51 pm

denis_berthier wrote:
champagne wrote:No comment

Very informative post.
But you may be right to make no comments. As you have rules for BUGs and URs, your system couldn't have the confluence property if it was merely the implementation of a set of resolution rules.


again: no comment
champagne
2017 Supporter
 
Posts: 7454
Joined: 02 August 2007
Location: France Brittany

Postby denis_berthier » Thu Sep 04, 2008 3:00 pm

champagne wrote:again: no comment

When, as in the present case, you have no rational argument in relation with the topic of this thread, could you avoid spoiling it with useless posts?
Thanks.
denis_berthier
2010 Supporter
 
Posts: 4197
Joined: 19 June 2007
Location: Paris

Postby champagne » Thu Sep 04, 2008 3:56 pm

denis_berthier wrote:
champagne wrote:again: no comment

When, as in the present case, you have no rational argument in relation with the topic of this thread, could you avoid spoiling it with useless posts?
Thanks.


Can you explain what is "rational" in your recent posts??

When I don't understand something I ask for explanations I don't try to escape thru insults or strong but wrong statements

Anyway, I disapperar for one full week, so you can go ahead without me.
champagne
2017 Supporter
 
Posts: 7454
Joined: 02 August 2007
Location: France Brittany

Postby denis_berthier » Fri Sep 05, 2008 2:02 am

champagne
I've pointed out a precise and obvious contradiction between your claims: containing a rule for BUGs and having the confluence property.
I'll leave the readers decide for themselves what's rational in my posts, who doesn't understand what's under discussion with the confluence property or with rules that would add candidates and who is evading the discussion.
denis_berthier
2010 Supporter
 
Posts: 4197
Joined: 19 June 2007
Location: Paris

Postby denis_berthier » Sat Sep 06, 2008 12:49 am

Allan Barker wrote: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.

You could also calibrate your scale based only on your solving technique and see afterwards how it correlates with SER and other ratings.
Can your solver solve long series of not extreme puzzles in a reasonable time? If so, you could choose one such function F, compute the results for the 10.000 puzzles in Sudogen0 and see how computation time and/or memory vary with your parameter.
You could test several functions F, see how they correlate and which one has the best intrinsic properties.
I think nobody is in a better position than you for deciding what the most promising Fs can be.

I'll soon publish on my Web pages the full NRCZT ratings for Sudogen0. Paul Isaacsson, in another thread, will also run his new solver on this collection. We could thus have several new ratings worth comparing - and still the older ones.

I'm also preparing something on a (much smaller) collection of harder puzzles (SER between 8 and 9.2). We can therefore check how our ratings work in an extended range of complexity.
denis_berthier
2010 Supporter
 
Posts: 4197
Joined: 19 June 2007
Location: Paris

Postby StrmCkr » Sat Sep 06, 2008 9:11 pm

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.


I believe I see where the arguments are coming from.

Are you attempting to have a rating in general for all puzzles? I don’t think you should be looking at all puzzles that are unique or not.

It should be a rating system based solely on Unique Solutions. (1 possible final grid state).

This is a direct requirement for any “Puzzle” to be considered a “Puzzle” by definition of what a puzzle is considered.

Sudokus to the public: are not a mathematically 9 dimensional constraints allocations problem and mathematician’s bequeth uniqueness due to the mathematical speaking affects of such patterns. If a puzzle is none unique uniqueness patterns will remove some of the possible solutions from the total count.

A player is not trying to prove mathematically a given problem at hand has 1 pattern only. The creator of the grid should be the one verifying this.

We are told in the beginning that “Sudoku” is a “Puzzle”.

now find it given the basic lay out of constraints. (formulate patterns and resolution techniques that work)

To the public in general it is by definitions a “puzzle”. Must have 1 solution!

Any rating program should test that the grid is firstly a unique completion. If it is not a single solution don’t rate it. As it is no longer a “puzzle” but instead it is a mathematical problem of how many solutions does it contain?

most puzzles with a unique solution should have a single final state


All puzzles with a unique solution have only 1 final state.

In practice, 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.


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.


You just caught your self in your own Confluent rules as well with these paragraphs.

I have had puzzles that involve: XY-wings. Sword-fish (variants), ALS-XY, and a few other moves at one stage of solving where valid. But a found a more complex eliminations that solved some singles. I chose the more complex manipulation:

But the affect of the move I chose disabled the application of all the aforementioned moves.

The candidate state changes, but certain techniques become no longer applicable; the rules of “T” allow specific candidates to be removed by a choice of a solver.

Variance in technique(choice) is what always changes to remove that candidate later on.
Even normal techniques become no longer valid.

In particular, if T solves P, you can't miss the solution by choosing the "wrong" rule at any time.


Correct any combination of moves that solves a puzzle.
The specific removals are the parts of “T” that can be in any order.

(It’s a question of what kinds of moves are valid at each stage of solving)

{T}+ {T}… = P

If you are generalizing the above to every problem may not be unique then uniqueness should not be included for mathematical reasons, this I can agree with but I do contest your quote of that it is not “pure logic” as I mentioned below they are constructed logically but used as a limitation.

But I do believe that sudoku is a “Puzzle” and being such shall have only 1 solution

{T}+ {T}… = P (unique)

P is limited to being 1.
Thus:
T can be any move including Uniqueness limitation arguments.

To me specific moves like muti -coloring x-wings and some other patterns are actually zero placement eliminations where the cover set of the pattern is locked to prevent the zero, but the contradiction viewed is the elimination placed forces a zero the pattern to display a zero solution or multiple candidate on a field (B,R,C). therefor any basic pattern rule could also be seen as a confluent as well by avoiding the zeros or contradictions states.

what makes thes rules any better if the pattern could actually incorrectly reduce a gird to a contradiction state when it is actually a zero state instead? that is confluente as well.
i have seen this happen in testing mutiople solution grids.

…And there's no guarantee that another rule in T will do the job in their stead


This is incorrect as well. Any given move can be replicated with a more complex technique later when a removal eliminates that simpler move earlier on.

Edit: {But depending, If I miss interpret this and you are in fact saying that all sudoku problems are not unique, and should be proved that they are instead a “puzzle”, where mathematically uniqueness arguments may remove possible solutions from a final solution count, or potentially leave a multiple solution grid with zero solutions.}

{In this alternative view point I can agree that mathematically uniqueness arguments remove clues other wise non removable when proving that it is a unique solution. } end Edit}

Meaning that Specific incorrect placements are always removed {question of how}, in the path leading to completion {P}

Examples if you want them are from the same page you quoted me on. A more complex chain instead of the bug, mugs, URs is required to solve.

http://forum.enjoysudoku.com/viewtopic.php?t=3907&postdays=0&postorder=asc&start=0,

[quote]
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:[quote]

It is pure logic,

One can logically formulate arrange of clues with x many cells and create a variance of patterns that would always yield 2+ solutions in all arrangements of combinations.

Example: {basic UR}

Ab –ab
| |
ab – ab

2 formulated solutions from all points of view. Constructed logically

Then apply this directly to the definition of a “Puzzle” must have 1 solution.

Thus logically all the arrangements of candidates yielding to 2 solutions are invalid; as these are logically a limitation of being unique.

Ab –ab
| |
ab – abx--------- Ax

Being a “puzzle” l it cannot have any pattern that leaves more than one solution thus logically puzzle must have limitations of uniqueness Leaves this as the only valid path.

Ab –ab
| |
B – x--------- A

For your point of view Denis:

If I listed more path diversity a player could solve this pattern with an alternative move if they wish to.

{This is where I say there is variance in applicable techniques to apply at any given candidate state.}
Last edited by StrmCkr on Sat Sep 06, 2008 5:24 pm, edited 1 time in total.
Some do, some teach, the rest look it up.
stormdoku
User avatar
StrmCkr
 
Posts: 1430
Joined: 05 September 2006

Postby StrmCkr » Sat Sep 06, 2008 9:23 pm

my approch to solving is probably what diffrentiats me from others.

i built my solver to identify all moves at each given stage of condidates.

i can identify pairs, hidden nakes at the same time and apply all there reductions. singles,hiden naked blr.

i can find all x-wing reductions and apply them a the same time.

same with sky scraper, kytes and turbots. fish any size.

i don't identify one move and apply it.

i look at all valid moves at once and apply them at the same time.

basically i elminated
all the extra candidates or place all the given singles at the same time and there affected chains that are singles.

at each step towards completion.

creating massive cascades of elminations.
Some do, some teach, the rest look it up.
stormdoku
User avatar
StrmCkr
 
Posts: 1430
Joined: 05 September 2006

Postby denis_berthier » Sat Sep 06, 2008 10:15 pm

StrmCkr
I fear all your comments are based on a misunderstanding of my post:

1) I said I considered a fixed theory T (i.e. any fixed, pre-defined set of resolution rules) ; "solved within T" obviously means solved by a sequence of rules from T; when you say that "Any given move can be replicated with a more complex technique later when a removal eliminates that simpler move earlier on", you're merely forgetting that "a more complex technique" may not be present in the theory T under consideration; I think this is the main reason for your misunderstanding;

2) I never said the notion of a knwowledge state had anything to do with rating all the puzzles; it is a notion of pure logic, very standard in epistemic logic, it does apply to any fixed theory T and to any puzzle, with 0, 1 or more solutions; in my post, the problem of rating puzzles appears only at the end; so you are criticising your own incorrect extrapolations;

3) as for Uniqueness, I took no position about it; I said many times that it is a constraint on the creator, not on the player; but accepting or rejecting the axiom of uniqueness is irrelevant here; at best, it could manifest itself partially in T as U-resolution rules;

4) if T is incomplete the solution may not be found with rules from T; if there is only one final state in the full knowledge space, it may not be the solution; moreover, if T doesn't have the confluence property, there may be several different final states; you are confusing the notion of a knowledge state obtained via the application of a fixed set of rules with the notion of a solution; if T contains only rules for singles, the final state for many puzzles won't be their solution;

5) the confluence property is a global property of a set of rules; it doesn't mean that one rule R will still allow you to do some elimination if you apply another one before it; it means that there will be other rule(s) in T that will allow you to do this elimination; typically, in my sets of rules, a shorter chain rule (i.e. a simpler technique, not a more complex one) will apply; here again, your criticisms apply only to your misunderstanding of this notion;

6) the presence of BUG in a theory prevents it from having the confluence property, because BUG, at least as it is generally formulated, imposes the presence of some candidates; there are many known cases where BUG can be applied at some point but can no longer if you have applied other rules before it; if you have a formulation of BUG that doesn't impose the presence of candidates, I'm willing to examine it.

Subsidiarily, it wouldn't be that stupid to rate puzzles that have no solution: how hard is it to prove they have no solution? For some puzzles, this can be as hard as finding solutions (if you don't use T&E). SudoRules can do this (not for all the puzzles). But I understand it isn't a concern for players.
denis_berthier
2010 Supporter
 
Posts: 4197
Joined: 19 June 2007
Location: Paris

Postby StrmCkr » Sat Sep 06, 2008 11:50 pm

i replied via pm to this thread, i would like further explination befor i post further on here.

i do not like miss interpreting somethign that i read when it could be concived in too many ways and my above post was regarding what i found i read in the posts quoted in the above.

its not a missunderstand but an alterantive conception of what you are implying. pls correct my notions if you will via pm.

thanks
strmckr.

the problem of rating puzzles appears only at the end;
how would you find this? or even suggest this.

the problem of rating a puzzle is not the end result. it is the question of which approches and what can be utilized through each step of T that reaches p (in what ever stage it ends on)

unles your looking at all the steps used in the end and how to rate them...
Some do, some teach, the rest look it up.
stormdoku
User avatar
StrmCkr
 
Posts: 1430
Joined: 05 September 2006

Postby denis_berthier » Sun Sep 07, 2008 12:14 am

StrmCkr wrote:
the problem of rating puzzles appears only at the end;
how would you find this? or even suggest this.

the problem of rating a puzzle is not the end result. it is the question of which approches and what can be utilized through each step of T that reaches p (in what ever stage it ends on)
unles your looking at all the steps used in the end and how to rate them...

I wrote "in my post, the problem of rating puzzles appears only at the end". Isn't it clear I meant "at the end of my post"?
denis_berthier
2010 Supporter
 
Posts: 4197
Joined: 19 June 2007
Location: Paris

Postby StrmCkr » Sun Sep 07, 2008 1:04 am

again that not completly clear.. end of which post in specific.

:)and just for giggles.

if its the end of the last post it actually self loops back onto the same post implying that the solution is a loop of the same question inferancing it to its self being the explination.

hahaha....:)
Some do, some teach, the rest look it up.
stormdoku
User avatar
StrmCkr
 
Posts: 1430
Joined: 05 September 2006

PreviousNext

Return to Advanced solving techniques