Abominable TRIAL-and-ERROR and lovely BRAIDS

Advanced methods and approaches for solving Sudoku puzzles

Postby David P Bird » Sun Nov 23, 2008 11:52 am

Coloin, I'm not sure of what you mean about locating this puzzle's weak spot! Although its bilocal & bivalue counts are low, it has a useful set of ALS/AHT pairs which provide sufficient routes to carry inferences around the grid. This is what makes it susceptible to my restricted method set. However, I don't think a continued discussion along such lines would be very welcome on this thread.
David P Bird
2010 Supporter
 
Posts: 960
Joined: 16 September 2008
Location: Middle England

Postby coloin » Sun Nov 23, 2008 1:04 pm

I agree, but we have both shown the same insertion by different means.

Your right, a puzzle's weak spot is an intriqing concept - a bit like the most "elegant" move ! I am sure denis agrees with this concept, however indefinable !

My slant is the relative contribution to a puzzle of all the clues. My methods are certainly "Abominable":(

In a minimal puzzle of course all the clues are necessary but in an easy puzzle you get eliminations with just a few clues.

In a very hard puzzle mabe one clue is not quite as necesasary as the rest. This is the case here. The lack of the 4@r7c9 is still only compatible with the inserted clue value of the 8@r8c2. There will be many ways to show this [as you did] because it is true ! Whatever way you do it it does not require "information" from the 4@r7c9.

C
coloin
 
Posts: 1638
Joined: 05 May 2005

Postby denis_berthier » Sun Nov 23, 2008 7:37 pm

coloin wrote:Your right, a puzzle's weak spot is an intriqing concept - a bit like the most "elegant" move ! I am sure denis agrees with this concept, however indefinable !

I agree with both the idea of "elegance" and the "undefinable".

coloin wrote:My slant is the relative contribution to a puzzle of all the clues. My methods are certainly "Abominable":(

Abominable from one POV (e.g. T&E) maybe more acceptable from another (braids).


If we add the clue n8r8c2, SER collapses to 9.2 (instead of 9.5) and the puzzle can be completely solved by whips of length <= 12.
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Postby denis_berthier » Thu Dec 04, 2008 1:45 am


About the T&E Theorems


Question from a French friend (my translation) wrote:Isn't there a contradiction between the two theorems you proved in relation with T&E:

Taken from the "concept of a resolution rule" thread, second post http://forum.enjoysudoku.com/viewtopic.php?t=5600:
denis_berthier wrote:Definition: T&E is the following procedure: recursively make ad hoc hypotheses on something that you do not know to be true at the time you make them, explore their consequences, with the possibility of retracting each of these hypotheses and their consequences if they lead to a dead end.

Theorem: Trial and Error is a resolution technique that cannot be the implementation of any resolution rule.


Taken from the "abominable T&E and lovely braids" thread, second post http://forum.enjoysudoku.com/viewtopic.php?t=6390:
denis_berthier wrote:T&E theorem: ANY ELIMINATION DONE BY T&E CAN BE DONE BY AN NRCZT-BRAID.
...
Corollary: ANY PUZZLE SOLVABLE BY T&E IS SOLVABLE BY NRCZT-BRAIDS.




Thanks for asking. I wans't aware that this wasn't obvious. The two procedures are different.
There may seem to be a contradiction, due to the very bad name I chose in the first case for the procedure I was defining.
But, the two theorems are true and non contradictory. We must just be careful about names.


The two definitions and associated theorems are recalled here (only the name of the first procedure is changed, the definitions and proofs given in the two aforementioned threads remain unchanged):

1) "Concept of a resolution rule" thread:
What I've called T&E and then rT&E in the first thread, and which should be called something like RTEG "recursive T&E with guessing" is any structured search procedure (DFS or BFS) with no a priori depth limit, and accepting positive results (if it finds a solution, it accepts it - which is a form of guessing).
RTEG theorem: RTEG is a resolution technique that cannot be the implementation of any resolution rule.
RTEG theorem (strong form): RTEG is a resolution technique that cannot be the implementation of any set of resolution rules.

This can be extended to any RTEG(T), for any resolution theory T, where RTEG(T) means the search is pruned by the rules in T.



2) "Abominable T&E and lovely braids" thread:

Definition: Given a resolution theory T (i.e. a set of resolution rules) and a candidate z, T&E(T, z) is the following resolution technique:
- start an auxiliary grid by copying the current PM; in this auxiliary grid, delete z as a candidate and add it as a decided value; apply to this auxiliary PM all the rules in T until quiescence;
- if a contradiction is thus obtained in this auxiliary PM, then eliminate z from the original one; if no contradiction is obtained, then merely go back to the original PM.

I think this is what everyone means by "using T&E(T) to eliminate candidate z".

Definition: Given a resolution theory T, T&E(T) is the following resolution technique (this is only conceptual, any implementation should optimise this):
a) define phase = 1;
b) apply all the rules in T;
c) set changed-PM = false; mark all the remaining candidates as "not tried";
d) if there is at least one "not-tried" candidate, then choose any of them, say z; apply T&E(T, z); if it eliminates z, then set changed-PM = true and apply all the rules in T, otherwise un-mark z; in both cases, goto d;
e) if there is no not-tried candidate:
----------- if changed-PM = true, then set phase = phase +1 and goto c);
----------- if changed-PM = false, then stop.
Said otherwise, repeat T&E(T, z) for all the candidates z, as long as any one remains, until quiescence.

T&E theorem: Any elimination done by T&E can be done by an nrczt-braid.
T&E theorem: Any elimination done by T&E(T) can be done by an nrczt-braid(T).



3) Differences between the two procedures:
In the second case:
- there's no recursion (although we can also define a depth 2 T&E, but it won't be unlimited recursion).
- no "guessing" is allowed: if a solution is found in the auxiliary PM, it is merely forgotten.
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Re: Abominable TRIAL-and-ERROR and lovely BRAIDS

Postby denis_berthier » Tue Nov 30, 2010 3:53 pm

The missing pages of this thread, lost due to the May 2009 crash, are available on my website:
http://www.carva.org/denis.berthier/HLS/SPF/TEB/index.html

Note 1: at the time I made this backup, it was for my private use only (I couldn't imagine the previous managers of the forum didn't make backups) and I didn't care about compatibility with browsers other than Safari on my Mac. It is therefore in the webarchive format. But it can be read most easily on Windows by first downloading Safari for Windows. For other ways of reading them, see the "real distribution of minimal puzzles" thread in the "general" section.

Note 2: I put these old Forum files online, as a historical reference, but a synthesis of all this has been available for a long time on my usual web pages for those who are not interested in details: http://www.carva.org/denis.berthier/HLS/index.html
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Re: Abominable TRIAL-and-ERROR and lovely BRAIDS

Postby JasonLion » Sat Mar 26, 2011 12:50 pm

Thanks to denis_berthier we now have PDF files of posts made to this topic between November 2009 and January 2010.

Page 8
Page 9
Page 10
Page 11
Page 12
Page 13
Page 14
Page 15
User avatar
JasonLion
2017 Supporter
 
Posts: 624
Joined: 25 October 2007
Location: Silver Spring, MD, USA

Previous

Return to Advanced solving techniques

cron