Abominable TRIAL-and-ERROR and lovely BRAIDS
by 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: 1043
- Joined: 16 September 2008
- Location: Middle England
by 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
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: 2507
- Joined: 05 May 2005
- Location: Devon
by 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: 4238
- Joined: 19 June 2007
- Location: Paris
by 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: 4238
- Joined: 19 June 2007
- Location: Paris
Re: Abominable TRIAL-and-ERROR and lovely BRAIDS
by 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
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: 4238
- Joined: 19 June 2007
- Location: Paris
Re: Abominable TRIAL-and-ERROR and lovely BRAIDS
by JasonLion » Sat Mar 26, 2011 12:50 pm
-
JasonLion - 2017 Supporter
- Posts: 642
- Joined: 25 October 2007
- Location: Silver Spring, MD, USA
Re:
by yzfwsf » Thu Jan 06, 2022 1:45 pm
denis_berthier wrote:Top1465 #2 (SER 9.5) is one of the 3 puzzles (# 2, SER 9.5 - #3, SER 9.6 - #77, SER 9.8) in the top1465 collection that can be solved neither by nrczt-whips nor by nrczt-
Top1465 #3 can also be solved with only ALS AIC
Hidden Text: Show
- yzfwsf
- Posts: 921
- Joined: 16 April 2019
n dit can be
by denis_berthier » Thu Jan 06, 2022 3:15 pm
yzfwsf wrote:denis_berthier wrote:Top1465 #2 (SER 9.5) is one of the 3 puzzles (# 2, SER 9.5 - #3, SER 9.6 - #77, SER 9.8) in the top1465 collection that can be solved neither by nrczt-whips nor by nrczt-
Top1465 #3 can also be solved with only ALS AIC
And it can also be solved by g-whips.
- denis_berthier
- 2010 Supporter
- Posts: 4238
- Joined: 19 June 2007
- Location: Paris
Re: n dit can be
by yzfwsf » Fri Jan 07, 2022 2:56 am
denis_berthier wrote:yzfwsf wrote:denis_berthier wrote:Top1465 #2 (SER 9.5) is one of the 3 puzzles (# 2, SER 9.5 - #3, SER 9.6 - #77, SER 9.8) in the top1465 collection that can be solved neither by nrczt-whips nor by nrczt-
Top1465 #3 can also be solved with only ALS AIC
And it can also be solved by g-whips.
Would you please provide solution paths for #2 and #3?
- yzfwsf
- Posts: 921
- Joined: 16 April 2019
Re: n dit can be
by denis_berthier » Fri Jan 07, 2022 5:33 am
yzfwsf wrote:Would you please provide solution paths for #2 and #3?
OK, but this old thread is not the right place for doing this.
Notice that all the useful content of this thread is now written in a much more readable final form in my book Pattern-Based Constraint Satisfaction and Logic Puzzles. (https://www.lulu.com/en/en/shop/denis-berthier/pattern-based-constraint-satisfaction-and-logic-puzzles-third-edition/paperback/product-q7269p.html?page=1&pageSize=4)
I'm opening two threads in the "Puzzles" section. Before giving my solutions, I'll wait until others have a chance to propose their(s).
- denis_berthier
- 2010 Supporter
- Posts: 4238
- Joined: 19 June 2007
- Location: Paris
