Abominable TRIAL-and-ERROR and lovely BRAIDS

Advanced methods and approaches for solving Sudoku puzzles

Postby Allan Barker » Wed Oct 22, 2008 10:47 pm

denis_berthier wrote:
Allan Barker wrote:However, as mentioned in the FM thread, the "illusion of Fata Morgana" is an illusion in itself. Its illusionary difficulty can only be observed with certain solving methods. The set-solver has no problems solving the puzzle thus Fata Morgana is really a conundrum.

Here I don't agree. You suppose there is some intrinsic measure of complexity. I think this is where the illusion is.
I always speak of complexity wrt to some predefined set of rules. If one add rules, the relative complexities of puzzles can be drastically changed.

Very well put.

The view that complexity should be defined in terms of the language used to describe a system is widely held.

I believe there must be an intrinsic complexity that relates to the definition of Sudoku, or any problem. Based on this, I believe that each puzzle has an intrinsic and finite set of logical relations. It is only for us to find them.

Your view that complexity should be measured wrt to some predefined set of rules used to solve Sudoku is equally valid and maybe more practical.

The answers to some questions then depend on which point of view is used. In your view of 'specific complexity' then Fata Morgana is a more difficult puzzle than Golden Nugget wrt to the kinds of solving methods mentioned above.
Allan Barker
 
Posts: 266
Joined: 20 February 2008

Postby aran » Thu Oct 23, 2008 7:19 am

Edit 23.10.08
Garbage deleted.
Last edited by aran on Thu Oct 23, 2008 4:27 am, edited 1 time in total.
aran
 
Posts: 334
Joined: 02 March 2007

Postby ttt » Thu Oct 23, 2008 8:09 am

Deleted
Last edited by ttt on Thu Oct 23, 2008 2:42 pm, edited 1 time in total.
ttt
 
Posts: 185
Joined: 20 October 2006
Location: vietnam

Postby aran » Thu Oct 23, 2008 8:20 am

ttt
Sorry about that.
Caught out by the concision thing that I am in favour of !
aran
 
Posts: 334
Joined: 02 March 2007

Postby PIsaacson » Fri Oct 24, 2008 12:17 am

ronk wrote:
denis_berthier wrote:The nrczt-braid rule is a resolution rule. T&E is an algorithm. Saying the 2 are the same thing is therefore meaningless.

A resolution rule without an algorithm to implement the rule is meaningless. When a rule can only be implemented with a T&E algorithm, then it's a T&E rule IMO ... and the distinction between rule and algorithm becomes meaningless.

Do you have a non-T&E algorithm to implement your nrczt-braid rule:?:


Ronk,

Denis may not since his implementation is in CLIPS rules, but I'm working on one. I've already coded a C++ implementation of nrczt chains + whips with the ability to include ALS and Kraken fish groups. If one accepts that nice-loops/AIC/nrczt chains are not T&E, then the answer is YES! Well, it's almost there, just needs some tweaking/debugging/testing for a couple of weeks/months...

I just got an essential Boost bimap structure added and working during chain construction. It's used to locate braid path splits/joins after executing an unsuccessful z-target tree search. If the nrczt depth first search resulted in an elimination, there's no need to execute the braid analysis. If the DFS was unsuccessful, then I examine the bimap looking for an llc-split rlc-join with conflicts.

Sounds simple? In fact, nrczt chains is a vastly more complex algorithm than nice-loops or AIC due to z/t on-the-fly promotions. Denis's rules are elegantly simple and indeed beautiful, if one can describe logic in terms of art. That said, they are a bear to correctly implement in C++. Braids is really giving me programming grief right now, but I will debug it and get it to work.

Denis,

I hope this post contains your latest Braids concepts. I almost have just the most basic braids (bi-location bi-value splits/joins) working. I'm running 24/7 tests on extremely difficult puzzles, but I still have problems with false reductions due to incorrect conflict detection and resolution.
PIsaacson
 
Posts: 249
Joined: 02 July 2008

Postby denis_berthier » Fri Oct 24, 2008 4:39 am

PIsaacson wrote:
ronk wrote:
denis_berthier wrote:The nrczt-braid rule is a resolution rule. T&E is an algorithm. Saying the 2 are the same thing is therefore meaningless.

A resolution rule without an algorithm to implement the rule is meaningless. When a rule can only be implemented with a T&E algorithm, then it's a T&E rule IMO ... and the distinction between rule and algorithm becomes meaningless.
Do you have a non-T&E algorithm to implement your nrczt-braid rule:?:

Denis may not since his implementation is in CLIPS rules

This is not the good reason. There can be an implementation of braids as Clips rules. It's just that I haven't had time.

PIsaacson wrote:I hope this post contains your latest Braids concepts.

Depends on what "this" post is. The most general braids are the zt-FP-braids, where FP is any family of elementary patterns. As I wrote in a previous post, zt-ing is the way of including any type of pattern in a braid.
Seems difficult to define more general braids.
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Postby PIsaacson » Fri Oct 24, 2008 1:31 pm

Denis,

My bad. My limited understanding of CLIPS is that the rules are, in fact, the code. For most computer procedural languages, there is a true distinction between the abstract high level design and the actual implementation by coding. I thought Ronk was arguing that an implementation based on a T&E algorithm of braids was a "poor" choice. I was trying to convey that I am working on a non-T&E design. Again, assuming that nrczt-chains, nice-loops, AIC and the like are assumed to be non-T&E methods.

Regarding zt-FP-braids: Is the FP concept similar to what I've worked on for nrczt extentions such as ALS/Kraken almost-objects being part of the nrczt chains? In my current braids work, I have been forced to fall back to my non-extended nrczt chains. I can't seem to make the split/join work correctly if any part of the split path includes an ALS/Kraken. It's probably just another bug and hopefully not a design flaw.
PIsaacson
 
Posts: 249
Joined: 02 July 2008

Postby ronk » Fri Oct 24, 2008 1:42 pm

PIsaacson wrote:I thought Ronk was arguing that an implementation based on a T&E algorithm of braids was a "poor" choice.

I was hinting that it would be difficult to devise algorithms for nrczt-braids and whips that were not T&E. At present, I know of only one such algorithm.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby denis_berthier » Fri Oct 24, 2008 10:14 pm

PIsaacson wrote:My limited understanding of CLIPS is that the rules are, in fact, the code.

The rules ARE the code. But there's of course the inference engine to use them.

PIsaacson wrote:Regarding zt-FP-braids: Is the FP concept similar to what I've worked on for nrczt extentions such as ALS/Kraken almost-objects being part of the nrczt chains? In my current braids work, I have been forced to fall back to my non-extended nrczt chains. I can't seem to make the split/join work correctly if any part of the split path includes an ALS/Kraken.

It is still unclear for me if your inclusion of ALS in braids uses the full power of zt-ing.
If you do, you don't have to consider ALS or AHS or almost fish. You only have to consider subsets modulo the previous rlc and target.
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Postby denis_berthier » Fri Oct 24, 2008 10:20 pm

ronk wrote:
PIsaacson wrote:I thought Ronk was arguing that an implementation based on a T&E algorithm of braids was a "poor" choice.

I was hinting that it would be difficult to devise algorithms for nrczt-braids and whips that were not T&E. At present, I know of only one such algorithm.


I have already answered this, but you've obviously not read my answer.
nrczt-chains and lassos have been in existence for more than a year and they have been implemented in SudoRules since the beginning.
nrczt-whips are more recent, but they are equivalent to chains and lassos and they are implemented in SudoRules.
So, there are now at least 2 non T&E implementations of nrczt-whips.

There is one non T&E implementation of braids (Paul's) but there is no obstruction (besides my lack of time) for an implementation in SudoRules.
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Postby ronk » Sat Oct 25, 2008 1:03 am

denis_berthier wrote:
ronk wrote:
PIsaacson wrote:I thought Ronk was arguing that an implementation based on a T&E algorithm of braids was a "poor" choice.

I was hinting that it would be difficult to devise algorithms for nrczt-braids and whips that were not T&E. At present, I know of only one such algorithm.

I have already answered this, but you've obviously not read my answer.

There are other possibilities such as ... I didn't agree with your answer. Given that you and I don't even agree on the generally non-controversial definition of chain, there's little or no chance that we agree on the definition of T&E.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby denis_berthier » Sat Oct 25, 2008 1:25 am

ronk wrote:
denis_berthier wrote:
ronk wrote:
PIsaacson wrote:I thought Ronk was arguing that an implementation based on a T&E algorithm of braids was a "poor" choice.

I was hinting that it would be difficult to devise algorithms for nrczt-braids and whips that were not T&E. At present, I know of only one such algorithm.

I have already answered this, but you've obviously not read my answer.

There are other possibilities such as ... I didn't agree with your answer. Given that you and I don't even agree on the generally non-controversial definition of chain, there's little or no chance that we agree on the definition of T&E.

This thread is based on my definitions. If you don't accept them, there's nothing to be discussed here and all yours claims or comments about my results are vacuous Eureka word fighting.
My definition of a chain is as standard as it can when all the misleading inference level stuff is replaced by descriptions of factual patterns.
I claim my definition of T&E is the standard one. If you don't agree with this, then the only thing you can do is, tell what is not standard in it.
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Postby PIsaacson » Sat Oct 25, 2008 3:02 am

Dear Ronk,

I hate to step into this, but I have to ask:

What is the generally non-controversial definition of chain?
Is there a generally non-controversial definintion of T&E?

I've coded Denis's nrczt chains, and to me, they seem really similar to nice-loops and AIC except for z/t on-the-fly promotions. That makes them non-reversible, but it's also what makes them very "powerful" in terms of solving puzzles beyond the standard nice-loops/AIC capabilities. Does non-reversibility disqualify them from being chains?

Does T&E always/only involve copying the current grid, making some change(s) to the grid copy to assess impact, then back-tracking to the original grid if necessary?

These questions are really off-topic, but if you could direct me to some definitive posts, I would really appreciate it.
PIsaacson
 
Posts: 249
Joined: 02 July 2008

Postby denis_berthier » Mon Oct 27, 2008 11:44 pm



In this post, I summarise the notions necessary to define general whips and braids and I develop the consequences of the following general idea

ZT-ING or, more specifically, ZT-WHIPPING OR ZT-BRAIDING IS THE WAY OF INCLUDING BASIC PATTERNS IN WHIPS OR BRAIDS.

It is a natural, and fully supersymmetric, generalisation of the "almost-ing" principle widely used to include ALS, AALS, AAALS ..., AHS, AAHS, ...., A-Fish, AA-Fish, ..., in AICs.
Instead of almost-ing wrt to the previous right-linking candidate in the chain, it does almost-ing wrt to the target and all the previous right-linking candidates.


In the same way as my definition of a chain unifies the previously conflicting views of a chain as a sequence of candidates and as a sequence of cells (in this case of rc-, rn-, cn- or bn- cells), my definitions of a whip and a braid unifiy the research on elementary patterns with limited resolution potential and the research on more complex patterns with broad resolution potential, which have to be based on chains/whips/braids/nets.

But it should first be recalled here that all that follows is interesting only for exceptionally hard puzzles: puzzles solvable by a human can be solved by the most basic nrczt-whips.


For completeness, let me recall the main definitions.

Definition: Given a set S of candidates and an abstract elementary pattern P (e.g. a Naked-Pair or a Swordfish), we say that another set S' of candidates satisfies pattern P modulo S if, when all the candidates in S' that are nrc-linkded to some candidate in S are forgotten from S', what remains in S' satisfies pattern P.

Definition: If P is any elementary pattern, with an associated resolution rule, a candidate C is nrc-linked to P if it satisfies the conditions of the elimination rule for P.

Now, let FP be any fixed family of basic patterns.

Definition: given a target candidate z, a zt-whip(FP) [resp. a zt-braid(FP)] built on z is any sequence L1 R1 L2 R2 L3 R3 .... Ln of elements alternatively called left-linking and right-linking, where
- L1, L2 ... Ln are candidates, (as usual, it is not necessary to extend the possibilities on left-linking candidates),
- each of R1, R2, R3 ... Rn-1 is a pattern from the FP family modulo the target and the previous right-linking candidates,
- L1 is nrc-linked to the target,
- for each 1 < k <= n: Lk is nrc-linked to Rk-1 (in the above extended sense of "nrc-linked") [resp. for braids: nrc-linked to the target or to any previous right-linking candidate]; this is the first part of the chain [resp. braid] condition,
- for each 1 <= k < n, Lk is nrc-linked to at least one element of either the rc-, rn-, cn- or bn- cell containing Rk; this is the second part of the chain condition,
- there is an rc-, rn-,- cn, or bn- cell containing Ln such that there is no candidate in this cell compatible with the target and the previous right-linking candidates.
The patterns in FP are called the generating patterns of the braids zt-braid(FP).


As the families FP of generating patterns will always contain ECP+NS+HS (rules for Elementary Constraints Propagation and for Singles), these patterns will often be left implicit.

Thus, we shall write zt-braids(BI) instead of zt-braids(ECP+NS+HS+BI). These are what I've previously called the hinged-nrczt-braids or grouped-nrczt-braids.

Similarly, we shall write zt-braids(BI+SubsetRules) to mean zt-braids(ECP+NS+HS+BI+ SubsetRules). These are what I've previously called the hinged-nrczt-ALS-braids, which subsume all the nrczt-whips, all the grouped nrczt-whips and all the grouped AICs (including ALS, AALS, AAAAALS, AHS, AAAAHS, A-Fish, AAAAFish,....)


The notion of a zt-braid(FP) establishes a duality between the families FP of basic patterns and the families zt-braid(FP) of braids.


I have proven the following:

T&E(FP) vs zt-braid(FP) theorem: for any family of patterns FP with associated resolution rules, any elimination that can be done by T&E(FP) can be done by a zt-braid(FP)


The T&E(FP) vs zt-braid(FP) theorem provides an easy means of testing whether a puzzle can be solved by zt-braid(FP).

This theorem can even provide a zt-braid(FP) solution for a puzzle, built from the trace of the T&E(FP) procedure. Notice however that this solution will differ from one obtained by directly looking for patterns in four respects:
- the zt-braids thus obtained will have lots of useless branches,
- even if the zt-braids thus obtained are manually pruned of their useless branches, they won't be the shortest ones possible,
- no simpler patterns, such as whips or 2D-chains ..., will be obtained,
- more generally, contrary to what is done for the rules in SudoRules, this procedure doesn't provide any means of putting priorities on the patterns obtained.



We are now naturally led to the question:

What is the "simplest" family FP of elementary patterns such that all the puzzles are solvable by zt-braid(FP)?

I've already mentioned that one can take FP = nrczt-braids and that all the known puzzles can be solved by zt-braids(nrczt-braids), but FP = nrczt-braids is too complex to be an interesting generating family.
The following results suggest that one can find a family FP of basic patterns much simpler than nrczt-braids such that all the known puzzles can be solved by zt-braids(FP).
Of course, the same question can be asked for whips:

What is the "simplest" family FP of elementary patterns such that all the puzzles are solvable by zt-whip(FP)?

In a sense, the question about whips is more interesting, because whips are chains (no branching) whereas braids are nets (even though relatively mild ones), but it is much more difficult to deal with it.



In a previous post, I had given results for the gsf collection of extreme puzzles. Here are more detailed results for the same braids.

Code: Select all
Nb of puzzles solved by the different types of braids:

FP family............ECP+NS+HS.........ECP+NS+HS+BI..............BI+SubsetRules
Braids used..........nrczt-braids......hinged-zt-braids..........hinged-zt-LS-braids
Other name(s)..........................grouped-nrczt-braids......zt-braids(BI+SubsetRules)
.......................................zt-braids(BI)
1-500................0.................187.......................443
501-1000.............0.................178.......................460
1001-1500............0.................163.......................486
1501-2000............0.................168.......................490
2001-2500............0.................135.......................474
2501-3000............0.................116.......................479
3001-3500............1.................120.......................473
3501-4000............0.................113.......................472
4001-4500............1.................104.......................448
4501-5000............0.................231.......................482
5001-5500............47................348.......................500
5501-6000............434...............490.......................500
6001-6500............487...............500.......................500
6501-7000............494...............500.......................500
7001-7500............500...............500.......................500
7501-8000............500...............500.......................500
8001-8152............152...............152.......................152
Total................2616..............4505......................7859
Rest.................5536..............3647......................293



As zt-braids(BI+SubsetRules) subsume all the grouped whips and AICs, this will be the starting point for my further analyses of larger families of generating patterns.
Last edited by denis_berthier on Mon Dec 08, 2008 5:50 pm, edited 1 time in total.
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Postby denis_berthier » Tue Oct 28, 2008 4:48 am


Adding finned fish and x2y2-belts in the zt-braids(BI+SubsetRules).

I've been wondering about adding x2y2-belts in the family of generating patterns of zt-braids.
x2y2-belts have been defined here: http://forum.enjoysudoku.com/viewtopic.php?t=5894
They are my interpretation of Steve's pattern (also known as SK-loop).
When x2y2-belts are added to the above family of generating patterns, we get a new type of braid: zt-braid(BI+SubsetRules+x2y2-belts)

However, there are patterns simpler than x2y2-belts that should be introduced before them as generating patterns. I therefore introduced finned fish.


Code: Select all
Nb of puzzles solved by the different types of braids:

FP family............ECP+NS+HS.........+BI.......................+SubsetRules................+finned-fish................+x2y2-belts
1-500................0.................187.......................443.........................466.........................489
501-1000.............0.................178.......................460.........................480.........................497
1001-1500............0.................163.......................486.........................494.........................500
1501-2000............0.................168.......................490.........................496.........................499
2001-2500............0.................135.......................474.........................489.........................497
2501-3000............0.................116.......................479.........................493.........................499
3001-3500............1.................120.......................473.........................486.........................498
3501-4000............0.................113.......................472.........................493.........................499
4001-4500............1.................104.......................448.........................471.........................497
4501-5000............0.................231.......................482.........................494.........................499
5001-5500............47................348.......................500.........................500.........................500
5501-6000............434...............490.......................500.........................500.........................500
6001-6500............487...............500.......................500.........................500.........................500
6501-7000............494...............500.......................500.........................500.........................500
7001-7500............500...............500.......................500.........................500.........................500
7501-8000............500...............500.......................500.........................500.........................500
8001-8152............152...............152.......................152.........................152.........................152
Total................2616..............4505......................7859........................8014........................8126
Rest.................5536..............3647......................293.........................136.........................26



These results are an indication of what a generating family of patterns may be and what the resolution potential of the corresponding braids is; it is not proposed as the final answer to the questions in the previous post.
What's noticeable here again is that, for any FP family, the number of puzzles unsolved is almost constant in a broad range of the Q1 rating.
Last edited by denis_berthier on Mon Dec 08, 2008 6:04 pm, edited 1 time in total.
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

PreviousNext

Return to Advanced solving techniques