Counting minimal puzzles: subsets, supersets, etc.

Everything about Sudoku that doesn't fit in one of the other sections

Re: ~TE(1)

Postby blue » Sat Jun 29, 2013 7:00 am

Hi Denis,

Thank you for the detailed analysis.

BTW, you mentioned a way of computing SER without uniqueness. What's the command line? Is there also a way of computing it without uniqueness and without any of the Subset rules?

I don't know if there is a way to do it with the command line interface.
In the GUI, there are the menu items Tools/Analyze to rate, and Options/"Solving techniques..." to disable selected rules.
The subset rules are individaually listed ... "Naked Pair", "Swordfish", etc.

Regards,
Blue.
blue
 
Posts: 573
Joined: 11 March 2013

Re: ~TE(1)

Postby denis_berthier » Sat Jun 29, 2013 7:13 am

OK, thanks
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Re: Counting minimal puzzles: subsets, supersets, etc.

Postby dobrichev » Sat Jun 29, 2013 7:58 am

I just posted some details for the universal puzzle minimization process which are relevant to this topic.
dobrichev
2016 Supporter
 
Posts: 1314
Joined: 24 May 2010

UA collection

Postby dobrichev » Sat Jun 29, 2013 9:09 am

Some experience on UA collection.

McGuire's method for short-sized UA collecting is very efficient for grid w/o forced givens but gives very limited results for subsets/supersets problem.

There are very efficient algorithms for UA4, for UA6, for 2-digits UA, but all of them are inapplicable too.

Some results gives collection of all 4-digits UA. It is based on exhaustive UA collection on all subgrids consisting of all combinations of all instances of 5 digits given, plus the forced givens. For more forced givens, 5-digits UA can be collected in similar way but for 0 forced givens this process is inefficient.

Exhaustive UA collection for forced givens + some random number of floating givens also works. For 81 floating givens the best result is for around 10 000 attempts with random 27-clue subgrid. It is difficult to predict the optimal number of attempts and number of random clues (only within the floating ones) for other situations.

I use 2 similar methods to collect all UA within a subgrid. It is essentially identification of unhit UA for a multiple-solution puzzle, within the context of one of its solutions.

The first method is closer to the topic. It assumes a fixed limit of minimal UA, currently 1 million in my code, but unlimited number of solutions to process.
The solver is called, and every solution is compared to the original grid so that a (potentially non-minimal) UA is identified. The obtained UA is checked against all already known UA and is a) discarded when non-minimal - other UA which is its subset is already known, or b) added and all their supersets are identified as non-minimal and marked for later deletion.
Periodically the list of the identified UA is purged from marked as invalid UA.
Below is part of the code.
Hidden Text: Show
Code: Select all
class uaCollector {
public:
   uaCollector(grid *theGrid, const unsigned char *unknowns, const int unknownsSize);
   //uaCollector(grid *theGrid);
   ~uaCollector();
   //void byMorphs();
   bool addSolution(const char *sol);
   //bool addMorph(const char *sol);
   unsigned long long runSolver();
   void addUaToGrid();
   static const int maxSolutions = 1000000;
   //static const int maxSolutions = 200000;
   grid &g;
   const unsigned char *unknowns;
   const int unknownsSize;
   int uniqueSize;
   int uaMaxSize;
   int firstInvalidUa;
   int numInvalidUas;
   bool uaLimitedBySize;
   bm128 *uaArray;
};

uaCollector::uaCollector(grid *theGrid, const unsigned char *theUnknowns, const int theUnknownsSize)
: g(*theGrid), unknowns(theUnknowns), unknownsSize(theUnknownsSize), uniqueSize(0), firstInvalidUa(maxSolutions), numInvalidUas(0) {
   uaArray = bm128::allocate(maxSolutions); //TODO: reduce the array size
   uaMaxSize = opt.uaOpt->maxuasize;
   uaLimitedBySize = (uaMaxSize < 81);
}
uaCollector::~uaCollector() {
   bm128::deallocate(uaArray);
}

bool uaCollector::addSolution(const char *sol) {
   //compose bitmask with differences between original grid & solution
   bm128 us;
   us.clear();
   int uaSize = 0;
   if(uaLimitedBySize) {
      for(int i = 0; i < unknownsSize; i++) {
         if(sol[unknowns[i]] != g.digits[unknowns[i]]) {
            us.setBit(unknowns[i]);
            if(++uaSize > uaMaxSize) {
               return false; //skip larger UA
            }
         }
      }
   }
   else {
      for(int i = 0; i < unknownsSize; i++) {
         if(sol[unknowns[i]] != g.digits[unknowns[i]]) {
            us.setBit(unknowns[i]);
         }
      }
   }
   //do some tests
   for(int y = 0; y < uniqueSize; y++) {
      if(uaArray[y].isSubsetOf(us)) {
         return false; //skip supersets & duplicates
      }
      if(us.isSubsetOf(uaArray[y])) {
         if(!uaArray[y].isInvalid()) {
            uaArray[y].invalidate(); //mark the superset (many can exist)
            if(firstInvalidUa > y)
               firstInvalidUa = y;
            numInvalidUas++;
         }
      }
   }
   //passed the tests, add at the end of list
   if(numInvalidUas > 500 || uniqueSize >= maxSolutions) {
      //attempt compressing the uaArray by removing the invalid elements
      int compressedSize = firstInvalidUa;
      for(int i = firstInvalidUa + 1; i < uniqueSize; i++) {
         if(!uaArray[i].isInvalid()) { //skip marked
            uaArray[compressedSize++] = uaArray[i];
         }
      }
      if(compressedSize  >= maxSolutions) {
         //nothing to do, return error
         return true;
      }
      uniqueSize = compressedSize;
      firstInvalidUa = maxSolutions;
      numInvalidUas = 0;
      //fprintf(stderr, "*");
   }
   uaArray[uniqueSize++] = us;
   return false;
}
unsigned long long uaCollector::runSolver() {
   unsigned long long solutions;
   char gg[81];
   //copy the grid
   for(int i = 0; i < 81; i++)
      gg[i] = g.digits[i];
   //clear the cells of interest
   for(int i = 0; i < unknownsSize; i++)
      gg[unknowns[i]] = 0;
   solutions = solve(g.gridBM, gg, this); //for each solution except original it calls addSolution
   return solutions;
}
void uaCollector::addUaToGrid() {
   uset ua;
   for(int x = 0; x < uniqueSize; x++) {
      if(!uaArray[x].isInvalid()) { //skip marked
         ua = uaArray[x];
         ua.positionsByBitmap();
         g.usetsBySize.insert(ua);
      }
   }
}


The second method assumes all solutions are known (by solving the puzzle but storing the solutions in buffer), and there is no preferable solution grid (which is not the case here, the code comes from large UA generation where we have no fixed solution grid but are interested in UA itselves). This method could easily be adopted to a fixed preferable grid. I am including it because a) there are additional SIMD optimizations included, and b) the collected UA are also periodically sorted so that the shorter UA, which have better chance to kill other UA as non-minimal, are positioned at the top.

The code.
Hidden Text: Show
Code: Select all
struct bm96 {
   bm128 bytes[6];
   void load(const char *p) {
      bytes[0].loadUnaligned(p + 0 * 16);
      bytes[1].loadUnaligned(p + 1 * 16);
      bytes[2].loadUnaligned(p + 2 * 16);
      bytes[3].loadUnaligned(p + 3 * 16);
      bytes[4].loadUnaligned(p + 4 * 16);
      bytes[5].bitmap128.m128i_u8[0] = *(p + 5 * 16); //81th byte, don't read after the possible buffer end
   }
   void diff(const char *p, bm128& dif) const {
      bm128 pp;
      dif.clear();
      pp.loadUnaligned(p + 0 * 16);
      dif.bitmap128.m128i_u32[0] = bytes[0].diffOctets(pp);
      pp.loadUnaligned(p + 1 * 16);
      dif.bitmap128.m128i_u32[0] |= (bytes[1].diffOctets(pp) << 16);
      pp.loadUnaligned(p + 2 * 16);
      dif.bitmap128.m128i_u32[1] = bytes[2].diffOctets(pp);
      pp.loadUnaligned(p + 3 * 16);
      dif.bitmap128.m128i_u32[1] |= (bytes[3].diffOctets(pp) << 16);
      pp.loadUnaligned(p + 4 * 16);
      dif.bitmap128.m128i_u32[2] = bytes[4].diffOctets(pp);
      //pp.loadUnaligned(p + 5 * 16);
      //dif.bitmap128.m128i_u32[2] |= (bytes[5].diffOctets(pp) << 16);
      if(*(p + 5 * 16) != bytes[5].bitmap128.m128i_u8[0])
         dif.bitmap128.m128i_u32[2] |= (1 << 16);
   }
};

void findUaBySolutions(const char *solList, const int nSol) {
   int uaMaxSize = opt.uaOpt->maxuasize;
   int uaMinSize = opt.uaOpt->minuasize;
   bool uaLimitedBySize = (uaMaxSize < 81);

#ifdef _OPENMP
#pragma omp parallel for schedule(dynamic, 1)
#endif
   for(int s = 0; s < nSol; s++) {
      //bm128* uaArray = bm128::allocate(nSol);
      sizedUset* uaArray = (sizedUset*)bm128::allocate(nSol);
      const char *sp = &solList[s * 81];
      bm96 sp96;
      sp96.load(sp);
   //for(sp = solList; sp < send; sp += 81) {
      int nUa = 0;
      int numInvalidUas = 0;
      int firstInvalidUa = nSol;
      const char *ssp, *send = solList + 81 * nSol;
      for(ssp = solList; ssp < send; ssp += 81) {
         if(ssp == sp)
            continue;   //don't compare to itself
         sizedUset &us = uaArray[nUa];
         us.clear();
         if(uaLimitedBySize) {
            int uaSize = 0;
            for(int i = 0; i < 81; i++) {
               if(ssp[i] != sp[i]) {
                  us.setBit(i);
                  if(++uaSize > uaMaxSize) {
                     goto nextSol; //skip large UA
                  }
               }
            }
         }
         else {
            //compare in parallel;
            sp96.diff(ssp, us);

            //for(int i = 0; i < 81; i++) {
            //   if(ssp[i] != sp[i]) {
            //      us.setBit(i);
            //   }
            //}
         }
         //do some tests
         for(int y = 0; y < nUa; y++) {
            if(uaArray[y].isSubsetOf(us)) {
               goto nextSol; //skip supersets & duplicates
            }
            if(us.isSubsetOf(uaArray[y])) {
               if(!uaArray[y].isInvalid()) {
                  uaArray[y].invalidate(); //mark the superset (many can exist)
                  if(firstInvalidUa > y)
                     firstInvalidUa = y;
                  numInvalidUas++;
               }
            }
         }
         //passed the tests
         us.setSize();
         nUa++;
         // compress uaArray if necessary
         //if(numInvalidUas > 120) { //37"
         //if(numInvalidUas > 5) { //slow"
         if(numInvalidUas > 15) { //23"
         //if(numInvalidUas > 20) { //23"
            //attempt compressing the uaArray by removing the invalid elements
            int compressedSize = firstInvalidUa;
            for(int i = firstInvalidUa + 1; i < nUa; i++) {
               if(!uaArray[i].isInvalid()) { //skip marked
                  uaArray[compressedSize++] = uaArray[i];
               }
            }
            nUa = compressedSize;
            firstInvalidUa = nSol;
            numInvalidUas = 0;
            //std::sort(uaArray, uaArray + nUa, isBm128Smaller);
            std::sort(uaArray, uaArray + nUa, sizedUset::isSmaller);
         }
         //if(0 == nUa % 60) { //163"(10000, 60/60), 140"(10000, 15)
         //   std::sort(uaArray, uaArray + nUa, isBm128Smaller);
         //}
nextSol:
         ;
      }
      //at this point we have uaArray populated, with possible invalid UA
//#ifdef _OPENMP
//#pragma omp critical
//#endif
      for(int y = 0; y < nUa; y++) {
         sizedUset &u = uaArray[y];
         if(!u.isInvalid()) {
            //int uaSize = 0;
            //int uaSize = u.popcount_128();
            int uaSize = u.getSize();
#if 1
            //hunting large UA sets at this point we have a stream of many many minimal UA
            //let hunt for high-valency UA too
            const int min_valency = 16;
            const int min_valency_size = 20; //check large UA only
            char ip[81]; //inverted multiple-solution puzzle
            int valency = 0;
            if(uaSize >= min_valency_size) {
               for(int i = 0; i < 81; i++) {
                  if(u.isBitSet(i)) {
                     ip[i] = 0;
                  }
                  else {
                     ip[i] = sp[i];
                  }
               }
               valency = (int)solve(ip, INT_MAX);
            }
            if(uaSize >= uaMinSize || valency >= min_valency) {
#else
            if(uaSize >= uaMinSize) {
#endif
               //output the UA
               char p[81];
               for(int i = 0; i < 81; i++) {
                  if(u.isBitSet(i)) {
                     p[i] = sp[i] + '0';
                  }
                  else {
                     p[i] = '.';
                  }
               }
#ifdef _OPENMP
#pragma omp critical
#endif
               {
                  if(uaSize >= uaMinSize) {
                     printf("%81.81s\n", p);
                  }
#if 1
                  if(valency >= min_valency) {
                     printf("%81.81s@%d\n", p, valency);
                  }
#endif
                  fflush(NULL);
               }
            }
         }
      }
      bm128::deallocate(uaArray);
   }
}


The best exhaustive UA collection process based on the above methods should be a mixture of both - targeted on a preferred grid, with SIMD, with sorting by size, and w/o parallelization.

If hitting UA is done by bitmap indexes, the process of indexing is actually transposition of bit matrix and efficient SIMD algorithm is implemented in the example code for minimization, see the reference in my previous post.
[edit: few typos fixed]
dobrichev
2016 Supporter
 
Posts: 1314
Joined: 24 May 2010

Supersets

Postby Afmob » Sat Jun 29, 2013 12:24 pm

blue wrote: I would guess that you've experimented with code to count the ~6.2e+21 grids, on your own.

No, I've never done that. I use a DLX solver to generate a random grid by permuting the corresponding rows for each cell. For checking minimality, uniqueness and getting all solutions I use JSolve. Before I go into some rambling of my own, here are some results with my improved algorithms:
Code: Select all
Computation time: 1 hour

751162 samples
93142  minimal 25 hits
+----+----------+--------------+------------+
| Cl |    Count |  E(nr/grid)  | E(rel err) |
+----+----------+--------------+------------+
| 25 |        1 |   6.998e+014 |  100.00%   |
| 26 |       53 |   1.426e+015 |   17.80%   |
| 27 |      756 |   1.507e+015 |    7.13%   |
| 28 |     3480 |   7.434e+014 |    4.08%   |
| 29 |     6139 |   1.809e+014 |    3.70%   |
| 30 |     4137 |   2.032e+013 |    4.51%   |
| 31 |     1437 |   1.366e+012 |    6.70%   |
| 32 |      251 |   5.218e+010 |   13.67%   |
| 33 |       18 |   9.072e+008 |   38.49%   |
| 34 |        2 |   2.668e+007 |   70.71%   |
| 35 |        0 |   0.000e+000 |      ---   |
| 36 |        0 |   0.000e+000 |      ---   |
+----+----------+--------------+------------+

Here, your algorithm is about 3 times as fast if I compare the time it takes to compute a 28 hit. Without your suggestions, my old algorithm wouldn't have got close to those results.
Code: Select all
Computation time: 1 hour

37949037 samples
155290   minimal 28 hits
+----+----------+--------------+------------+
| Cl |    Count |  E(nr/grid)  | E(rel err) |
+----+----------+--------------+------------+
| 28 |        8 |   9.376e+014 |   35.36%   |
| 29 |       52 |   2.102e+014 |   18.45%   |
| 30 |       73 |   1.967e+013 |   14.17%   |
| 31 |       50 |   1.304e+012 |   21.35%   |
| 32 |        6 |   1.956e+010 |   40.83%   |
| 33 |        0 |   0.000e+000 |      ---   |
+----+----------+--------------+------------+

In this example, your algorithm is about 1.65 as fast which shows that my algorithm is more suited for larger subsets since it assumes that (nearly) all unhit UA have been found prior to adding clues.

The main improvement is definitely checking for possible redundancy prior to adding clue a from a UA. Another addition was using BFS but this didn't seem to improve the efficiency as much as for the subset method. My guess is that a lot of the remaining minimal UA are disjoint or have small intersections, so that a clue that hasn't been chosen yet is not likely to appear in a different UA, but this is just a (wild?) assumption.
The second addition is getting a new UA on the fly (by comparing the 2nd solution with the original one) when all precomputed UAs have been hit but the superset still has multiple solutions. This happens more often with smaller subsets. I tried only using those new UAs without precomputing UAs but this is slower since the new ones aren't necessarily minimal, so one should definitely calculate some minimal UA before solving the hitting set problem.

Those improvements will make my long weekend calculation obsolete but if the error estimates are low enough the results may still be worth posting. I'll run some tests to see which is the best choice for the subset size to get good results (that is with a small error estimate) for puzzles of size >= 32. Another idea is to use JSolve to generate random grids by randomizing the guessing step since a it takes a lot of time to build the exact cover matrix in my DLX method.
Afmob
 
Posts: 130
Joined: 28 June 2011

Class sampling

Postby Red Ed » Sat Jun 29, 2013 4:28 pm

Here's another idea for a speed-up. Recall that we're taking the mean of V ≡ Σm∈A φ(m)/Pr(m) as our number-of-minimals estimate where, in our current algorithms, A ranges uniformly over s-clue subsets of solution grids. There's nothing in the generic counting method that requires A to be uniformly distributed, so perhaps we can bias A towards "nicer" s-clue subsets. For a while, I thought that was impractical: if you have a non-uniform distribution on A then the Pr(m) terms can be hard to calculate. So let's approach it a different way.

Divide up the range of A into a few (k, say) classes. Let ClassProb(c) be the probability that a uniformly distributed A has class c. For some number of trials with uniformly-distributed A, let W(c) be the mean of V in the cases where class(A)=c. Then Σc ClassProb(cW(c) is an unbiased estimate for the population mean of V. Notice that A only has to be uniformly distributed within classes, but it can be wildly biased between classes (e.g. we can choose to spend an unnaturally large amount of time in class 1, provided that we treat all items in that class equally).

It pays to pick classes such that the behaviour of V is quite strongly dependent on class(A). To take a subsets-method example, with A ranging over 30-clue subgrids and k=3, we might calculate the sum, over boxes, of the number of clues-squared in the box, and deem A to be in the "smooth" class if the sum's <109, "rough" if the sum's >125, otherwise "normal". You'd expect many more puzzles from smooth A than from rough A, so (intuitively) perhaps we should spend longer on "smooth" A than we would otherwise have done. You could have fun coming up with more complicated definitions of the classes; most things are allowable, provided you can calculate the ClassProb values and you have an efficient way of sampling uniformly at random from within a class.

Now we can easily work out the correct amount of time to spend in each class. Let Sigma(c) be the standard deviation of V when A is in class c and let Rate(c) be the number of V we can compute per second when A is in class c. Then the optimum time spent sampling from class c is T×ClassProb(c)×Sigma(c)/sqrt(Rate(c)), where T is a scale factor chosen to fill the total time available. Sigma(c)/sqrt(Rate(c)) is the expected standard deviation of W(c) after 1 second (you don't need to calculate this, you can just measure it): the lower, the better. If Sigma/sqrt(Rate) is constant for all c then the optimum sampling time is proportionate to ClassProb(c), (edit: deleted incorrect comparison to the usual algorithm). If Sigma/sqrt(Rate) is not constant then we will spend longer on those classes for which it is worse.

I've not tested this yet, so it might turn out to be a rubbish idea, but I thought I'd better write the theory down or I'd never get round to it.
Last edited by Red Ed on Sun Jun 30, 2013 5:20 pm, edited 1 time in total.
Red Ed
 
Posts: 633
Joined: 06 June 2005

Re: Supersets

Postby Red Ed » Sun Jun 30, 2013 11:03 am

Afmob wrote:I use a DLX solver to generate a random grid by permuting the corresponding rows for each cell. For checking minimality, uniqueness and getting all solutions I use JSolve. ... Another idea is to use JSolve to generate random grids by randomizing the guessing step since a it takes a lot of time to build the exact cover matrix in my DLX method.
Unfortunately, I suspect neither method generates unbiased solution grids.

If you have a good grid generator that's not quite fast enough then one way to improve its effective speed would be to take each V to be the result of processing not just one A (s-clue subgrid) but the average of, say, ten of them.
Red Ed
 
Posts: 633
Joined: 06 June 2005

Postby Afmob » Sun Jun 30, 2013 11:33 am

My implementation of the subset method overestimates the number of minimal puzzles (despite a small error estimate) and I'm trying to look for the source of the error and I already suspected that my generator is the source. Oddly enough, the bias does not seem to effect the superset method that much. I'll have a look at your unbiased grid generation thread. So for now, rather trust blue's results though my implementation of both methods looks sound apart from the possible bias in the solution grids. :|
Afmob
 
Posts: 130
Joined: 28 June 2011

Re: Counting minimal puzzles: subsets, supersets, etc.

Postby Red Ed » Sun Jun 30, 2013 12:16 pm

Generators can be made faster and solution grid bias fixed -- that's another topic really. For this thread, I think it's much more interesting to understand the various techniques for exploring the space of c-clue subgrids and to see the effect of those techniques on the relative error estimates (which don't appear very sensitive to the source of solution grids). That's why I've been running my tests on a single set of 1000 grids read over and over again: it ensures consistency of my results and keeps solution-grid generation out of the timings. I've been impressed by the speed of your and Blue's algorithms!
Red Ed
 
Posts: 633
Joined: 06 June 2005

Bias from grid generation

Postby Afmob » Sun Jun 30, 2013 12:32 pm

Supposing that my error comes from the grid generation, the subsets estimations are definitely affected by the bias.
Code: Select all
Computation time: 1 hour

18304542 samples
210930   unique 30 hits
+----+----------+--------------+------------+
| Cl |    Count |  E(nr/grid)  | E(rel err) |
+----+----------+--------------+------------+
| 19 |        1 |   1.514e+003 |  100.00%   |
| 20 |      588 |   5.019e+006 |    8.09%   |
| 21 |    31904 |   1.661e+009 |    2.06%   |
| 22 |   577533 |   2.005e+011 |    0.86%   |
| 23 |  3240071 |   8.295e+012 |    0.50%   |
| 24 |  5889873 |   1.249e+014 |    0.36%   |
| 25 |  3577132 |   7.208e+014 |    0.32%   |
| 26 |   738477 |   1.667e+015 |    0.40%   |
| 27 |    54506 |   1.691e+015 |    0.84%   |
| 28 |     1483 |   8.248e+014 |    3.63%   |
| 29 |       14 |   2.072e+014 |   30.31%   |
| 30 |        0 |   0.000e+000 |      ---   |
+----+----------+--------------+------------+

Though the distribution of the counts looks good, the sample ratio (that is I need about 87 grids to get a sample) is off since you and blue need about 98 grids for a sample. I'll edit this when I've found the source of error.

Edit: The generator is the source of error. Here are my results if I modify my DLX solver:
Code: Select all
Computation time: 1 hour

34245043 samples
215253   unique 30 hits
+----+----------+--------------+------------+
| Cl |    Count |  E(nr/grid)  | E(rel err) |
+----+----------+--------------+------------+
| 19 |        3 |   2.428e+003 |   74.54%   |
| 20 |      218 |   9.946e+005 |   11.01%   |
| 21 |    13683 |   3.808e+008 |    2.54%   |
| 22 |   273770 |   5.080e+010 |    0.99%   |
| 23 |  1828895 |   2.503e+012 |    0.55%   |
| 24 |  4108806 |   4.659e+013 |    0.37%   |
| 25 |  3186469 |   3.432e+014 |    0.32%   |
| 26 |   867000 |   1.046e+015 |    0.37%   |
| 27 |    82683 |   1.372e+015 |    0.72%   |
| 28 |     2741 |   8.184e+014 |    2.63%   |
| 29 |       36 |   2.848e+014 |   18.00%   |
| 30 |        0 |   0.000e+000 |      ---   |
+----+----------+--------------+------------+

Here, I underestimate the values and the sample ratio (~159) is larger. In both methods the randomization comes from permuting the rows for each cell but in the first method I look for columns of size less or equal to one. If there are none it chooses the cell with the least possibilites. The second method uses the optimal column search that is the smallest sized column.

The superset method yields different results. It's results are less dependent on the bias of the generator though still recognizable. It's seems that the sample ratio is a good indicator on how unbiased the estimations are. For the subset method (starting with 30 clue valid puzzles) we have (98 | 87 | 159) and the superset method (starting with 25 clue minimal puzzles) gives (8.01 | 8.06 | 7.90) ratios which should be understood as follows: (blue's ratio | my first DLX method | my second DLX method).

Now I just have to find a fast unbiased generator or write one myself though I would definitely prefer the first option since I want to focus on improving the subset/superset method.
Last edited by Afmob on Mon Jul 01, 2013 4:43 am, edited 4 times in total.
Afmob
 
Posts: 130
Joined: 28 June 2011

Re: Class sampling

Postby Red Ed » Sun Jun 30, 2013 6:54 pm

I wrote:I've not tested this yet, so it might turn out to be a rubbish idea, but I thought I'd better write the theory down or I'd never get round to it.
Preliminary investigation suggests the idea will work in the tails of the distribution. The key parameter in determining whether there's any benefit to be had is Sigma*sqrt(Rate): if it's constant across classes then the fancy class-sampling idea doesn't help; if it varies significantly, class-sampling is beneficial. (I was mistaken, originally, in thinking it was Sigma/sqrt(Rate) that had to be non-constant.)

You have to decide what c to optimise for. In the subsets-of-30-clues method, if you optimise for discovery of (say) 21-clue puzzles then you should expect improved performance around the 20-22 clue region, no change around 25 clues, but to lose out for c close to 30.
Red Ed
 
Posts: 633
Joined: 06 June 2005

Re: Bias from grid generation

Postby m_b_metcalf » Mon Jul 01, 2013 8:34 am

Afmob wrote:Now I just have to find a fast unbiased generator or write one myself though I would definitely prefer the first option since I want to focus on improving the subset/superset method.

Red Ed examined the output of my generator back in January, 2007, and gave it a stamp of approval for randomness (test can be easily repeated). It's not that fast and is embedded in a larger program, but I have prepared a Windows .exe file that asks the user to supply the number of grids required and writes them with no compression to puzzle.txt. On a 1.6 GHz PC it takes 98s to generate 1 million. Each run begins with a fresh PRNG seed. I can send the .exe file by PM to anyone who wants it. (The source code is Fortran 95.)

Regards,

Mike Metcalf
User avatar
m_b_metcalf
2017 Supporter
 
Posts: 8335
Joined: 15 May 2006
Location: Berlin

Postby Afmob » Mon Jul 01, 2013 9:17 am

m_b_metcalf wrote:I can send the .exe file by PM to anyone who wants it.

Thanks, I'll contact you soon. Nevertheless, I might give the B2347 method a try.
Afmob
 
Posts: 130
Joined: 28 June 2011

Re: Counting minimal puzzles: subsets, supersets, etc.

Postby Red Ed » Mon Jul 01, 2013 5:22 pm

I've finally got round to posting my generator:
http://forum.enjoysudoku.com/unbiased-grid-generation-b2347-method-t31236.html

WARNING: it doesn't do the last step of picking a random validity-preserving transform to "spin" the grid. That makes no difference, though, for the algorithms discussed here.
Red Ed
 
Posts: 633
Joined: 06 June 2005

Re: ~TE(1)

Postby eleven » Mon Jul 01, 2013 10:42 pm

OT:
blue wrote:These are the final numerical results for ~TE(1) and minimal puzzles ...

Thanks blue, for these investigations. They showed me, that yet another sudoku conjecture i had, was wrong, namely that ~TE(1) puzzles would have an average ER beyond 9.5. With hindsight that is easily explained. My "empiric results" were as biased as the sets i worked on.
Now i could say something about conclusions i could can draw concerning the grey zone or the clue distributions of the hardest, but i neither have time nor interest in the moment.
eleven
 
Posts: 1559
Joined: 10 February 2008

PreviousNext

Return to General