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