UAs concept full grid, one band, 2 bands

UAs in a full grid

 

If we have a solution grid an unavoidable set (UA) is by definition a group of cells where at least one clue must be given to have a unique solution.

 

Here is an example of a lexically minimal solution grid

 

123 456 789

457 189 623

986 327 415

 

235 874 196

614 293 857

879 615 342

 

392 741 568

561 938 274

748 562 931

 

It has an example of the smallest UA in rows 1,2. if none of the digits 1,4 is given, the puzzle will have a minimum  of 2 solutions. Digits 1,4 could be exchanged.

 

A solution grid has a huge number of UAs. It’s clear that if only one cell is given, the puzzle is not solved. So any set of  80 cells is a UA and surely this is true also for any set of 79;78 … 81-16=65 cells.

 

Some of these UAs with many cells have a subset like our small UA, nevertheless, the number of UAs with no subset grows very fast with the number of cells.

 

In this thread

http://forum.enjoysudoku.com/bands-and-low-clue-puzzles-t30218-45.html

Blue gave an estimate of the UAs per solution grid having no subset.

 

The beginning of the table is the following

 

UA size |  all grids      

--------+------------------
    4   | 1.1580e+1
    6   | 1.5338e+1
    8   | 2.2038e+1
    9   | 6.0455e+0
   10   | 5.8380e+1
   11   | 2.9499e+1
   12   | 1.3667e+2
   13   | 1.0483e+2
   14   | 3.6172e+2
   15   | 3.9133e+2
   16   | 1.0498e+3
   17   | 1.4800e+3
   18   | 3.4658e+3
   19   | 5.5821e+3
   20   | 1.1778e+4
   21   | 2.0773e+4
   22   | 4.1781e+4
   23   | 7.7262e+4
   24   | 1.5191e+5
   25   
| 2.8748e+5
   26   | 5.5831e+5
   27   | 1.0649e+6
   28   | 2.0469e+6
   29   | 3.8959e+6

 

 

 

In fact UAs of big size are of small interest, if all smallest UAs are hit, most of them are hit as well.

However, at the end, some of them can help to identify quickly whether a set of given can not solve the grid. If one UA is not hit, the puzzle has more then one solution.

 

 

UAs can be used in several ways.

 

A classical one is to use them, starting with the smallest to produce all possible perms of “n given” having a chance to be a Sudoku.

 

In this search of 17clues puzzles, the possible perms come through a different process and the list of UAs appear as a filter to clear quickly a proposed “n given”.

 

In fact, in the proof that no 16 clue exists, Gary Mc Guire used both.

 

The first to produce “n given”

The second through “UAs of higher degree”, a concept not in use in this program.

 

Anyway; it’s impossible to collect all UAs, so at the end the brute force will be applied to check whether the “n given” is a valid solution.

 

The first question is then which UAs can we collect at the start (primary list)

And the second one is  Can we use the brute force check to collect more UAs

 

 

UAs in the 17 clues search

 

Note readers not familiar with he concepts of gangster;gangster PM;socket2;socket3;GUAs ... should first read this page  (page 3)

 

In fact, in the 17 clues search “as of blue”, we are not that much interested by the full grid. Most of the job is done in band and in the first 2 bands. The full grid check comes very late and the result has small possibilities to be re used.

 

One band UAs

 

We need the UAs  for each band (gangster PM) . We have in the full code the command 90 doing the job. This code has been tested, mainly to secure the process, but in fact, in the program, a table of the UAs for the 416 min lexical bands exists.

UAs are copied from that table and  morphed to the studied band.

The final list of UAs of the band is then processed differently depending on the band.

 

expanded to prepare the process for bands 1 and 2

Analyzed to locate sockets in use and potential GUA4 GUA6 .

 

Bands 1+2 UAs

 

This is the key primary UAs table.

The target is to collect as many as possible UAs for the gangster 2bands (bands 1+2).

As the process combine one valid band 1 (against the gangster band 1) to a valid band 2 (against the gangster band 2) UAs purely located in one band can be ignored.

 

More such UAs will come in the validity check of the given bands 1+2 to analyze. They will be re used as much as possible, growing the main table for next steps,  and locally in FIFO tables within a step (this will be clarified in the process description);

 

In this document, the description is focused on the primary generation of such UAs.

 

The first double question to solve is

 

How many UAs do we expect

What is the size limit for an UA collected

 

The optimum is not easy to define, so the code is flexible and these 2 parameters are given in

 

#define UALIMSIZE 20

#define TUA64_12SIZE 2000

both  in the head part of the sk_s17p2 file.

 

This means that the optimum seems to be with a relatively high number of UAs.

In the inner loop, (to see in the program description) only part of the primary table is used.

And the table will grow during the process if new small UAs appear during the check that a bands 1+2 set of given is “valid” (toward the gangster 2 bands)

 

The generation (see here for details) is done first in a classical way, for an increasing number of digits 2 to five digits.

 

Then, again following results of experimentation, UAs with 6 and 7 digits are searched in one band with in the other band one of these conditions

 

One pair in a mini row (equivalent in logic to the socket 2 in band 3)

One triplet in a mini row (equivalent in logic to a socket 3 in band 3)

2 pairs in 2 mini rows of different stacks

1 pair plus one triplet in 2 mini rows of different stacks.

 

This seems to be a balanced choice {efficiency of the set of UAs} / {cost of generation)

The process is covered in some milliseconds.

 

Socket UAs

 

We have room in the memory for the 81 socket 2 and the 81 socket 3 UAs primary tables.

The size of each table is limited to 150 socket UAs (see go_17_genb12.h). Only the part of the UA in bands 1+2 is stored;

If we have >= 10  bands 3 linked to the bands 1+2, all sockets2 and sockets3 will be needed.

With a lower number of bands 3 (corresponding normally to bad cases for the number of couples band1+band2 to study) some of the sockets can be ignored.

 

Later in the process, for a set of given bands 1+2 passing the global filters, the validity of some GUA2s can be checked. Then, new socket GUAs can appear, added to the table or replacing a bigger one if they are small enough, this did not pay in tests, so the socket UAs table is not updated.

 

Each socket UAs has more or less the same potential in UAs as the primary bands 1+2 UAs.

The search is done on another gangster 2 band, but the rest is very similar.

 

Even limiting the count to 150 UAs per socket, we have a potential of 81x2x150 uas. As the detection of valid GUA2s GUA3s is a key point for the last phase in he process, the size limit for such UAs is kept at a high level (close to the size limit for the bands 1+2 table). In several places (explained partly here and partly in the program description) action is done first to avoid overflow in tables, but also to have a reasonable total size in the steps.

 

The generation produces  to sockets UAs of 5 digits, (see here for details). Many actions are taken at generation time to prepare the work in the final phase. The generation itself is very similar to what is done for bands 1+2  (2-5 digits).

Are also searched socket UAs of bigger size limited to one mini row in one of the bands 1;2. Again something very similar to what is done for the main UAs table.

 

The current limit for socket UAs is 18 cells in bands 1+2. In the add process, if the limit for the table (150) is reached, smaller UAs replace the bigger ones.