The New Sudoku Players' Forum

[Wepwawet]

I am contemplating a long overdue update of my code for Alternate Inference Chains in my solver and was wondering what the consensus is on the application of breadth and depth first. At what point should one should consider what strategy to use? I am considering using breadth first up to chains of 5 nodes length before switching to the depth option, is that sound, or efficient. What do you guys think?

[StrmCkr]

I use breadth, on my
dual edge xor gate (strong links) nodal setup.

Build a list of weak inferences (nand) for each node.
. Then breath walk the nodes add in full but only to a depth of 10.(mutable value)

For how to build strong links
https://reddit.com/r/sudoku/w/C-terminology

some math for why this works:
https://reddit.com/r/sudoku/w/aic

After it runs I toss the output into a classifier

named-chains-wings-rings-structure-for-i-ding-in-code-t42435.html

[yzfwsf]

I use breadth, on my
dual edge xor gate (strong links) nodal setup.

Why emphasize xor? In fact, the strong relationship in the chain is not necessarily xor, but can be true at the same time (accurate description cannot be false at the same time). The relationship between any two candidate numbers in ALS is a typical representative that cannot be both false but can be true at the same time.

[Wepwawet]

Well, I am unsure about the XOR or NAND application. My current AIC chain algorithms goes up to a depth of about 8 nodes, but as I am planning to revise it (as I want to incorporate missing algorithms, e.g. ALS, UR's, into the chains). As for creating a list of weak links, for the love of money, I cannot see, or found, a use for that. My current model for AIC's employs just strong links, the sees of one strong link to another strong link, are the weak links. So, a list of strong links must induce the weak links, unless, I am missing something here.

Anyway, I was more interested in thoughts/feedback on using breadth verses depth, pros and cons, not so much on the mechanisms to achieve it, but on the pragmatism (or lack of) employing one method over the other.

Edited and added: BTW my intention is to limit chains to a depth of 10 nodes.

[StrmCkr]

why the emphasis: cause they are all xor gates, including the ones for ALS:
XOR (LS, RCC)

xor by default via the construction limits of Sudoku space and construction rules.

single digit:
xor (mini sector A,mini sector B)

A.I.C the logic is Deterministic:

instead of a union of iteration of truth tables final results via "or" gates if that's the direction you think they are from, as this also works but doesn't respect the grid space.

[yzfwsf]

If I understand correctly, XOR (a, b) satisfies, then a and b are not only strong but also weak. Obviously, the strong edge of ALS cannot satisfy the inference that it becomes a weak relation.

[blue]

"XOR (LS, RCC)" is correct.
The "weak" part follows from "N cells can't hold more than N digits".

[RSW]

I'm a bit late to this discussion, but when I wrote my X-chain and XY-chain solvers, I used a breadth first search.

Later, when I wrote my general AIC solver that works with any combination of strong/weak link sets, I used a cellular automata path finding algorithm (searching for a path through "strong link space"):
1. Pick a desired elimination.
2. Find all strong links that can see the target elimination cell, such that if any two of them can be linked together in an AIC it would give the elimination.
3. Loop through as many cell generations as necessary to propagate AIC link connections through "strong link space" until two subchains from the target links meet.
4. These two sub-chains connected together will be the shortest AIC for the target elimination.

[Hajime]

path through "strong link space"

Does "grouped AIC" fit in too?

[RSW]

It works with grouped strong links, because it obeys the directional constraints of the grouped link.
For example for this puzzle:
46.8...51.......2..2.9...4.8..2.9..3.........3..1.64.8.4...7.8..1.......9....2.17
(Source: steve-stumble-12-6-2025-t46175.html)

The AIC solver gives these stats:

Total BiLocal links: 67
Total BiValue links: 24
Total UR links: 0
Total ALS links: 1032
Group Links: 12
Inline Group Links: 9
Weak Links: 14923

And several of the AIC's that it generates have grouped strong links.
For example grouped link (5)r4c7=r5c79 in the following AIC:
(5)r4c7 = (5)r5c79 - (5=8)r5c6 - (8)r8c6 = (8-7)r8c3 = (7-1)r2c3 = (1)r4c3 => -1r4c7

[StrmCkr]

yes grouped links fit into xor definitions , as does Eri

how my codes been doing this for years: {finally got around to writing some formal documentations on it linked in this thread..} over this crappy thing i made as a rough reference

strong links:
xor (mini sector A, mini Sector B): gives 4 mini sector types under 1 umbrella structure covering all cases like these: { x = x, x=xxx, xxx = x, xxx = xxx}

sector A = xor ( {mini sector A,B,C} , if B = 0, then we have xor ( mini sector A,C)

mini sector defined as a intersection of Sector
example row has Row 1 { r1*b1,r1*b2, r1*b3) if r1*b3 is empty then the one of the other two must satisfy the row for digit d.

mini sectors:
https://www.reddit.com/r/sudoku/wiki/aic/mini-sectors/

Eri is harder to explain as its a hyper dimensional xor: {short cut programming see below uses it as a "union"{or} to go around corners but its equally valid. }

https://www.reddit.com/r/sudoku/wiki/aic/empty-rectangle-intersection/

ALS
https://www.reddit.com/r/sudoku/wiki/aic/almost-locked-sets

AHS
https://www.reddit.com/r/sudoku/wiki/aic/almost-hidden-sets

aic mathy stuff: https://www.reddit.com/r/sudoku/wiki/aic

i have the base RN,Cn,Bn RC spaces setup with addition Mini Sector spaces

Code: Select all

 
 for (int n = 0; n < 9; n++) {
                    if (basicGrid.hasCandidate(cell, n)) {
                     

 RCBnbp[0][rSec][n].set(Bsec[Bxy[cell]]);
                        RCBnbp[1][Cy[cell]][n].set(Bsec[Bxy[cell]]);
                        RCBnbp[2][Bxy[cell]][n].set(Rsec[Rx[cell]]);
                        RCBnbp[3][Bxy[cell]][n].set(Csec[Cy[cell]]);
...

i have hard coded cardinal lockups ~

}

in short:
R x number storing Box
C x n storing Box
B x n storing Col
Bx n storing Col


these 4 mini sectors the code below uses

Single digit: Show

Code: Select all

private static void SingleDigitStronglinks(SBRCGrid sbrc, Set<StrongLink>[] linkset, int digit, int line, int t) {

        // BitSet originSector = SetOps.fromInts(line + offset[t]);

        BitSet startingDigits = SetOps.fromInts(digit);
        BitSet linkDigits = SetOps.fromInts(digit);

        BitSet options = sbrc.RCBnbp[t][line][digit];
        int first = options.nextSetBit(0);
        int second = options.nextSetBit(first + 1);

        BitSet startSector = sbrc.DigitRCB[line + offset[t]][digit];
        BitSet firstSector = sbrc.DigitRCB[first][digit];
        BitSet secondSector = sbrc.DigitRCB[second][digit];

        BitSet activeCells = SetOps.intersection(startSector, firstSector);
        BitSet linkCells = SetOps.intersection(startSector, secondSector);

        BitSet originSector = Tools.commonSectors(SetOps.union(activeCells, linkCells));

        BitSet startDigitSwapAvailable = new BitSet();
        if (activeCells.cardinality() == 1) {
            startDigitSwapAvailable = SetOps.difference(sbrc.pm[activeCells.nextSetBit(0)], SetOps.fromInts(digit));
        }

        BitSet endDigitSwapAvailable = new BitSet();
        if (linkCells.cardinality() == 1) {
            endDigitSwapAvailable = SetOps.difference(sbrc.pm[linkCells.nextSetBit(0)], SetOps.fromInts(digit));

        }

        Map<Integer, BitSet> startingSector = new HashMap<>();
        Map<Integer, BitSet> linkSector = new HashMap<>();
        startingSector.put(digit, Tools.commonSectors(activeCells));
        linkSector.put(digit, Tools.commonSectors(linkCells));

        // Create maps for potential eliminations
        Map<Integer, BitSet> potentialElimStart = new HashMap<>();
        Map<Integer, BitSet> potentialElimEnd = new HashMap<>();
        potentialElimStart.put(digit, Tools.GetPeers(sbrc, digit, activeCells));
        potentialElimEnd.put(digit, Tools.GetPeers(sbrc, digit, linkCells));

        int linkType = determineLinkType(activeCells, linkCells);

        StrongLink Link = new StrongLink(linkType, originSector, startingDigits, activeCells, linkCells, linkDigits, startingSector, linkSector, potentialElimStart, potentialElimEnd, startDigitSwapAvailable, endDigitSwapAvailable);
        linkset[linkType].add(Link);
    }

ERi: Show

Code: Select all

 private static void EmptyRectangleIntersections(SBRCGrid sbrc, Set<StrongLink>[] linkset, int digit, int line) {
        int box = line + 18;
        // BitSet originSector = SetOps.fromInts(box);

        BitSet boxCells = sbrc.DigitRCB[box][digit];
        BitSet digitSet = SetOps.fromInts(digit);

        for (int r = 0; r < 3; r++) {
            for (int c = 0; c < 3; c++) {
                int col = ((line % 3) * 3) + r + 9;
                int row = (line / 3) * 3 + c;

                BitSet rowCells = sbrc.DigitRCB[row][digit];
                BitSet colCells = sbrc.DigitRCB[col][digit];

                BitSet boxRow = SetOps.intersection(boxCells, rowCells);
                BitSet boxCol = SetOps.intersection(boxCells, colCells);

                if (boxRow.isEmpty() || boxCol.isEmpty())
                    continue;

                BitSet union = SetOps.union(boxRow, boxCol);
                if (!boxCells.equals(union))
                    continue;

                BitSet originSector = Tools.commonSectors(union);

                int linkType = ERI;
                BitSet startDigitSwapAvailable = new BitSet();
                if (boxRow.cardinality() == 1) {
                    startDigitSwapAvailable = difference(sbrc.pm[boxRow.nextSetBit(0)], digitSet);
                }
                BitSet endDigitSwapAvailable = new BitSet();
                if (boxCol.cardinality() == 1) {
                    endDigitSwapAvailable = difference(sbrc.pm[boxCol.nextSetBit(0)], digitSet);
                }

                Map<Integer, BitSet> startingSector = new HashMap<>();
                Map<Integer, BitSet> linkSector = new HashMap<>();
                startingSector.put(digit, Tools.commonSectors(boxRow));
                linkSector.put(digit, Tools.commonSectors(boxCol));

                Map<Integer, BitSet> potentialElimStart = new HashMap<>();
                Map<Integer, BitSet> potentialElimEnd = new HashMap<>();
                potentialElimStart.put(digit, Tools.GetPeers(sbrc, digit, boxRow));
                potentialElimEnd.put(digit, Tools.GetPeers(sbrc, digit, boxCol));

                StrongLink link = new StrongLink(linkType, originSector, digitSet, boxRow, boxCol, digitSet, startingSector, linkSector, potentialElimStart, potentialElimEnd, startDigitSwapAvailable, endDigitSwapAvailable);

                linkset[linkType].add(link);
            }
        }
    }

building a edge list for each strong link {nand gate}
path walking is cycling the edge case list for each node, breadth or depth : with 1 rule no node may repeat.

[Hajime]

I have some troubles implementing grouped AIC's.
Let me explain using a grouped X-chain.

Code: Select all

  . . . . . . . / /
  . . . . . . . / /
  . 5 . . . . . / 5
  . . . . . . . / /
  . . . . . . . / /
  . . . . . . . / /
  . . . . . . . 5 /
  / 5 / / / / 5 5 5
  . . . . . . . / /

All 5's are candidates. A / means: no candidate 5 in this cell. A dot is undetermined.

Start at r8c2: suppose it is not a 5. Then r8c789 must be a 5. Then r7c8 cannot be a 5.
Then r8c8 must be a 5 because of column 8. Then r8c9 cannot be a 5 [some kind of feedback loop]
Then r3c9 must be a 5. So r3c2 as a 5 can be eliminated.
I have programming difficulties in box 9.
In your implementation this situation is solved ?

[thelardoffear]

I am having trouble understanding why this example needs grouped X-chains etc.

From column 8, r7c8 or r8c8 is 5.
Therefore r8c7 and r8c9 can't be 5 in box 9 by simple locked candidates.
Therefore r3c9 is 5 in column 9.

[Hajime]

I am having trouble understanding why this example needs grouped X-chains etc

Yep, you are right. Wrong example.
Maybe the max complicated is here

[StrmCkr]

AIC: (1)(r5c5 = r5c8)(1) - (1)(r789c8 = r8c789)(1) - (1)(r8c123 = r789c2)(1) - (1)(r2c2 = r2c5)(1) - ring => b8p2468,r13468c258 <> 1

Code: Select all

.---------------------------------.---------------------------------.---------------------------------.
| 123456789  123456789  123456789 | 123456789  123456789  123456789 | 123456789  123456789  123456789 |
| 23456789   123456789  23456789  | 23456789   123456789  23456789  | 23456789   23456789   23456789  |
| 123456789  123456789  123456789 | 123456789  123456789  123456789 | 123456789  123456789  123456789 |
:---------------------------------+---------------------------------+---------------------------------:
| 123456789  123456789  123456789 | 123456789  123456789  123456789 | 123456789  123456789  123456789 |
| 23456789   23456789   23456789  | 23456789   123456789  23456789  | 23456789   123456789  23456789  |
| 123456789  123456789  123456789 | 123456789  123456789  123456789 | 123456789  123456789  123456789 |
:---------------------------------+---------------------------------+---------------------------------:
| 23456789   123456789  23456789  | 123456789  123456789  123456789 | 23456789   123456789  23456789  |
| 123456789  123456789  123456789 | 123456789  123456789  123456789 | 123456789  123456789  123456789 |
| 23456789   123456789  23456789  | 123456789  123456789  123456789 | 23456789   123456789  23456789  |
'---------------------------------'---------------------------------'---------------------------------'

Code: Select all

Type: BILOCAL
   Link Type:0,originSector:{4},startDigits:{0},activeCells:{40},linkedCells:{43},linkDigits:{0},startSector:{0={4, 13, 22}},linkSector:{0={4, 16, 23}},startSwap:{1, 2, 3, 4, 5, 6, 7, 8},endSwap:{1, 2, 3, 4, 5, 6, 7, 8},PE Start:{0={4, 13, 22, 30, 31, 32, 43, 48, 49, 50, 58, 67, 76}},PE End:{0={7, 25, 33, 34, 35, 40, 51, 52, 53, 61, 70, 79}},
   Link Type:0,originSector:{1},startDigits:{0},activeCells:{10},linkedCells:{13},linkDigits:{0},startSector:{0={1, 10, 18}},linkSector:{0={1, 13, 19}},startSwap:{1, 2, 3, 4, 5, 6, 7, 8},endSwap:{1, 2, 3, 4, 5, 6, 7, 8},PE Start:{0={0, 1, 2, 13, 18, 19, 20, 28, 46, 55, 64, 73}},PE End:{0={3, 4, 5, 10, 21, 22, 23, 31, 40, 49, 58, 67, 76}},
Type: CELL_TO_GROUP
Type: GROUP_TO_GROUP
   Link Type:2,originSector:{20},startDigits:{0},activeCells:{6, 7, 8},linkedCells:{24, 25, 26},linkDigits:{0},startSector:{0={0, 20}},linkSector:{0={2, 20}},startSwap:{},endSwap:{},PE Start:{0={0, 1, 2, 3, 4, 5, 24, 25, 26}},PE End:{0={6, 7, 8, 18, 19, 20, 21, 22, 23}},
   Link Type:2,originSector:{21},startDigits:{0},activeCells:{27, 28, 29},linkedCells:{45, 46, 47},linkDigits:{0},startSector:{0={3, 21}},linkSector:{0={5, 21}},startSwap:{},endSwap:{},PE Start:{0={30, 31, 32, 33, 34, 35, 45, 46, 47}},PE End:{0={27, 28, 29, 48, 49, 50, 51, 52, 53}},
Type: ERI
   Link Type:3,originSector:{26},startDigits:{0},activeCells:{69, 70, 71},linkedCells:{61, 70, 79},linkDigits:{0},startSector:{0={7, 26}},linkSector:{0={16, 26}},startSwap:{},endSwap:{},PE Start:{0={61, 63, 64, 65, 66, 67, 68, 79}},PE End:{0={7, 25, 34, 43, 52, 69, 71}},
   Link Type:3,originSector:{24},startDigits:{0},activeCells:{63, 64, 65},linkedCells:{55, 64, 73},linkDigits:{0},startSector:{0={7, 24}},linkSector:{0={10, 24}},startSwap:{},endSwap:{},PE Start:{0={55, 66, 67, 68, 69, 70, 71, 73}},PE End:{0={1, 10, 19, 28, 46, 63, 65}},

= 6

=== StrongLink: ({0})r5c5=({0})r5c8{BILOCAL}Link ID =3
RIGHT -> target: ({0})r8c789=({0})r789c8{ERI} dir=false wt=1 digit?=Target Link id =5
LEFT -> target: ({0})r2c2=({0})r2c5{BILOCAL} dir=false wt=1 digit?=Target Link id =0
=== StrongLink: ({0})r2c2=({0})r2c5{BILOCAL}Link ID =0
RIGHT -> target: ({0})r5c5=({0})r5c8{BILOCAL} dir=true wt=1 digit?=Target Link id =3
LEFT -> target: ({0})r8c123=({0})r789c2{ERI} dir=false wt=1 digit?=Target Link id =4
=== StrongLink: ({0})r1c789=({0})r3c789{GROUP_TO_GROUP}Link ID =1
=== StrongLink: ({0})r4c123=({0})r6c123{GROUP_TO_GROUP}Link ID =2
=== StrongLink: ({0})r8c789=({0})r789c8{ERI}Link ID =5
RIGHT -> target: ({0})r5c5=({0})r5c8{BILOCAL} dir=false wt=1 digit?=Target Link id =3
LEFT -> target: ({0})r8c123=({0})r789c2{ERI} dir=true wt=1 digit?=Target Link id =4
=== StrongLink: ({0})r8c123=({0})r789c2{ERI}Link ID =4
RIGHT -> target: ({0})r2c2=({0})r2c5{BILOCAL} dir=true wt=1 digit?=Target Link id =0
LEFT -> target: ({0})r8c789=({0})r789c8{ERI} dir=true wt=1 digit?=Target Link id =5
Starting BFS from: ({0})r5c5=({0})r5c8{BILOCAL}
Starting BFS from: ({0})r2c2=({0})r2c5{BILOCAL}
Starting BFS from: ({0})r1c789=({0})r3c789{GROUP_TO_GROUP}
Starting BFS from: ({0})r4c123=({0})r6c123{GROUP_TO_GROUP}
Starting BFS from: ({0})r8c789=({0})r789c8{ERI}
Starting BFS from: ({0})r8c123=({0})r789c2{ERI}
Total start nodes = 6
Normal chains count:16 Unique chains retained = 12 { note ~ missing rotation eliminations in this code for normalization}
AIC: (1)(r5c5 = r5c8)(1) - (1)(r789c8 = r8c789)(1) => r8c5 <> 1
AIC: (1)(r2c5 = r2c2)(1) - (1)(r789c2 = r8c123)(1) => r8c5 <> 1
AIC: (1)(r5c8 = r5c5)(1) - (1)(r2c5 = r2c2)(1) - (1)(r789c2 = r8c123)(1) => r8c58 <> 1
AIC: (1)(r2c2 = r2c5)(1) - (1)(r5c5 = r5c8)(1) - (1)(r789c8 = r8c789)(1) => r8c25 <> 1
AIC: (1)(r5c5 = r5c8)(1) - (1)(r789c8 = r8c789)(1) - (1)(r8c123 = r789c2)(1) - (1)(r2c2 = r2c5)(1) - ring => b8p2468,r13468c258 <> 1
AIC: (1)(r5c8 = r5c5)(1) - (1)(r2c5 = r2c2)(1) - (1)(r789c2 = r8c123)(1) - (1)(r8c789 = r789c8)(1) - ring => b8p2468,r13468c258 <> 1
AIC: (1)(r2c2 = r2c5)(1) - (1)(r5c5 = r5c8)(1) - (1)(r789c8 = r8c789)(1) - (1)(r8c123 = r789c2)(1) - ring => b8p2468,r13468c258 <> 1
AIC: (1)(r2c5 = r2c2)(1) - (1)(r789c2 = r8c123)(1) - (1)(r8c789 = r789c8)(1) - (1)(r5c8 = r5c5)(1) - ring => b8p2468,r13468c258 <> 1
AIC: (1)(r8c789 = r789c8)(1) - (1)(r5c8 = r5c5)(1) - (1)(r2c5 = r2c2)(1) - (1)(r789c2 = r8c123)(1) - ring => b8p2468,r13468c258 <> 1
AIC: (1)(r789c8 = r8c789)(1) - (1)(r8c123 = r789c2)(1) - (1)(r2c2 = r2c5)(1) - (1)(r5c5 = r5c8)(1) - ring => b8p2468,r13468c258 <> 1
AIC: (1)(r8c123 = r789c2)(1) - (1)(r2c2 = r2c5)(1) - (1)(r5c5 = r5c8)(1) - (1)(r789c8 = r8c789)(1) - ring => b8p2468,r13468c258 <> 1
AIC: (1)(r789c2 = r8c123)(1) - (1)(r8c789 = r789c8)(1) - (1)(r5c8 = r5c5)(1) - (1)(r2c5 = r2c2)(1) - ring => b8p2468,r13468c258 <> 1

my chain walk has a weak inference builder for the "-" as these are nand gates

= r5c8)(1) - (1)(r789c8 =