AIC's net equivalent to forcing net

Advanced methods and approaches for solving Sudoku puzzles

Postby champagne » Sun Nov 23, 2008 8:05 am

coloin wrote:If we remove a given clue from this puzzle say the 8 @ r3c6, we get a subpuzzle with more than 1 solution.

The "real" pm board of this subpuzzle [as opposed to the above "virtual" board] reveals many elimiinations. Particularly the 2 @ r6c2 can be inserted !.

Does this indicate the weak spot in this puzzle ?
C


Hi coloin,

I red at least two recent posts with the same statement.

I am familiar with "adding a clue".

I never heard of "erasing a given" to ease the process, but I am not everywhere.

Could you comment a little more:?:

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

Postby coloin » Sun Nov 23, 2008 12:10 pm

The other recent post was on denis's "braid-not actually braid" thread ! I got the same clue insertion as David Bird did with his GEM.

It is likely you will be able to reproduce these eliminations/insertion with the "floors" i mentioned. My hunch is that this represents the "weakness" in a complete puzzle.

Removing a clue from a minimal puzzle [with n clues] gives a subpuzzle with more than 1 grid solution.

My method is to look at the way each of the [n] subpuzzles attempt to complete.

In easy puzzles there ary many eliminations/insertions in many of the n-1 and n-2 subpuzzles. In hard puzzles you ususally only get a few eliminations when you look at all the n-1 subpuzzles. Usually it is the clue which has the least grid solutions.

If you go back to the Easter Monster Puzzle [an unbalanced puzzle] and the first discovery of the SK loop. you will see that the SK eliminations are based only on the 16 clues in B12346789, [ie not box 5]. This is an extreme example of a subpuzzle with n-5 clues. I demonstrated this rather clumsily here . I got the same eliminations as Allan.

The important distinction is in the pm board of the complete puzzle - each empty cell has one correct and "real" clue and 1 or more wrong or "virtual" clues and.........

Now I know you cant do this bit....but I can......:(

....... the "real" pm board of the subpuzzle . In this "real" pm board the impossible clues are removed - there are no virtual clues.

You will see that there are eliminations - and in this case an insertion....

I do note there are relatively few eliminations in the GN puzzle - which is much more balanced.

C
coloin
 
Posts: 2502
Joined: 05 May 2005
Location: Devon

Postby coloin » Sun Nov 23, 2008 12:38 pm

Confirmatory details, this is the only n-1 subpuzzle from tarx0075 which shows an insertable clue.

Code: Select all
+---+---+---+
|...|...|..6|
|..5|..1|8..|
|.9.|...|.7.|
+---+---+---+
|...|8.2|...|
|..3|.1.|2..|
|4..|5.3|...|
+---+---+---+
|.6.|...|.9.|
|..8|3..|1..|
|7..|...|..4|
+---+---+---+  8@r3c6 removed = 28 grid solutions


........6..5..18...9...8.7....8.2.....3.1.2..4..5.3....6.....9...83..1..7.......4  complete puzzle

puzzle solution
187234956645791832392658471516872349873419265429563718264187593958346127731925684

27 other grid solutions
134785926275691843896234571517862439683419257429573618362148795948357162751926384
134789526275641839896235471517862943683914257429573618361428795948357162752196384
134789526275641839896235471517862943683914257429573618361458792948327165752196384
134789526275641839896235471519872643683914257427563918361428795948357162752196384
134789526275641839896235471519872643683914257427563918361458792948327165752196384
134798526275461839896235471617842953583619247429573618362184795948357162751926384
134798526275461839896235471617842953583916247429573618362184795948357162751629384
134798526275641839896235471517862943683419257429573618362184795948357162751926384
134798526275641839896235471519872643683419257427563918362184795948357162751926384
134987526275461839896235471657842913983716245421593687362154798548379162719628354
234987516675431829891265473156842937983716245427593681362154798548379162719628354
234987516675431829891625473156842937983716245427593681362154798548379162719268354
287439516645721839391685472516872943873914265429563781164257398958346127732198654
287439516645721839391685472519842763873916245426573981164257398958364127732198654
287439516645721839391685472519862743873914265426573981164257398958346127732198654
287934516645721839391685472516872943873419265429563781164257398958346127732198654
287934516645721839391685472519862743873419265426573981164257398958346127732198654
287935416645721839391486572519842763873619245426573981164257398958364127732198654
287935416645721839391684572516872943873419265429563781164257398958346127732198654
287935416645721839391684572519862743873419265426573981164257398958346127732198654
317428956645971832892635471176892345583714269429563718264187593958346127731259684
317428956645971832892635471176892543583714269429563718264187395958346127731259684
317428956645971832892635471179842365583716249426593718264187593958364127731259684
317428956645971832892635471179842563583716249426593718264187395958364127731259684
317428956645971832892635471179862345583714269426593718264187593958346127731259684
317428956645971832892635471179862543583714269426593718264187395958346127731259684
834927516675431829291685473156842937983716245427593681362154798548379162719268354
.................................................................................
..............................................X.................................. insertable clue
coloin
 
Posts: 2502
Joined: 05 May 2005
Location: Devon

Postby StrmCkr » Sun Nov 23, 2008 1:15 pm

colin i do see what your going at from the generated soultion counts, marking the same clue that is seen by all the grids and reinsert that back into the oringal puzzle.

an intresting but clumsy method of finding addition all clues.

or was there somthing else besided checking all the other grids for solution markups? that found the "2"

and did you go through and remove 1 clue at at time for all the givens and verify all soution counts for the same repeating clue in all those none single solution grids?

i have done similar things for easter monster with removing 1 clue and adding in issomorphic variations to find additional clues.

there is a few that produce a solution count of 3 on that puzzle.

with a handfull of identical clues.
very tedious....
Some do, some teach, the rest look it up.
stormdoku
User avatar
StrmCkr
 
Posts: 1433
Joined: 05 September 2006

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

I was just demonstrating with the data, its not how I do it !

The insertion is revealed to me by the "real" pm grid courtesy of Havard's Sudoku Architect !

With hindsight, in effect all I am saying is that the 2@r6c2 can be inserted without any information gained from the 8@r3c6. This is the only clue in tarx0075 puzzle which has this feature.
C
coloin
 
Posts: 2502
Joined: 05 May 2005
Location: Devon

Postby StrmCkr » Sun Nov 23, 2008 5:53 pm

oh, i was wondering...
just guessed at what you where doing.

i have done it the backwards way... removing clues looking at clue counts of remaing grids seeing if similar clues are still identified.

then looking at the coversets "pm" that are intact. or exposed that still cause that expression... which becomes long and tedious...

i was exploring this option to see if some data set exsits from beging and at each point of construction and if various constructs still expose the same clues... even with reduction of specific clues...
Some do, some teach, the rest look it up.
stormdoku
User avatar
StrmCkr
 
Posts: 1433
Joined: 05 September 2006

Postby champagne » Sun Nov 23, 2008 10:27 pm

coloin wrote:Confirmatory details, this is the only n-1 subpuzzle from tarx0075 which shows an insertable clue.


Hi coloin,

Quite clear now. Let me react as I feel it.

Some similarities with Allan Barker underlying way to find eliminations/assignments.

No problem to apply that procedure using a computer,

But what can we do out of it for players:?:

In Allan Barker method, I have been first hooked by the Sets / Link Sets construction. This is something a players can smell.

I am slightly disappointed that applying the rules is not so easy when fighting against hardest, but I am convinced Allan will improve the way he expess rank within a complex structure.

One should find a similar way to operate using your idea (I was surprised seeing that it works).:D

Nothing to object for example to the downgrading of the given to apply Allan Barker model (we are just not used to doing it).

A new meditation starts. At least for me, this is quite new.

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

Postby coloin » Mon Nov 24, 2008 6:03 am

Yes, a liffle meditation is in order, and i am not sure what help this is to any solver !

But 30 seconds later.

The "topic" comes to mind......"how do easy /hard puzzles solve ?"


Rewriting the pms like for the subpuzzle above.....[only partially completed]

Code: Select all
114224416245421822291....7....8.2.....3.1.2..4..5.3....6.....9...83..1..7.......4
23743552 67 63  333 2                                                           
38 78795    74  498 9                                                           
8  998      96                                                                   
     9       7                                                                   
             9 


simultaneous analysis of all the n subpiuzzles will reveal how the puzzle solves.........

if any clue is ommitted from any of the the strings - it is emiminated.
if any clue is solitary in any of the strings - it is inserted.

easy puzzles will have rather more solitary clues
hard puzzles - well it wont be obvious especially in GN

C
coloin
 
Posts: 2502
Joined: 05 May 2005
Location: Devon

Postby Allan Barker » Mon Nov 24, 2008 7:02 am

Coloin,
Coloin wrote:simultaneous analysis of all the n subpiuzzles will reveal how the puzzle solves.........

if any clue is ommitted from any of the the strings - it is emiminated.
if any clue is solitary in any of the strings - it is inserted.

Congratulations on your second step (first one as well).

As Champagne mentioned, I use a similar logical argument for possible candidates in a piece of logic (chain, fish, etc). Any candidate that is present in all possible candidate arrangements is assigned and any candidate that is absent from all is eliminated. I also have used the same to solve whole puzzles.

However, aside from the logic part, this has nothing to do with your rather (to me) unique revelation, the idea of that examining a puzzle's potential multiple solutions can be used to make deductions.
Allan Barker
 
Posts: 266
Joined: 20 February 2008

Postby coloin » Mon Nov 24, 2008 10:18 am

Thankyou, praise indeed. It is showing how all the clues contribute to the puzzle solution, understanding this.......well I hope i am doing.

Ive had a quick look at GN, not many eliminations with the [n-1] subpuzzles

Code: Select all
+---+---+---+
|...|...|.39|
|...|..1|..5|
|..3|.5.|8..|
+---+---+---+
|..8|.9.|..6|
|.7.|..2|...|
|1..|4..|...|
+---+---+---+
|..9|.8.|.5.|
|.2.|...|6..|
|4..|7..|...|
+---+---+---+  GN


Except this is quite good.....

If 5@r2c9 removed, this removes the 5s as pms from r5c7 and r6c7.
Put the 5 back..... and you can insert a clue 5@r4c7

likewise
If 6@r8c7 removed this removes the 6 as a pm from r3c8
Put the 6 back, and you can insert the 6 @r2c8

How does this fit in with your analysis ?

Im not saying that this is a technique, but perhaps it is one of the ways [the way] the puzzle determines its solution.

C
coloin
 
Posts: 2502
Joined: 05 May 2005
Location: Devon

Postby Allan Barker » Mon Nov 24, 2008 4:17 pm

Coloin wrote:How does this fit in with your analysis ?

I don't think that it does fit, or compare. Anything I do is derived only from the original 234 Sudoku constraints (what I call "sets"). As such, I cannot (directly) do uniqueness either.

The eliminations and assignments you see for GN do not relate to "easy" or initially "seeable" eliminations based on original constraint logic. This is because the underlying logical arguments are also not related. Uniqueness is a bit the same, for instance some of the recent Gurth's method solutions where one simple argument virtually solves some of the toughest puzzles.

I suppose that you to must make the initial assumption that the parent grid has a unique solution, right?
Allan Barker
 
Posts: 266
Joined: 20 February 2008

Postby StrmCkr » Mon Nov 24, 2008 5:53 pm

hey colin,
another option with the maping
is that it shows unavoidable sets in some sequences...
Some do, some teach, the rest look it up.
stormdoku
User avatar
StrmCkr
 
Posts: 1433
Joined: 05 September 2006

Postby eleven » Tue Nov 25, 2008 1:05 am

coloin wrote:If 5@r2c9 removed, this removes the 5s as pms from r5c7 and r6c7.
Put the 5 back..... and you can insert a clue 5@r4c7

likewise
If 6@r8c7 removed this removes the 6 as a pm from r3c8
Put the 6 back, and you can insert the 6 @r2c8

The first one is trivial. What you say is, that we dont need the 5 in r2c9 to eliminate 5's in r56c7. But any 5 in r456c7 immediately would imply a 5 in r2c9 again.
However i cant see something similar for the 6 elimination.

For solvers it would be interesting to find minimal subsets of cells (rather in a grid than a sudoku), which allow an elimination/placement. Having one, we then could look, which techniques are most appropriate to achieve it.
Maybe the SK loop is a good sample, where all possible placements in 16 cells allow the eliminations (outside).

But calculating such sets of cells and their eliminatons is certainly not possible in reasonable time. Also it is a problem, that in general you would need all 9 cells of a unit, when a simple strong link is used in a solution move.
eleven
 
Posts: 3173
Joined: 10 February 2008

Postby coloin » Tue Nov 25, 2008 11:36 am

Thank-you for all your vaid comments ! This isnt a solving technique.
Perhaps its more of sorting out the "route" that a hard puzzle takes initially to be able to determine its solution. [quite a difficult concept].
In easy puzzles there are many solving routes as such.


Allan.....
Absolutely correct, there is no easy way to "see" these eliminations.....except they are there !
The eliminated pms dont occur in any of the [multiple] grid solutions.
The fact that the eliminations are there doesnt necesarily mean that they would be the simplist to find - which you have confirmed [pity:( ].
Although the fact that they are there probably means that there is a logical way to find them.

eleven......
As i said above you cant see the elimination - you almost need to have T&E glasses ! - The eliminations and insertions are definitely present.

I am not sure of the relevance of uniqueness - In somewhat easier puzzles there will be eliminations present with [n-2] subpuzzles, and indeed we have seen the eliminations in the SK loop in EM where there were visable [and demonstratable] eliminations in the [n-5] subpuzzle.

In the GN puzzle we can proceed following the above 2 clue insertions [we now have a non minimal puzzle] to look at the [n-1] pms and continue to get furthur eliminations - and the solving path will be variable given the multiple eliminations and insertions that are bound to occur.

In harder [well balanced] puzzles there is a tendancy to have few eliminations with the [n-1] analysis. In unbalanced puzzles - with an SKloop - virtually all the puzzles we generated using a 16-clue template and adding clues to a central box here will have eliminations with the 16 clues alone.

In easier puzzles you tend to get several eliminations with a low number of clues. Trivially you only need 4 clues to insert a clue using a "single" technique.

StrmCkr.....
Removing a clue absolutely leaves unavoidable sets [minimal and non-minimal] uncovered which are specific to each solution grid. We revisited this recently here. Perhaps there is a distintion here with "real" pm board showing the clues that can be present in all the combinations of "deadly patterns" in all the grid solutions of each subpuzzle.

I am going to see if other puzzles [next is FM] also have an initial insertion which breaks the puzzle. I optimistically expect this to be the case.

..............
Code: Select all
+---+---+---+
|...|...|..3|
|..1|..5|6..|
|.9.|.4.|.7.|
+---+---+---+
|...|..9|.5.|
|7..|...|..8|
|.5.|4.2|...|
+---+---+---+
|.8.|.2.|.9.|
|..3|5..|1..|
|6..|...|...|
+---+---+---+   FM

FM certainly lived up to its name......a very balanced puzzle.

There were no eliminations initially......none. Apart from the insertion of the 5 at r5c5 ! which decimated it, on the first round.

the most obvious elimination leading to an insertion was:

pms @ r2c9 are 249
without 5@r8c4 no 2@r2c9 [bivalue 49@r2c9]
without 5@r2c6 no 4@r2c9 [bivalue 29@r2c9]

therefore an inserted clue will be 9@r2c9..........................

Probably not a move that a solver [computor or StrmCkr] could make very easily.

C
coloin
 
Posts: 2502
Joined: 05 May 2005
Location: Devon

Postby ttt » Thu Nov 27, 2008 5:29 am

Hi All,
I gave up for tarx0075 - nothing new. Perhaps, it has to use floor r5c46 at start…

BTW, based on SS solver I can’t follow coloin’s ways… And now, I know that Vodka is not good for eyes…:D

ttt
ttt
 
Posts: 185
Joined: 20 October 2006
Location: vietnam

PreviousNext

Return to Advanced solving techniques