The New Sudoku Players' Forum

[champagne]

Finding the minimal sudokus for a given one having redundant clues has been solved long ago.
“Gridchecker” sends all minimal in “stdout” in a quick way

In the vicinity search planned to work around seeds having the tridagon pattern, the yield can be significantly improved if we can do the same, building a table of minimal easy to reuse in the process.

This is what is expected from this DLL.

The “primary seeds”, in the tridagon vicinity search are often resulting of a “max expand” step.
Such seeds can produce thousands of minimal sudokus. (seen close to 20000)

But in my draft of code for the vicinity search, the most common case is to get a valid puzzle with around 25-30 clues and a small number of redundant clues, leading to less than 10 “minimal”.

This pushed to let the caller supply a table receiving the results having the appropriate dimension.

This pushed also to have a code filtering in priority cases with a small number of “minimal”.

Next posts will tell more about the entries and the process applied. As far as I can see, this process is faster than Gridchecker, but this is not a key point

[champagne]

Basically, the DLL has one service with 2 calls corresponding to different situations in the caller program.

The caller sends
a valid sudoku
The return table pointer
The maximum of “minimal” to store
And receives the number of minimal stored.
____________________________________________________

As the caller is assumed to give enough room to store all “minimal”, the process looks for all possibilities.
A 0 count as return means that something wrong happened, usually a wrong sudoku pattern.
________________________________________________________

The first call is for a given sudoku in a classical 81 characters string where empty cells are dots.
Eg: this one given by “coloin” with 1192 “minimal”

Code: Select all

98...5.677.46..8...6.87.9...78.6.4..4.9.....665...4..88.7..65...4...7683.96...712

Here the storage is done also in char[82] and the storing parameter is a pointer to a table of such strings.

My call to get in ttmp the list of “minimal”

Code: Select all

char myp[82];
typedef  struct {char w[82];} PUZZLE;
PUZZLE ttmp[30000];

int ir = SkMinPchar(myp, ttmp, 30000);


__________________________________________________

The second call is done in a situation where

the solution grid is known
all puzzles are described as an 81 bits field giving the cells active in the solution grid.


The 81 bits are with the pattern of the brute force.
They are in a 128 bits field, where the first 3x32 bits receive 3x27 bits, one band for each 32 bits field.

The storage is done in 128 bits fields as well
This is usually for puzzles close to an existing minimal one, so the number of puzzles to store will be small.
Here, the call must also give the solution grid, expressed as a 81 int where each digit is 0-8

My call to get in “tmin” the list of BF128 “minimal”

Code: Select all

Int grid[81];
BF128 puzbf,tmin[10000];
Int ir= SkMinP(puzbf, grid,tmin, 10000);

Next post will be for a short description of the process.

[champagne]

The main process is working well when a big number of minimal is expected.
It is based on expansion of unavoidable sets, (like in the proof that no 16 exists, in the check that all 17s are known .....)

With a valid sudoku having (or not) redundant clues,

all unavoidable sets hit the sudoku
and no hit is out of the sudoku pattern.
Any unavoidable set hitting only once the sudoku defines a compulsory clue (but several unavoidable sets can hit the same clue)


This means that all UAs of the solution grid can be reduced to the cells belonging to the pattern.
This increases the chances of having a subset and in fact, starting from several thousand ED UAs, I got in one example less than 200 UAs

Another key point is that we should have at the end usually some tens, as a limit some thousands of sudokus given by the UAs reduced set. (if the start sudoku is of reasonable size).

“blue” and I have experienced such a process in several conditions.

Starting from a limited set of small unavoidable sets, expansion starts.
When the list of UAs is fully hit, a call to the brute force checks if the puzzle is valid. Then:
If yes, we have a “minimal”,
If not, we get a list of UAs to add to the primary list.

A DLL builds in one call the primary list,
A brute force specific call makes the second operation.

We can here apply the simplest process, we don’t have to control a huge number of possible puzzles, and the full list of ED UAs will stay relatively small (below 2000)

But, as we’ll see in the next post, for easy cases, we have a better process.

[champagne]

The main process requires a first list of unavoidable sets.
This is not a very expensive process, around 50 milliseconds per solution grid, but for easy cases, it remains something as using a drop hammer to scratch a fly.

First of all, compulsory clues are easy to spot with a call to the brute force. (one call per clue)

If all clues are compulsory, the sudoku given is minimal.

If nearly all clues are compulsory, we can see if using just them the puzzle is valid
If yes, we have the unique minimal sub puzzle,
If no, we have a set of UAs (small size if “nearly all clues are compulsory”). We can start the expanding process using this set of UAs.

With a smaller number of compulsory clues, testing compulsory pairs of clues “not compulsory” seems very efficient to build a primary “reduced list” with UAs of size 2. More can be tried, but in my code, only pairs are searched.
Then, an expanding step can start with a pattern excluding compulsory clues and with the compulsory pairs as first UAs.

This is surely part of the possible optimization, but this is what is in my DLL;

[champagne]

This topic did not raise big interest. I close it releasing the code of the central loop.

The central loop works out minimal out of a UAs list;
here is the central loop, a variant of a code inherited years ago from "blue"

Hidden Text: Show

Code: Select all

int WW::Expand() {
   char ws[82]; ws[81] = 0;
   TUA3X_2048& tu = tu2048a;
   spt[0].Start();
   SPOT* s, * sp;
   sp = spt;   s = spt + 1;   *s = *spt;
next:
   if ((cell = s->GetNext()) < 0) {// go back
      if (--s > spt) goto next;      return ntmin;
   }
   int iua = s->Netxua(tu);
   if (iua < 0) {// see if valid
      x = s->all_cells;
      if (CheckValid(x)) NotValid();
      else {// see if minimal
         if (SeeIfMinimal()) AddBack(x);
         goto next;
      }

   }
   // assign next in this ua with active cells
   BF128 y = (tu.tua[iua] & puzbf) - s->dead_cells;
   if (y.isNotEmpty()) { sp = s++;   s->Copy(sp, iua, y); }
   goto next;
   return 0;
}

This loop uses "spots" controlling the steps. Here 40 clues are possible after compulsory clues. This not enough for a general code, but more than needed for a reasonable entry.
The UAs table can receive up to 2048 UAs. again much more than needed with a reasonable entry, but I tested limit cases supplied by coloin where more than 1000 UA where there at the end.

Hidden Text: Show

Code: Select all

struct SPOT {
   BF128 cur_ua, all_previous_cells, dead_cells, all_cells;
   uint32_t iua, ispot, cell;
   void Start() {
      iua = ispot = 0;
      all_previous_cells = ww.psingles;
      dead_cells = ww.psingles;
      cur_ua = tu2048a.tua[iua];
   }
   int GetNext() {
      cell = cur_ua.getFirstCell();
      if (cell < 0) return -1;
      cur_ua.Clear_c(cell);
      dead_cells.Set_c(cell);
      return cell;
   }
   int Netxua(TUA3X_2048& tu, int op = 0) {
      char ws[82]; ws[81] = 0;
      all_cells = all_previous_cells;
      all_cells.Set_c(cell);
      if (op)cout << all_cells.String3X(ws) << " all cells iua=" << iua << endl;

      for (int i = iua + 1; i < tu.nua; i++) {
         BF128 w = tu.tua[i];// w.bf.u32[3] = 0;
         if (op) {
            cout << w.String3X(ws) << " iua=" << i << endl;
         }
         if ((w & all_cells).isNotEmpty()) continue;
         return i;
      }
      return -1; // no more ua
   }
   void Copy(SPOT* o, int iuae, BF128 u) {
      *this = *o; ispot++; iua = iuae; cur_ua = u;
      all_previous_cells.Set_c(cell);// add last cell
   }
   
}spt[40];

if (CheckValid(x)) NotValid();

This line of code call the brute force to see if the puzzle is valid, and insert new uas in the table if it is not.