The New Sudoku Players' Forum

[RW]

I was originally goin to post this is the Investigation of one-band-free-patterns thread, but I decided that this perhaps deserves a thread of it's own.

From the mentioned thread a quote on finding the unavoidables in an empty band:

- find grid's UA sets for its first band. Say, by creating a puzzle from the previously generated grid with 54 givens in bands 2 and 3, then finding all its solutions, comparing them to original grid, storing differences as unavoidable sets, and finally filtering out non-minimal UA. The cell positions for the UA found are property of the band (all one-band UA in all 416 bands have only 2 permutations), and hitting them is necessary for all band's completions.

Is there really no faster way to find all unavoidable sets in a band? Creating 96 to 1728 solutions, depending on the band, seems like a detour to me when we should be able to recognize all unavoidable sets by looking at the original grid.

An unavoidable in a band has the following two properties:

1) For each cell C there exists a buddy digit D that it can see both in the same row and in the same minicolumn.
2) Every cell can (and must) be counted as a buddy digit once in the row and once in the minicolumn.

Here is an example of a set that fulfills the first requirement, but not the second, therefore it is not an unavoidable set:

Code: Select all

1.3|4..|..9
4..|..9|.31
..9|1.3|.4.

In this set every cell has a buddy digit that appears in the same row and the same minicolumn, but in row 1 the buddy digit for 4 and 9 is 1 and digit 3 is not the buddy digit to any other cell in the row.

So let's look at a band and how to find unavoidables:

Code: Select all

123|456|789
456|789|231
789|123|645

Any unavoidable that includes r1c1 must also include either 4 in r2c1 and r1c4 or 7 in r3c1 and r1c7. Let's say we pick the first. As r1c4 now is included, we know that either 7 in {r2c4,r1c7} or 4 in r3c4 must be included as well. Let's pick the latter. Now with r3c4 included, we know that either 4 in r3c8 or 7 in {r2c4,r3c1} must be included. Pick the second option and now we see that both added digits already have buddy digits that are not accounted for yet in the same row/minicolumn => We have found our first unavoidable set:

Code: Select all

1..|4..
4..|7..
7..|1..

If we instead had picked the second option at the last stage, we would then have r3c8 included and continue by adding either {r1c8,r3c2} or {r2c8,r3c6} and so on, until we find an unavoidable set like for example:

Code: Select all

123|45.|.89
4..|..9|.31
.89|123|.45

Please note in the set above that it includes both {r1c8,r3c2} and {r2c8,r3c6} as potential buddy digits for r3c8, but to fulfill property 2) mentioned above, the buddy digit must be 8 in {r1c8,r3c2}. r2c8 and r3c6 are required as buddy digits for other cells. Therefore you must re-evaluate the whole situation every time you add new cell to the set and cannot always keep buddy digits assigned at earlier stages.

Then there is also the issue of minimality, the set found is not necessarily always minimal. But after an exhaustive search, it should be possible to sort out the minimals quite easily.

I know nothing about how to efficiently code a search like this, or if it would be more efficient than the method used by dobrichev. Just wanted to show that you can find them without knowing the other solutions. At least for this band with 1728 solutions:

Code: Select all

123|456|789
456|789|123
789|123|456

I can use this method to easily see that it cannot have any minimal unavoidables of size <> 6 and find them all, just by looking at the grid.

Perhaps this method could come in handy if it could be extended to sets covering more than one band, where the solution count easily gets ridiculously high. I haven't quite worked out the details on such sets yet, but I think I'm not far off by saying that for cells that can see cells in other boxes both in both the same band and the same stack, the first rule should be replaced by "For each cell C there exists a buddy digit D that it can see in the same row, column and box" and the second requirement would be that each cell can be counted only once in each row column and box. But I'm not 100% sure yet if this covers all sets.

I know some of you here have found large amounts of unavoidable sets in rather big areas. What kind of methods have been used for this?

RW

[dobrichev]

An unavoidable in a band consists of an even number of cells (up to 18 cells for a minimal unavoidable) and has the following two properties...

This is not quite right.
Look at this example for a UA of size 23.
Columns are puzzle, number of givens, number of solutions.

Code: Select all

123456789456789213978123456231867945597341628684295371812934567345678192769512834   81   1
1234567894567892139781234562318679455973416286842953718..9.............2....1....   58   2 #UA 23
12345678945678921397812345623186794559734162868429537181.9.............2....1....   59   1
1234567894567892139781234562318679455973416286842953718.29.............2....1....   59   1
1234567894567892139781234562318679455973416286842953718..93............2....1....   59   1
1234567894567892139781234562318679455973416286842953718..9.4...........2....1....   59   1
1234567894567892139781234562318679455973416286842953718..9..5..........2....1....   59   1
1234567894567892139781234562318679455973416286842953718..9...6.........2....1....   59   1
1234567894567892139781234562318679455973416286842953718..9....7........2....1....   59   1
1234567894567892139781234562318679455973416286842953718..9.....3.......2....1....   59   1
1234567894567892139781234562318679455973416286842953718..9......4......2....1....   59   1
1234567894567892139781234562318679455973416286842953718..9.......5.....2....1....   59   1
1234567894567892139781234562318679455973416286842953718..9........6....2....1....   59   1
1234567894567892139781234562318679455973416286842953718..9.........7...2....1....   59   1
1234567894567892139781234562318679455973416286842953718..9..........8..2....1....   59   1
1234567894567892139781234562318679455973416286842953718..9...........1.2....1....   59   1
1234567894567892139781234562318679455973416286842953718..9............92....1....   59   1
1234567894567892139781234562318679455973416286842953718..9.............27...1....   59   1
1234567894567892139781234562318679455973416286842953718..9.............2.6..1....   59   1
1234567894567892139781234562318679455973416286842953718..9.............2..9.1....   59   1
1234567894567892139781234562318679455973416286842953718..9.............2...51....   59   1
1234567894567892139781234562318679455973416286842953718..9.............2....12...   59   1
1234567894567892139781234562318679455973416286842953718..9.............2....1.8..   59   1
1234567894567892139781234562318679455973416286842953718..9.............2....1..3.   59   1
1234567894567892139781234562318679455973416286842953718..9.............2....1...4   59   1

The distribution of essentially different one-band UA by size is

Code: Select all

Sz  #ua
4     1
6     3
8     2
10    6
11    2
12   20
13    8
14   46
15   22
16   66
17   69
18  257
19  111
20  259
21   71
22   78
23   14

Cheers,
MD

[RW]

An unavoidable in a band consists of an even number of cells (up to 18 cells for a minimal unavoidable) and has the following two properties...

This is not quite right.
Look at this example for a UA of size 23.

Thank you, I stand corrected. I edited the post. I should have researched better if the statement is true, don't really know where I pulled that from... It was probably just a hunch, which of course is not good enough, at least when it comes to unavoidables that tend to surprise again and again and again. But the rest of the requirements do apply to the 23 cell unavoidable set you showed.

RW