News and Updates on X
SudokuWiki.org
Strategies for Popular Number Puzzles

AIC with ALSs

Naked Pair and Almost Locked Set
Naked Pair and Almost Locked Set

A Locked Set is a group of cells (that can all see each other) of size N where the number of candidates in those cells is equal to the size of the group. That is N cells contain N candidates. A solved cell or a clue is a Locked Set where N=1, but such a cell is not useful. The smallest useful Locked Set is a Naked Pair (where N=2) as in the [2,8] set in the diagram. The next smallest Locked Set is a Naked Triple (N=3) and so on.
An Almost Locked Set (ALS) is N cells containing N+1 candidates. In the context of Alternating Inference Chains in this solver, an ALS is of size N=2 and the number of different candidates in those cells is 3, although bigger ALS groups are possible. So an ALS of size 2 will be a two Conjugate Pairs plus one other candidate. In the diagram above the [2,8] pair are joined by a stray 6 which stops it being a useful Naked Pair.

ALS in an AIC fragment
ALS in an AIC fragment

Lets continue with this ALS.

While solving a puzzle I am hunting around for Inference Chains and perhaps I find my chain turns ON the 6 in cell C4. That will remove all other 6s in the box including the 6 in our ALS. If that 6 is OFF then we create an on-the-fly Naked Pair.

Now, a Naked Pair eliminates candidates in the row or column (or box) it is aligned on so we can use this elimination property as part of our chain. This is the trick! By removing the 6 in B5 we fix 2 and 8 into those two cells so we can look along the row at other 2s and 8s and turn them OFF. This I do in cell B9. From there I can continue the inference chain. You get two cracks of the whip: check both branches - the 2s and the 8s in the pseudo Naked Pair.

AIC with ALS
AIC with ALS : Load Example or : From the Start
A real life example now. This chain contains an ALS on the cells {G6,H6} (I used squiggly brackets to denote ALS as opposed to square brackets for Grouped Cells). 9s in row H are the entry point. We turn 9 ON in H2 which turns OFF the 9 in H6 - the extra candidate that makes the ALS an ALS. This gives us a Naked Pair of [5,7] that points up column 6 turning OFF the 7 in F6 and the chain continues.

Ultimately we use Nice Loop Rule 2 to place 4 in A4
AIC on 4 (Discontinuous Alternating Nice Loop, length 12):
-4[A4]+4[D4]-7[D4]+7[D2]
-7[H2]+9[H2]-9[H6]+7{H6|G6}
-7[F6]+4[F6]-4[A6]+4[A4]
- Contradiction: When 4 is removed from A4 the chain implies it must be 4 - other candidates 2/5 can be removed


Off Chain eliminations
Off Chain eliminations : Load Example or : From the Start

This second example uses a chain to kill off-chain candidates, which is Nice Loop Rule 1. The ALS is in {F1,F4} and consists of [1/3/8] and [1/3] respectively. We turn off the extra candidate, 8 in F1 to enable the Naked Pair to be formed.
Alternating Inference Chain
AIC Rule 1: -3[B5]+6[B5]-6[B8]+6[D8]-8[D8]+8[D1]-8[F1]+3{F1|F4}-3[F3]+3[B3]-3[B5]
- Off-chain 6 taken off B9 - weak link: B5 to B8
- Off-chain candidates 1 taken off cell D8, link is between 6 and 8 in D8
- Off-chain 8 taken off F2 - weak link: D1 to F1
- Off-chain 8 taken off F3 - weak link: D1 to F1
- Off-chain 8 taken off J1 - weak link: D1 to F1
- Off-chain 3 taken off B4 - weak link: B3 to B5




Comments

CommentsTalk

... by: Himself

Sunday 13-Aug-2023
In the last example, I believe the chain should also eliminate the 1s in F8 and F9, since 1 will always be contained within the naked pair.
Andrew Stuart writes:
This is correct, logically. The solver however is doing a lot of work here but is not sophisticated to nab those eliminations. Might be too much to explain in one step!
Add to this Thread

... by: Ymiros

Friday 7-Jul-2023
Wouldn't this strategy also work with almost locked hidden sets?
Specifically for N=2 this would be a set of 2 digits that within a specific unit have only 2 possible positions, but one of them is allowed to have a 3rd possible position within that unit so if that 3rd possibility gets eliminated we can get rid of all other candidates from the hidden pair and possibly continue with a strong link from there.
REPLY TO THIS POST

... by: tebo

Thursday 11-May-2023
I'm curious why this Strategy is not in your solver's Extreme Strategies list. I have not worked through any examples of this with any solver, nor have I examined Robert's "almost fish", "forcing net", or "AALS" logic. However, from your examples, it seems like the objective is to remove the N+1 Digit, leaving a Naked Subset. The regular AIC Strategy would still Eliminate the N+1 Candidate, leaving the Naked Subset to be found by a following step in the Solution Path. I completely agree with removal of AIC with ALSs if it's simply an intellectual exercise.
Andrew Stuart writes:
It is in the solver! It is just not a partitioned strategy. It is implemented for all strategies that use alternating inference chains. It is a type of chain link and there are other ones: grouped cells and URs for example. I don't think there is a simpler two-part process to using a chain with these elements, but would be interested in an example
Add to this Thread

... by: Robert

Monday 6-Dec-2021
I have worked a bit more on this.

An AIC with "almost locked sets" and also "almost fish" can solve the "unsolvables" #92 and #115 (and possibly others - I don't have all the unsolvables in my database).

A fish is basically the same thing as a locked set (which is itself the same thing as a hidden locked set).

If you think of a "fish" as consisting of "base sets" and "cover sets", where each set contains nine candidates, one of which must be true, then there are four kinds of such sets of candidates:

row-val: the nine candidates occurring in a particular row and with a particular value, but occurring in different columns.

col-val: the nine candidates occurring in a particular column and with a particular value, but occurring in different rows.

blk-val: the nine candidates occurring in a particular block and with a particular value, but occurring in different cells within that block.

row-col: the nine candidates occurring in a particular row and a particular column (so a cell), but having different values.

So a "fish" is then a group of base sets, and a group of cover sets, the same number of each type. If all the candidates in the base sets that have not already been eliminated, also occur in the cover sets, then any candidates remaining in the cover sets but outside the base sets, can be eliminated.

If base sets are row-cols with the same row and different columns (so cells), and the cover sets are row-vals with the same row and different values, the "fish" is a locked set (within a row). Same idea for columns and blocks.

If base sets are row-vals with the same row and different values, and the cover sets are row-cols with the same row and different columns, the "fish" is a hidden locked set (within a row). Same idea for columns and blocks.

If base sets are row-vals with the same value and different rows, and the cover sets are col-vals with the same value and different columns, then this is a traditional fish. Same idea with rows and columns switched.

So since there is really no conceptual difference between a locked set, a hidden locked set, and a fish, the concept of "almost locked sets" in an AIC extends to the other two as well. Hidden locked sets are not so important, because if there is an "almost hidden locked set", there is also a conjugate "almost locked set". But the "almost fish" are not redundant with "almost locked sets" in an AIC.
REPLY TO THIS POST

... by: Robert

Tuesday 20-Jul-2021
And following up - I have implemented an "Almost Fish" feature in my AIC/forcing net software. That is, there is no fish, but as you start to follow the "off" implications of an AIC, a fish appears, and can be used to turn some other candidates "off".

In my database of 235 "difficult" puzzles (of which 166 can already be solved), this does not get me any additional solved puzzles. However, it does get a small number of additional eliminations - just not enough to solve fully the puzzles. So I think the idea of an "almost fish" being used as a link in an AIC is valid, although in practice it may not be found very often. (It's actually found quite a lot in my sample, but most of the eliminations I get would eventually have been found anyway by other methods.)

I am now tending to use the terminology "dynamic locked set" or "dynamic fish" instead of "almost locked set" or "almost fish", to allow for their more general use in a forcing net. It can be that there are multiple extra candidates preventing the existence of a locked set or a fish, but following the implications of the forcing net, those multiple extra candidates bring the locked set or fish into existence (conditional on the initial assumption behind the forcing net).
REPLY TO THIS POST

... by: Robert

Tuesday 20-Jul-2021
I think the idea can be extended a bit.

The most obvious one would be to allow ALSs with more than two cells and more than three values. The description above is quite general, but from the comments, "In the context of Alternating Inference Chains in this solver, an ALS is of size N=2 and the number of different candidates in those cells is 3, although bigger ALS groups are possible." I take it the implementation in the solver is limited to two-cell ALSs. The current "unsolvable", #461, can be solved if larger ALSs are allowed.

There is another possible generalisation though. Suppose you have an AALS, two cells with four values. You begin by assuming some candidate somewhere is "on", and follow the implications through weak and strong links. If *two* of the values in the AALS are eliminated, then (conditional on the initial assumption) it becomes an ALS, and we can draw further inference by eliminating the two values in other cells in the same unit. This is even more likely to occur if we move to a "forcing net" way of doing things instead of a linear chain (related to the "AICs with Exotic Links" topic). Unsolvables #411 and #412 can be solved in this way.

I have a database of 235 advanced puzzles (which cannot be solved using naked/hidden singles/pairs/triples/quads, box-line reduction and pointing pairs/triples), many of which have come from this site, including the unsolvables, but some from other sources. I can now solve (with my own solver) 166 of them. 15 of those require a "forcing net" technique, sometimes including the generalisation of the ALS technique as described above. However, my "forcing net with dynamic LS" algorithm is so slow it is painful - I need to improve it.
REPLY TO THIS POST

... by: Nono

Tuesday 4-Jun-2013
Question like Str8tsFan.
the last solver version 1.95 does not eliminate the 8 in J1.
No problem for good sudoku players !


Andrew Stuart writes:
Quite correct. There was some very odd code in there that stopped J1 from being eliminated because the link had already eliminated in the box. Can't say why, must have had a brain fart that day. Diagram and solver updated.
Add to this Thread

... by: Str8tsFan

Wednesday 3-Oct-2012
I hope Andrew will ever read (and answer) these comments... About the second example:

(1) Using the link to the solver leads to a sudoku with a tiny little difference: B9 has an additional candidate 6, which is missing at the example. At the solver this candidate will be eliminated with the very same example:
"- Off-chain candidate 6 taken off B9 - weak link: B5 to B8"

(2) What about the candidate 8 at J1? As far as I can understand the theory, the weak link "D1 to F1" should not only eliminate the 8s at F2 and F3 (weak link in same box) but also the 8 at J1 (weak link in same column). More interesting: the solver doesn't eliminate that 8 at J1 either. Why? Did I make any mistake, or is it a flaw of the solver? As far as I understood, a weak link can be part of two entities (box and row or box and column) and thus should be able to eliminate candidates at both entities, maybe the solver fails to check the second entity?
Andrew Stuart writes:
Thanks for the detailed hints. Both points correct. I've updated the diagram and solver.
Add to this Thread

... by: Mr Turner

Tuesday 10-Jul-2012
The last paragraph seems flawed since there is an 8 at F8. The 8s at F2 and F3 could be colored off as an inference from D1 being on. This implies F8 is on. F8 is also inferred to be on from D8 being off.
Andrew Stuart writes:
Correct. I've removed that paragraph now. Doh.
Add to this Thread

... by: Mr Archibald

Wednesday 22-Apr-2009
I call this the 6 pack.

the first three in a line on rows 1,2 is the some as the last six on row 3. this can work upsidedown and backtofront and sideways.

a b c d e f g h i
i h g f e d c b a
d e f a b c i h g
REPLY TO THIS POST
Article created on 12-April-2008. Views: 67852
This page was last modified on 23-April-2016.
All text is copyright and for personal use only but may be reproduced with the permission of the author.
Copyright Andrew Stuart @ Syndicated Puzzles, Privacy, 2007-2024