Ultimate Lizard Guide

Advanced methods and approaches for solving Sudoku puzzles

Ultimate Lizard Guide

Postby tarek » Sun May 23, 2010 12:53 am

This Thread follows the exploxive increase in the number of different complex sudoku solving techniques.

The power of Base/Cover single Symbol(digit, value, candidate) pattern based tecniques (especially NxN fish) has pushed me to present similar tecniques that are not limited to a single Symbol (digit, value, candidate). Please refer to Ultimate Fish Guide

The Lizards will have a pool of 9 values * 9 Rows * 9 Columns * 9 Boxes + 81 cells = 324 constriants (in vanilla sudoku) to choose Base/covers from compared to the 27 available for each Symbol (digit, value,candidtae) forming a fish.

Lizards subsume Fish. And if Terminology is appropriate, they can be applied in sudoku variants.

I'm hoping that it can provide a more user friendly technique to present things like Subset counting & ALSs. & a useful tool to present different technique under one banner

The first post of this thread should be the reference...it will be evolving over time to reflect any additions, deletions, examples, suggestions or comments offered by the players.

This is a joint & collective effort aimed towards the advanced players.

Terminology
Code: Select all
*Sector*: a group of cells with a constraint derived from the puzzle's rules, in a vanilla sudoku it is a group of 9 cells arranged in a row, column or box that must contain 9 different symbols (digits 1 to 9)

*Line*: a collective term that can describe a row or a column

*Candidate*: One of several POSSIBLE symbols (digits, values, candidates) that may occupy a sudoku puzzle cell. In a valid vanilla sudoku, each cell must eventually house 1 of its candidates only.

*Nonet*: a 9-cell box in vanilla sudoku or any 9-cell sector replacing the box in some sudoku variants

*Peer*: a cell that shares one or more sectors with another cell

*Lizard*: a collection of different constraint groups that can be mapped onto an "A" number of groups and a "B" number of groups where A=B
      The "A" groups are called "Base groups" & the "B" groups are called "Cover groups".
      The number of groups forming the Base or Cover groups is usually termed the lizard's "Size".
      The type of groups forming the Base  and Cover groups determines the lizard's "Shape" or configuration.
      A Lizard May have special qualities based on its anatomy.
      The lizard's "Name" can be defined in terms of "Shape","Size" and "Special qualities"
      The lizard is therfore a powerful Base/Cover oriented sudoku technique

  The intersection of Base & cover groups forming the lizard will divide its symbols (digits, values, candidates) into vertices, scales and potential eliminations
*Scale (S)*: is a candidate that has Base groups > Cover groups
*Vertex (V)*: is a candidate that has Base groups = Cover groups
*Potential Elimination (PE)*: is a candidate that has Base groups < Cover groups
*ExoScale (XS)*: S with Base groups=1
*EndoScale (NS)*: S with Base groups>1
*Scale cell*: a cell where a scale exists

     A lizard with one or more scales is a "Scaly lizard".
     A lizard with NO scales is a Smooth lizard (omitting the "Smooth" when describing the smooth lizard is acceptable)

*Eventual Elimination(EE)*: Potential Elimanation that can be linked
  (through the Pattern) to All Scale cells & their values.
  In the Abscence of scales, EE(s)=PE(s)

*Remote scale (RS)*:F that's in a cell which is not a peer with all EE(s) cells

*Lizard Eliminations/Exclusions: are termed Eventual Elimination(s)


Lizard Anatomy
Code: Select all
Naming Lizards:

A Lizard name consist of terms that describe Size, Shape & Special qualities as follows:

A Lizard's Name: Lizard Special Qualities + Lizard Shape + Lizard Size


Code: Select all
Size of Lizards:

1. monosaurus: All elements are in 1 group * 1 group (a.k.a 1-Lizard)
2. disaurus: All elements are in 2 groups * 2 groups (a.k.a 2-Lizard)
3. trisaurus: All elements are in 3 groups * 3 groups (a.k.a 3-Lizard)
4. tetrasaurus: All elements are in 4 groups * 4 groups (a.k.a 4-Lizard)
5. pentasaurus: All elements are in 5 groups * 5 groups (a.k.a 5-Lizard)
6. hexasaurus: All elements are in 6 groups * 6 groups (a.k.a 6-Lizard)
7. heptasaurus: All elements are in 7 groups * 7 groups (a.k.a 7-Lizard)
8. octasaurus: All elements are in 8 groups * 8 groups (a.k.a 8-Lizard)

For larger fish: Usage of Greek Numeral Prefixes should be used or simply X-Lizard


Code: Select all
Shape of Lizards:

1.  Basic: The use of more than one type of Line in either Base groups Or Cover groups is not allowed
2.  Franken: similar to "Basic" with Nonet(s) allowed to be added to Base groups and/or Cover groups   
3.  Mutant: Any combination of groups (That is not Basic nor Franken)
4.  Kraken: Any lizard (1-3) that requires life support (information from outside the pattern)


Code: Select all
Special Qualities of lizards:

*   Scaly Lizard: A lizard with Scale(s). A Lizard with No scales is a Smooth lizard.
*   Degenerate Lizard: A lizard that (in the abscence of all scales) will degenerate (using lizard based logic) into a smaller lizard. A lizard that doesn't display this quality is an Upright Lizard
*   AutoCannibalistic Lizard: A lizard with EE(s) having Base groups>0


Lizard Physiology
Code: Select all
In a Scaly Lizard: Any PE that is linked directly (Peer relationship) or indirectly (Other Relationship deduced from the NxN pattern) to ALL scale(s) is described as EE & can be safely eliminated.
In a Smooth Lizard: All PEs are described as EEs and can be safely eliminated


Code: Select all
Lizard Notation:

[Lizard Name] [base groups/cover groups] [Cell addresses<>EEs]

Lizard name has been dicussed in the "Lizard anatomy" section

Base/Cover groups:
   Each group must be enclosed within "()"
   If the group is a multi locality constraint (single Sector Symbol/value/digit) then the group is notated as XSector, where X is the symbol/value/digit & Sector is the sector address,e.g., 1r5, 7b5, 3c9
   If the group is a multi value constraint (A single cell) then the group can be notated as rXcY where X is the cell's row & Y is the cell's column

Each scale is notated as s(CandidateCellAddress) , e.g., s(1r1c3) s(2r3c4)

When possible, similar identifiers can be combined to give us a shorter version, e.g., r1r2 ---> r12, (1r1c2)(1r1c7) ---> (1r1c27), (1r5)(3r5) ---> (13r5)
Here is an example showing a long version and its shorter version
(2r2)(2r6)(r4c2)(r5c2)/(2c2)(3c2)(2c6)(2c8)  ---> (2r26)(r45c2)/(2c268)(3c2)

And a fully notated example:
Scaly Hexasaurus (r2c89)(r37c9)(r79c6)/(78b3)(r2c6)(3b8)(7r7)(9c9) S(9r2c8)(9r9c6) r2c6<>9


Code: Select all
Logic behind Smooth lizard based eliminations

In an NxN smooth lizard, i.e., a lizard without scales, the N base groups contain only vertices
Each base group is a constraint that requires ONLY 1 truth for the puzzle to be valid
Therefore we need 1 truth per base group
The Smooth lizard has exactly N cover groups
A vertex lies at the intersection of a base/cover groups
N vertices will therfore occupy the N cover groups & eliminate all potential eliminations.
If any potential elimination was true then the remaining vertices will not be enough to give 1 truth per base group

Implications:
All potential eliminations can be safely eliminated and described as eventual eliminations

In short, In a valid puzzle Only vertices of an NxN Smooth lizard can provide truths for the base/cover groups



Code: Select all
Logic behind Scaly lizard based eliminations

Conjecture:
In an NxN Scaly lizard:
If the smooth lizard component ,i.e., the lizard without scales is false, then at least one of the scales is true
If all the scales are false, then the smooth lizard component is true

Implications:
Only potential eliminations that can be linked to all scales can be safely eliminated
User avatar
tarek
 
Posts: 2624
Joined: 05 January 2006

Re: Ultimate Lizard Guide

Postby tarek » Sun May 23, 2010 12:54 am

And you thought that it went away with the old forum :D

This post is reserved for the examples which I unfortunately didn't backup.

tarek
User avatar
tarek
 
Posts: 2624
Joined: 05 January 2006

Re: Ultimate Lizard Guide

Postby tarek » Sun May 23, 2010 12:55 am

This is reserved as well for related links & info.

tarek
User avatar
tarek
 
Posts: 2624
Joined: 05 January 2006


Return to Advanced solving techniques