The New Sudoku Players' Forum

[Serg]

Hi, people!
Efficient detection of UA sets is very important in exhaustive search projects. But not so many methods of their detection are known. Method of using "blueprints" of UA sets, to my mind, can be quite efficient only for small UA sets. Several classes of UA sets are still known, for which efficient methods of detection do exist.

1. Bidigital UA sets.
2. Two-row-plus-two-columns UA sets (see blue's post (March 13, 2013) in the thread Investigation of one-band-free patterns on this forum).

I propose a method for "two-box" UA sets detection. Such UA set participate 2 boxes exactly. I'll consider minimal UA sets only, i.e. UA sets not having other UA sets as their subsets.

Here are patterns of all possible 2-boxes (minimal) two-box UA sets.

Code: Select all

+-----+-----+     # U4
|. . x|x . .|
|. . x|x . .|
|. . .|. . .|
+-----+-----+

+-----+-----+     # U6
|. . x|x . .|
|. . x|x . .|
|. . x|x . .|
+-----+-----+

+-----+-----+     # U10
|. . x|x . .|
|. x x|x x .|
|. x x|x x .|
+-----+-----+

+-----+-----+     # U12 (variant 1)
|. x x|x x .|
|. x x|x x .|
|. x x|x x .|
+-----+-----+

+-----+-----+     # U12 (variant 2)
|. x x|x x .|
|. x x|x . x|
|. x x|. x x|
+-----+-----+

+-----+-----+     # U14
|. x x|x x .|
|x x x|x x x|
|x x .|. x x|
+-----+-----+

+-----+-----+     # U18
|x x x|x x x|
|x x x|x x x|
|x x x|x x x|
+-----+-----+


Two-box U6 is well known. Let's consider it in details.

Both its minicolumns must contain the same set of digits. Let's denote this set by A = {a1,a2,a3}.
Denotation

Code: Select all

+-----+-----+
|. . A|A . .|
|. . A|A . .|
|. . A|A . .|
+-----+-----+


shows that all cells marked by "A" letter contains a digit belonging to A set.

Minicolumn in the second box of U6 must be cyclically shifted minicolumn from the first box - cyclically shifted up or down.

Let's consider now more complicated UA set - U12 (variant1).

Code: Select all

+-----+-----+
|. A B|? ? .|
|. A B|? ? .|
|. A B|? ? .|
+-----+-----+


What can we say about 2 minicolumns in the second box? Their top cells must be "A B" or "B A", because these cells must exchange their digits with top cells of the first box minicolumns during UA permutation. So, 6 cells of U12 in the second box must contain the same set of digits as 6 cells in the first box. Here is their possible arrangement.

Code: Select all

+-----+-----+
|. A B|A B .|
|. A B|A B .|
|. A B|B A .|
+-----+-----+


Arrangement

Code: Select all

+-----+-----+
|. A B|A B .|
|. A B|A B .|
|. A B|A B .|
+-----+-----+


is not permitted, because in this case U12 would contain U6 as subset, i.e. it would not be minimal.

Configuration

Code: Select all

+-----+-----+
|. A B|A B .|
|. A B|A B .|
|. A B|B A .|
+-----+-----+


of the first permutation of U12 is the only possible one up to column/row permutations.

Let's find now the second permutation of U12. 3 cells marked by "A" in the second box must go up or down alltogether to "compensate" shift of minicolumn AAA in the first box. That shift can be possible only when minicolimn BBA goes cyclically in the same direction as minicolumn AAB! So, both minicolumns of the second box must move synchronically up or down to form second permutation of this UA set. This implies that BBB values in the second box must be shifted in the same manner as AAA values ralative to AAA and BBB minicolumns in the first box.

Let's consider an example of U12.

Code: Select all

+-----+-----+
|. 1 4|2 5 .|
|. 2 5|3 6 .|
|. 3 6|4 1 .|
+-----+-----+


This is the second permutation (state) of this UA:

Code: Select all

+-----+-----+
|. 2 5|4 1 .|
|. 3 6|2 5 .|
|. 1 4|3 6 .|
+-----+-----+


Continuation follows...

Serg

[Serg]

Hi!
I am continuing description of two-box UA sets detection.

Algorithm of U12 (variant 1) detection can be described as follows.

1. For each minicolumn of the first box do steps:
a) Analyze pattern of the minicolumn's digits in the second box - all 3 digits must occupy 3 different rows in the second box.
b) Compose virtual minicolumn from minicolumn's cells in the second box, preserving row numbers of the cells.
c) Compute cyclic shift of virtual column relative to minicolumn of the first box (possible values: "up", "down").

2. For each minicolumns pair having correct virtual minicolumns in the second box do steps:
a) Check sets of columns occupied by both virtual minicolumns in the second box. If there are 2 virtual minicolumns in the second box occuping the same 2 columns AND both minicolumns have the same shifts ("up" and "up" or "down" and "down"), then U12 is found.

Let's consider now U18 two-box UAset.

Code: Select all

+-----+-----+
|A B C|? ? ?|
|A B C|? ? ?|
|A B C|? ? ?|
+-----+-----+


Each minicolumn of the first box must have correct virtual minicolumn in the second box, and all virtual minicolumns must have the same shifts. Example of U18 layout:

Code: Select all

+-----+-----+
|A B C|A B C|
|A B C|A B C|
|A B C|C A B|
+-----+-----+


Example of U18 with its second permutation:

Code: Select all

+-----+-----+     +-----+-----+
|1 4 7|2 5 8|     |2 5 8|7 1 4|
|2 5 8|3 6 9|     |3 6 9|2 5 8|
|3 6 9|7 1 4|     |1 4 7|3 6 9|
+-----+-----+     +-----+-----+


Continuation follows...

Serg

[Serg]

Hi!
I am continuing description of two-box UA sets detection.

Let's consider now U12 (variant 2) UA set.

Code: Select all

+-----+-----+
|. A B|? ? .|
|. A B|? . ?|
|. A B|. ? ?|
+-----+-----+


It turns out, there is the only layout (up to A <-> B relabeling) of this UA set:

Code: Select all

+-----+-----+
|. A B|A B .|
|. A B|B . A|
|. A B|. A B|
+-----+-----+


Interesting, that shifts of virtual minicolumns of the second box must be opposite now.

Example of U12 (variant 2) with its second permutation:

Code: Select all

+-----+-----+     +-----+-----+
|. 1 4|2 6 .|     |. 2 6|4 1 .|
|. 2 5|4 . 3|     |. 3 4|2 . 5|
|. 3 6|. 1 5|     |. 1 5|. 6 3|
+-----+-----+     +-----+-----+


Now it's turn of U10.

Code: Select all

+-----+-----+
|. . B|? . .|
|. A B|? ? .|
|. A B|? ? .|
+-----+-----+


It turns out, there is only 1 possible layout (up to rows permutation):

Code: Select all

+-----+-----+
|. . B|B . .|
|. A B|B A .|
|. A B|A B .|
+-----+-----+


Algorithm of U10 detection looks rather complicated.

1. For each minicolumn of the first box do steps:
a) Analyze pattern of the minicolumn's digits in the second box - all 3 digits must occupy 3 different rows in the second box.
b) Compose virtual minicolumn from minicolumn's cells in the second box, preserving row numbers of the cells.
c) Compute cyclic shift of virtual column relative to minicolumn of the first box (possible values: "up", "down").

2. For each virtual minicolumn having 2 cells exactly in a minicolumn of the second box do steps:
a) Find the second minicolumn in the second box, containing 1 cell exactly of the virtual minicolumn.
b) Locate the "hole" - third cell of the first minicolumn (containing 2 cells), not belonging to virtual minicolumn.
c) Find "target cell" in the second minicolumn, depending on shift of processed virtual minicolumn - if sfift = "up", then target cell's row is obtained by shifting hole's row up, if sfift = "down", then target cell's row is obtained by shifting hole's row down.
d) Now we know 2 cells in the second box - candidates for AA subminicolumns. Check the first box for existing AA subminicolumn. If AA subminicolumn is found in the first box - U10 is found.

Let's consider now U14 UA set.

Code: Select all

+-----+-----+
|. B C|? ? .|
|A B C|? ? ?|
|A B .|. ? ?|
+-----+-----+


It turns out, there is only 1 possible layout (up to rows/columns permutations and A <-> C relabeling):

Code: Select all

+-----+-----+
|. B C|B C .|
|A B C|C A B|
|A B .|. B A|
+-----+-----+


Algorithm of U14 detection is very similar to the algotithm of U10 detection described above.

U4 UA sets can be simpler detected by "two-rows" UA detection technique. So, overall procedure of two-box UA detection should looks like this:

1. Filter out U4 by "two-rows" UA detection technique.

2. Find all correct virtual minicolumns in the second box.

3. For all virtual minicolumns do:
a) check for U6;
b) check for U10;
c) check for U14.

4. For all virtual minicolumns pairs do:
a) check for U12 (variant 1);
b) check for U12 (variant 2).

5. Check for U18 (3 virtual minicolumns involved).

The End.

Serg

[champagne]

Hi Serg,

All UA's if size <= 12 should be covered in the "Mac Guire blue prints". Could you check that?

If this is ok, the new 2 boxes UA's are the 14 and 18 cells (if I read correctly your posts).
Did you try to put your patterns in the Max Guire form?

[champagne]

2. Two-row-plus-two-columns UA sets (see blue's post (March 13, 2013) in the thread Investigation of one-band-free patterns on this forum).

Serg

Another question:

Is there in that family UA's not covered in the Mac Guire blue prints

[Serg]

Hi, champagne!

Is there in that family UA's not covered in the Mac Guire blue prints

Where can I see MacGuire's blueprints?

Serg

[champagne]

Hi, champagne!

Is there in that family UA's not covered in the Mac Guire blue prints

Where can I see MacGuire's blueprints?

Serg

They are part of the gridchecker package (file unav12 if the version of gridchecker that I recently downlaoded).
In the same file, you have the code to generate UA's using the blue prints.

Mladen dobritchev knows more than me about these files.

[Serg]

Hi, people!
Some comment to proposed two-box UA detection method.

It's not so obvious, but all (except for asymmetric U12 (variant 2)) two-box UA sets can be detected either by starting from the left box, or by starting from the right box. But U12 (variant 2) layout is asymmetric, so one should try to detect it 2 times - first by starting from the left box, and the second - by starting from the right box (treating right box as the first box of UA set, and left box - as the second box of UA set).

Serg