Forcing Chains

Advanced methods and approaches for solving Sudoku puzzles

Postby gsf » Wed Mar 28, 2007 5:46 pm

ronk wrote:I don't see an answer to my question in there anywhere. Are you saying f4#5 is part of an almost-locked-set (ALS):?: If so, please identify the ALS.

If not part of an ALS, what made f4#5 a more promising number to try than any other:?:

and another question to add to ron's: the original statements mention nothing about almost
exactly what methods/constraints/techniques are applied on the recursion level?
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby leon1789 » Wed Mar 28, 2007 7:32 pm

ronk wrote:I don't see an answer to my question in there anywhere. Are you saying f4#5 is part of an almost-locked-set (ALS):?: If so, please identify the ALS.

In fact, Dynamic Contradiction Forcing Chains using locked sets is part of general ALS strategy. I can try to write such an ALS, but it's a very big one !:) I have already done it (with an other example) in a french forum...

ronk wrote:If not part of an ALS, what made f4#5 a more promising number to try than any other:?:

I suppose that f4#5 is not the better choice, but it's my choice:) . Some other eliminations are possible too, of course. May be they are better, I don't know.

Sorry if I don't understand your question...:(
leon1789
 
Posts: 37
Joined: 15 November 2006

Postby leon1789 » Wed Mar 28, 2007 7:46 pm

gsf wrote:and another question to add to ron's: the original statements mention nothing about almost
exactly what methods/constraints/techniques are applied on the recursion level?


I repeat (sorry for my poor english)... The "method" is :
-- only one guess on a bivalue cell or a bilocation number
-- (in 1-level recursion) use Dynamic Contradiction Forcing Chains involving locked sets (not almost !) in order to disprove any bad candidates. Is it "understandable" ?:)

Moreover a remark : Dynamic Contradiction Forcing Chains are particular case of a general ALS technique.
leon1789
 
Posts: 37
Joined: 15 November 2006

Postby ronk » Wed Mar 28, 2007 9:22 pm

leon1789 wrote:In fact, Dynamic Contradiction Forcing Chains using locked sets is part of general ALS strategy. I can try to write such an ALS, but it's a very big one !:)
[...]
I suppose that f4#5 is not the better choice, but it's my choice:) . Some other eliminations are possible too, of course. May be they are better, I don't know.

So the [edit: "method"] is to
... 1) guess one of two possible assertions of either a bivalue or bilocation pair
... 2) then guess a series of assertions with the goal of making a series of eliminations-by-contradiction, backtracking as necessary
... 3) with the further goal of eventually finding a number where both the assertion and negation cause a contradiction
... 4) then backtrack and rather than make the assertion of step 1), make the alternate assertion instead
... 5) repeating steps 1) through 4) [edit: a second time, if required.]

Is that correct:?:

I should pinch myself, as it seems I've been here before.:)
Last edited by ronk on Thu Mar 29, 2007 7:11 am, edited 1 time in total.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby sirdave » Wed Mar 28, 2007 11:01 pm

ronk"][quote="leon1789 wrote:I should pinch myself, as it seems I've been here before.:)


Like, roundabout June, 2005?
sirdave
2010 Supporter
 
Posts: 36
Joined: 04 January 2006

Postby udosuk » Thu Mar 29, 2007 6:55 am

To be fair, I think Leon was just posting his workings as examples to demonstrate his conjecture, instead of a "technique" for us to use.

I surely won't follow that procedure to solve any puzzle, nor would I recommend any others to follow it... But they are logically sound steps to prove that the solutions of those puzzles can be obtained in that manner (and proving the uniqueness of solution at the same time). They're sort of like mathematical proofs... You don't question how people set out to prove a theorem, as long as they show you all the logical steps.

Just like with the "singles backdoor twins conjecture" doesn't recommend us to solve every puzzle by finding 2 backdoor cells, I suppose we should treat this "bifurication + 2-level branching of contradiction chains conjecture" as a mathematical problem rather than a technique...:?:

And sirdave, I think you should have correctly quoted that sentence as below:
ronk wrote:I should pinch myself, as it seems I've been here before.:)
udosuk
 
Posts: 2698
Joined: 17 July 2005

Postby gsf » Thu Mar 29, 2007 8:17 am

leon1789 wrote:
gsf wrote:and another question to add to ron's: the original statements mention nothing about almost
exactly what methods/constraints/techniques are applied on the recursion level?


I repeat (sorry for my poor english)... The "method" is :
-- only one guess on a bivalue cell or a bilocation number
-- (in 1-level recursion) use Dynamic Contradiction Forcing Chains involving locked sets (not almost !) in order to disprove any bad candidates. Is it "understandable" ?:)

Moreover a remark : Dynamic Contradiction Forcing Chains are particular case of a general ALS technique.

thanks
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby ronk » Thu Mar 29, 2007 11:07 am

udosuk wrote:To be fair, I think Leon was just posting his workings as examples to demonstrate his conjecture, instead of a "technique" for us to use.

Agreed, I edited the post changing "technique" to leon1789's term -- "method."
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby leon1789 » Thu Mar 29, 2007 7:03 pm

ronk wrote:So the [edit: "method"] is to
... 1) guess one of two possible assertions of either a bivalue or bilocation pair
... 2) then guess a series of assertions with the goal of making a series of eliminations-by-contradiction, backtracking as necessary
... 3) with the further goal of eventually finding a number where both the assertion and negation cause a contradiction
... 4) then backtrack and rather than make the assertion of step 1), make the alternate assertion instead
... 5) repeating steps 1) through 4) [edit: a second time, if required.]

Is that correct:?:

No backtracking is necessary in step 2. (if I anderstand your text)

udosuk wrote:To be fair, I think Leon was just posting his workings as examples to demonstrate his conjecture, instead of a "technique" for us to use.

Right !
leon1789
 
Posts: 37
Joined: 15 November 2006

Postby ronk » Thu Mar 29, 2007 7:49 pm

leon1789 wrote:
ronk wrote:So the [edit: "method"] is to
... 1) guess one of two possible assertions of either a bivalue or bilocation pair
... 2) then guess a series of assertions with the goal of making a series of eliminations-by-contradiction, backtracking as necessary
... 3) with the further goal of eventually finding a number where both the assertion and negation cause a contradiction
... 4) ...

No backtracking is necessary in step 2. (if I anderstand your text)

Are you saying that every guess in step 2 results in a contradiction?
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby leon1789 » Fri Mar 30, 2007 8:15 am

ronk wrote:Are you saying that every guess in step 2 results in a contradiction?

No, I don't say a contradiction (only one) of course.
leon1789 wrote:f4#5, d4#8, f3#8, g4#3, g9#1, c1#2, f4#1, b9#8, b3#9, c8#9, b6#8, b6#9, k7#2, contradiction

There is 13 chains for 13 contradictions for 13 eliminations, and after that a final contradiction . It's not a recursive algorithm, but a iterative one : an important difference for me.
leon1789
 
Posts: 37
Joined: 15 November 2006

Postby udosuk » Sun Apr 08, 2007 1:35 pm

leon1789 wrote:An other conjecture.... This method solves all puzzles :
-- only one guess on a bivalue cell or a bilocation number
-- contradiction nets using singles and locked sets in 1-level recursion

Leon, looks like JPF has found the monster that should prove your conjecture wrong:
Code: Select all
1.......2
.9.4...5.
..6...7..
.5.9.3...
....7....
...85..4.
7.....6..
.3...9.8.
..2.....1

Go on, take it on...:)
udosuk
 
Posts: 2698
Joined: 17 July 2005

Postby RW » Sun Apr 08, 2007 8:12 pm

udosuk wrote:
leon1789 wrote:An other conjecture.... This method solves all puzzles :
-- only one guess on a bivalue cell or a bilocation number
-- contradiction nets using singles and locked sets in 1-level recursion

Leon, looks like JPF has found the monster that should prove your conjecture wrong:

I'm sorry udosuk, but I believe the conjecture still stands, even though it's close to failing. There's no bivalue cells and only 13 bilocation cells to choose your guess from. Guessing r1c8=6 or r2c7=1 leaves an ER 9.3 puzzle that can be solved by tabling, which basically equals contradiction nets using singles only. But not very easy, SE uses 30 dynamic contradiction forcing chains for both, sudocue needs 31 & 28 tabling steps to solve them. Some of the other eight possible guesses might also give a solvable puzzle using locked sets in the contradiction nets.

RW
Last edited by RW on Mon Apr 09, 2007 3:14 am, edited 1 time in total.
RW
2010 Supporter
 
Posts: 1000
Joined: 16 March 2006

Postby daj95376 » Mon Apr 09, 2007 1:12 am

RW,

If I understand the premise correctly, then your results plus a few more.

First, I found 13 bilocation cells. Setting [r3c5]=9,[r5c6]=4,[r5c9]=5,[r7c3]=9 failed to lead to a solution with any of the techniques below in the contradiction nets.

Code: Select all
Singles                               : [r1c8]=6,[r2c7]=1
Singles + Locked Candidates           : [r1c2]=7,[r7c8]=2
Singles + Locked Candidates + N-tuples: [r2c6]=7,[r3c1]=5,[r3c9]=4,([r4c8]=7,[r8c9]=7)
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006

Postby udosuk » Mon Apr 09, 2007 4:01 am

Okay, thanks for the checking guys... So the conjecure survives... For now...:)
udosuk
 
Posts: 2698
Joined: 17 July 2005

PreviousNext

Return to Advanced solving techniques