ALS and useful ALS...

Advanced methods and approaches for solving Sudoku puzzles

ALS and useful ALS...

Postby Havard » Tue Jul 25, 2006 2:33 pm

I have been working a lot with ALSs for a while now, and I have come to realize that the definintion I use for finding an ALS might not be the best way...

Some of this might better belong in the programmers forum, but I hope that some of this might be general enough to apply to manual solvers as well...

In short, the definition I have used for an ALS is: "n cells with exactly n+1 different candidates". Hence our beloved bivaluecell are the smallest known ALS.

However, even though all sets found with this definition is arguably an ALS, I have found that it produces a lot of so called "useless" ALSs, or ALS's that is not suited to be used in ALS related eliminations...

This is just screaming for an example, so let's start with this first argument:

"many ALSs that are found with the "n cells, n+1 candidates"-argument are actually several ALSs.":

The simplest example is if you have two cells: [13] and [14].
These two seen under one fulfills the "n cells, n+1 candidates"-argument because we have 2 cells and (1,3,4)=3 different candidates. However, this is also two different ALS's [13] and [14], and it turns out that any elimination that can be done using [13] and [14] as one ALS, can also be done with the short ALS chain: [13]-1-[14].

The removal of such superflous ALSs from a recursive ALS-chain-builder will speed it up conciderably without any loss of potential eliminations.

A more complex example would be the three cells: [123] [12] [14]
All these cells combined could be concidered an ALS. Both [12] and [14] can be concidered separate ALSs, but [123] can not, so here we can not say that this is one ALS concisting only of smaller ALSs. However, [123] and [12] can be concidered one ALS when combined and hence the [14] is not needed. And again, any elimination that can be done with the ALS: [123][12][14] can also be done with the little chain [123][12]-1-[14]

So that is my first objection... The second one is even more obvious and happens when a Locked Set finds it's way into an ALS.

"if an ALS contains a Locked Set, the cells that contain the locked set are useless to the ALS."

This might be stating obvious, but following the same rule, this has to be concidered an ALS:
[12] [12] [45]

We have three cells, and exactly 4 different candidates, and yet what have happend here is that a bivaluecell has clinged on to a Locked Set which it has absolutely no relation to whatsoever! You see my point? This is an absurd ALS, and yet it fits the definition perfectly?!?

What I want is for some of the great brains at this forum to help me come up with a new definition for what I call the "useful" ALSs...

Thanks!:)

Havard
Havard
 
Posts: 377
Joined: 25 December 2005

Postby Carcul » Tue Jul 25, 2006 4:39 pm

Havard wrote:What I want is for some of the great brains at this forum to help me come up with a new definition for what I call the "useful" ALSs...


For me, a useful ALS is one in which two of his candidates are in two different sets of cells of the ALS. For example,

Code: Select all
 456 . . | .   .   .   | . . .
 .   . . | .   .   .   | . . .
 .   . . | .   .   .   | . . .   
---------+-------------+------
 .   . . | 159 .   589 | . . .
 .   . . | .   .   .   | . . .
 .   . . | 157 578 .   | . . .
---------+-------------+------
 458 . . | .   .   .   | . . .
 58  . . | .   .   .   | . . .
 .   . . | .   .   .   | . . .


in the ALS in cells r178c1, candidate "6" is located only in box 1, whereas candidate "8" is located only in box 7: [r1c1]=6|8=[r78c1].
On the other hand, in the ALS in cells r4c46/r6c45, candidate "7" is located only in row 6, and candidate "9" is located only in row 4: [r6c45]=7|9=[r4c46].
In general, an ALS will probably be more useful if we can write for it a link of the type [A|B|...]=x|y=[L|M|...], where "x", "y" are candidates belonging to the ALS, and A, B, ..., L, M, ..., are cells belonging also to the ALS.

Here is a good grid for you to see a usefull example of Almost Locked Sets:

Code: Select all
 *-----------------------*
 | . . . | . 2 . | . 8 . |
 | 1 . 9 | . . 5 | 3 . . |
 | 7 . . | . . 4 | 1 . 5 |
 |-------+-------+-------|
 | . . . | 6 4 . | 5 . . |
 | 9 . . | . . . | . . 8 |
 | . . 3 | . 9 2 | . . . |
 |-------+-------+-------|
 | . . 2 | . . . | . . 1 |
 | . . 1 | 4 . . | 2 . 3 |
 | . 6 . | . 5 . | . . . |
 *-----------------------*

Carcul
Carcul
 
Posts: 724
Joined: 04 November 2005


Return to Advanced solving techniques