The New Sudoku Players' Forum

[Sudtyro2]

Does anyone have a simple algorithm to find all of the Almost-Locked Sets (ALS) in a single Sudoku house (row, col, box)?
And, if so, then extend that algorithm to find AALS, AAALS, etc. in that same house?

IOW, even I can manually see a bivalue cell of the form (ab), which is the simplest ALS.
I can also easily find 2-cell ALS of the form (ab) (abc).
But, after that, my mind sorta clouds over.

TIA for any suggestions!

[JasonLion]

I use a methodical test of all possible combinations of cells watching for the number of candidates between all of the current set of cells being N less than the number of cells involved. You can shortcut the search when the number of candidates along some path exceeds some threshold.

[daj95376]

The folowing example is from Andrew Stuart's website. I suspect that many people's minds would cloud over while searching [b5] for this ALS.

Code: Select all

  *-----------*
 |..6|8.5|.3.|
 |.34|6..|85.|
 |58.|...|.1.|
 |---+---+---|
 |893|1..|4..|
 |...|.9.|..3|
 |...|...|9.1|
 |---+---+---|
 |3..|...|.4.|
 |.75|..3|16.|
 |648|2.1|39.|
 *-----------*

 *-----------------------------------------------------------------------------*
 | 1279    12      6       | 8       1247    5       | 27      3       2479    |
 | 1279    3       4       | 6       127     279     | 8       5       279     |
 | 5       8       279     | 3479    2347    2479    | 267     1       24679   |
 |-------------------------+-------------------------+-------------------------|
 | 8       9       3       | 1      *2567   *267     | 4       27      56      |
 | 1247    56      127     |*47      9      *2478    | 56      278     3       |
 | 247     56      27      | 3457    234678 *24678   | 9       278     1       |
 |-------------------------+-------------------------+-------------------------|
 | 3       12      129     | 579     678     6789    | 257     4       278     |
 | 29      7       5       | 49      48      3       | 1       6       28      |
 | 6       4       8       | 2       57      1       | 3       9       57      |
 *-----------------------------------------------------------------------------*


The definition of an ALS is very simple. Manually putting it to good use probably takes lots of practice. In addition, there are those who argue that (12) (23) (34) (45) is a terrible waste of an ALS when described as (1=2345)cells or (1=5)cells.

[David P Bird]

Almost Naked and Almost Hidden Sets are both ALSs as far as I am concerned. As they come in complementary pairs I think it's easier to look for the candidates that are locked in the AHS. Although I've never coded it in full, I think this approach should work:

1. For each unsolved digit, assume it is locked in a AHS, mask out the cells that contain it, and count the cells and digits that remain checking for an ANS
2. When an ANS is found, check if it contains a naked single or pair. If so these digits & cells can be transferred to the AHS to leave a smaller ANS nested inside it.

This should find all 'primitive' ANS/AHS combinations.

When there are a lot of unsolved cells in a house, this routine should be extended to work through any untested digit pairs locked in the AHSs as well.

(My interactive spreadsheet only implements step 1 for the current focus digit and shows an alert when it is a member of a an AHS. I then run through step 2 by eye)

From my files here's a test puzzle from ttt in July? 2011 where row 2 and column 2 contain multiple nested ANSs

Code: Select all

*----------------------*----------------------*----------------------*
| 3456   346    1      | 2369   7      2569   | 2689   256    568    |
| 3567   367    29     | 8      356    12569  | 4      12567  1567   |
| 8      67     29     | 1269   4      12569  | 269    12567  3      |
*----------------------*----------------------*----------------------*
| 1      69     3      | 4679   2      679    | 56     8      456    |
| 69     2      4      | 5      8      3      | 7      169    16     |
| 7      5      8      | 469    1      69     | 3      469    2      |
*----------------------*----------------------*----------------------*
| 2      1348   57     | 1367   356    15678  | 568    34567  9      |
| 39     1389   6      | 1237   35     4      | 28     2357   578    |
| 34     348    57     | 2367   9      25678  | 1      234567 45678  |
*----------------------*----------------------*----------------------*

(356=7)r2c125 - (7=6)r3c2 - (6)r4c2 = (6)r5c1 – (6=1)r5c9 - (1)r2c9 = (129)r2c368 => r2c68 <> 56

[Sudtyro2]

Thanks to all for the helpful feedback. Let me think about your responses for a bit. In the meantime, see below for two hypothetical row examples having ALS with some that are easy to spot and some that are much less obvious and can be missed altogether.

Row Sample 1: (259)(157)(479)(38)(389)(6)(2357)(489)(1458)

Code: Select all

The bolded entries are easy to spot, so we immediately get two ALS:
   c4     => 38
   c45    => 389    Now, two more ALS are harder to find:
   c458   => 3489
   c3458  => 34789

Row Sample 2: (29)(17)(457)(389)(1279)(6)(237)(4589)(1358)

Code: Select all

The two bivalues jump right out:
   c1     => 29
   c2     => 17     Then, less obvious are:
   c125   => 1279
   c1257  => 12379
   c12457 => 123789

OK, confession time...
These “row” samples are actually arcilla lists, where each ALS translates to a basic Fish having (usually) a single fin cell, although ALS (1279) above has two. Further along, AALS usually define two fin cells, AAALS define three fin cells, etc., although for now efforts are concentrating on single-fin Fish. Hence, the interest in a simple algorithm to catch them all.