Guess Theory 101 & 102

Programs which generate, solve, and analyze Sudoku puzzles

Guess Theory 101 & 102

Postby Mathimagics » Thu Feb 28, 2019 7:35 am

When a solver has exhausted all of its "solving techniques", and unsolved cells remain, then generally we either give up (not a very interesting topic), OR we resort to DFS (depth first search), aka "brute-force", "T&E", "backtracking" etc.

In most applications, the way that guess is made (ie: which candidate cell+digit is selected to try) is neither here nor there, 9 x 9 Sudoku solvers can solve even low-clue, minimal puzzles, so fast that it is unlikely to matter.

It is only when we move outside the safe world of 9x9 puzzles, into, say 16x16 puzzles, or multiple 9x9 overlapped grids like Samurai, that we discover the potentially catastrophic consequences of the "bad guess".

"Guess Theory" asks the fundamental question:
Q: What candidate should we try next?

but sadly, everything we know currently suggests only one answer:
A: I have no idea! Your guess is as good as mine!


The most common NCS (next candidate selection) strategy is what I call the "taxi-rank" method. TR selects the cell with the minimum NPV (number of possible values), and where there is multiple choice, takes the first one in the list (however this list is built), and then takes first (lowest) digit candidate for that cell.

Mladen dobrichev found that a tweak to this method gave better results (overall) for 9x9 puzzles. In his fsss2 solver, given a choice between cells with the same (minimum) NPV, he selects the digit first, ie the lowest digit that appears in the candidate list, and then the first cell in the list that has this digit as a candidate. So effectively he has inverted the TR method to pick "first digit" then "first cell". I call this method MR (Mladen's Rule).

I ran extensive tests using only low-clue 16x16 puzzles, and compared these two methods, plus a 3rd method, XR which is just "select randomly". These tests showed that the only appreciable difference between them (in terms of the # of guesses required to solve), was that different puzzles resulted in bad guesses for each method. Yes, the XR method was inclined to encounter more "bad guess" cases, but really there was little difference. Especially when just a single instance of "bad guess" syndrome was like running into a brick wall - solve times went from the milliseconds scale to HOURS in some cases.

Unless one is willing to spend some time looking at the full search-tree below (ie some form of look-ahead), there is little that can be done to avoid these cases. The only effective "pathological case prevention" method is to apply "guess limits" - so the solver now has an extra return code to indicate that this limit was reached. One can then try an alternative NCS method, and most of the time this will work.
Last edited by Mathimagics on Fri Mar 01, 2019 12:48 pm, edited 2 times in total.
User avatar
Mathimagics
2017 Supporter
 
Posts: 1329
Joined: 27 May 2015
Location: Canberra

Guess Theory 102

Postby Mathimagics » Thu Feb 28, 2019 7:51 am

Some additional observations:

  • "pathological cases" are not the result of a single "bad guess", but rather a chain of bad guesses, each of which worsens the situation by enlarging the search tree
  • Mladen also introduced a clever trick with method MR (but which can be applied to TR also). Since, in his solver, NCS is expensive compared to singles-based eliminations, it makes sense to "recycle" the list of candidates as far as possible. If one starts with a list of bi-valued candidate cells, then as we proceed to look further down the tree, these remain valid (unless converted to "solved" or "eliminated" state), so no recalculation is required until this list is exhausted. Nice! 8-).

    But as observed above, altering the guess sequence does not change the underlying problem we have identified here, it just changes the puzzles for which we will find "bad guess syndrome".
  • DLX solvers typically use what Knuth called "Heuristic S" - this is just the TR method. DLX solvers are also DFS solvers, so they are also susceptible to "bad guess syndrome"
User avatar
Mathimagics
2017 Supporter
 
Posts: 1329
Joined: 27 May 2015
Location: Canberra

Re: Guess Theory 101

Postby Leren » Thu Feb 28, 2019 8:04 am

One trick I cottoned onto in the PX and X projects was to always guess first r5c5 (if it's available), as this sees more cells than any other. The result : an immediate 20% increase in average speed, not bad for just moving 4 lines of code.

The obvious next trick was to next guess the other cells on the diagonals, but this only works well if they have the minimum number of candidates. The result was not so spectacular bur still worth it, a further increase of about 10% on average.

Leren
Leren
 
Posts: 3608
Joined: 03 June 2012

A Case Study

Postby Mathimagics » Thu Feb 28, 2019 8:07 am

I currently have an example that illustrates the impact of "bad guess syndrome".

Hajime has produced an example of what I call a "Tutti-Frutti" Samurai puzzle. The 5 grids have independent Sudoku modes, in this case we have 4 grids with "Jigsaw + Sudoku Boxes", and a central grid with "SudokuX (Sudoku + Diagonals).

I've been working on a similar thing, and thought a useful experiment would be to attempt to reduce this puzzle to a minimal form. My initial solver is basically a DLX solver (1-9 but on a 21 x 21 grid, with 369 cells actually in use).

So the grid uses less cell settings than 16x16 Sudoku, but many more cells (369 vs 256). I reduce the puzzle by selecting a clue at random, testing it for redundancy, fixing it or removing it depending on the result.

My first attempt produced a minimal puzzle in less than 25 minutes. But my second attempt has been running for over 12 hours - a few 30-60 minute clue test times, and finally a genuine pathological case, where testing the clue removal has been running for 8 hours, and God knows how long it will actually take to complete!

[EDIT] It finished 4 hours later, approx. 12 hours to test that particular clue. So 16 hours all up for this particular reduction.
Last edited by Mathimagics on Fri Mar 01, 2019 12:05 pm, edited 2 times in total.
User avatar
Mathimagics
2017 Supporter
 
Posts: 1329
Joined: 27 May 2015
Location: Canberra

Re: Guess Theory 101

Postby Mathimagics » Thu Feb 28, 2019 8:16 am

Leren wrote:One trick I cottoned onto in the PX and X projects was to always guess first r5c5 (if it's available), as this sees more cells than any other.


This is certainly a useful heuristic for single 9x9 grid case.

My Samurai case above only has diagonals in the central grid, and this grid has the lowest number of givens. It isn't easy to tell a DLX solver in these circumstances when & how to apply the heuristic.
User avatar
Mathimagics
2017 Supporter
 
Posts: 1329
Joined: 27 May 2015
Location: Canberra

Re: Guess Theory 101

Postby Mathimagics » Thu Feb 28, 2019 8:24 am

The Samurai case raises an interesting question, though.

One thing I learned from Kakuro experiments with "diabolical" puzzles, was that NCS strategies like TR can focus the solver on sections of the grid that have little impact on each other. So if the bi-value list is "scattered" around a large grid, much time is wasted.

Same applies to Samurai - should the NCS strategy concentrate on the bi-values (or min-NPV vases) for the one grid? Most probably yes, so I will need to look into that … it could perhaps first select the grid with the most min-NPV candidate cells, then apply TR.
User avatar
Mathimagics
2017 Supporter
 
Posts: 1329
Joined: 27 May 2015
Location: Canberra

Re: Guess Theory 101

Postby Leren » Thu Feb 28, 2019 8:34 am

The percentages I quoted above were abased on a random sample of puzzles, but the tricks were very effective for otherwise slow to solve (does that mean hard ? :D ) puzzles.

eg The first time I solved one of the 9 clue PX puzzles my slow Excel solver it took about 35 seconds. With the tricks in place that's now down to less than one second.

Leren
Leren
 
Posts: 3608
Joined: 03 June 2012

Re: Guess Theory 101

Postby dobrichev » Thu Feb 28, 2019 9:47 am

Mathimagics wrote:"Guess Theory" asks the fundamental question:
Q: What candidate should we try next?

but sadly, everything we know currently suggests only one answer:
A: I have no idea! Your guess is as good as mine!


Hi, I hope in the above message "we" doesn't cover the whole humankind.

See this post considering vanilla 9x9 sudoku as well as the discussion above.
I can add that strategy for choosing from the equally rated candidates from left to right or from right to left depends on the density of the unknowns and for puzzle stream converted to least lexicographical representation statistically the non-givens are concentrated at left.
For 16x16 a more comprehensive guessing strategy could give better overall results (and there I am part of "we").
dobrichev
2016 Supporter
 
Posts: 1745
Joined: 24 May 2010

Re: Guess Theory 101

Postby Mathimagics » Thu Feb 28, 2019 11:12 am

Hi Mladen,

"We", such a small word, so many nuances … :?

Too many math papers have been read over too many years, so I automatically slip into "we" mode: We = Author + Reader

PS: I have found another possible use for that bm256 class: we (and here "we" means you and I and blue, but probably only means me!) can turn dSolver/fsss2 into a dSamurai solver with that!!
User avatar
Mathimagics
2017 Supporter
 
Posts: 1329
Joined: 27 May 2015
Location: Canberra

Re: Guess Theory 101

Postby champagne » Fri Mar 01, 2019 2:19 am

Hi leren,

some late reaction to this

Leren wrote:One trick I cottoned onto in the PX and X projects was to always guess first r5c5 (if it's available), as this sees more cells than any other. The result : an immediate 20% increase in average speed, not bad for just moving 4 lines of code.

The obvious next trick was to next guess the other cells on the diagonals, but this only works well if they have the minimum number of candidates. The result was not so spectacular bur still worth it, a further increase of about 10% on average.

Leren


as this sees more cells than any other

any cell sees 20 cells, so either the wording is specific to your case or you have anotherreason to make a better choice in r5c5.
but something seems of value, A strategy killing more candidates is in average better.

I tested and implemented with success the selection of a bi-value cell in the band having the highest number of unsolved cells.
The same could be done using band + stack,
I also considered to do the same on a digit bi values, but the criteria giving the best choice must be cheap and I did not find so far the quick way to select the best digit bi value.
champagne
2017 Supporter
 
Posts: 6979
Joined: 02 August 2007
Location: France Brittany

Re: Guess Theory 101

Postby Mathimagics » Fri Mar 01, 2019 3:07 am

champagne wrote:any cell sees 20 cells, so either the wording is specific to your case or you have another reason to make a better choice in r5c5.

Leren is indeed talking about specific cases like SudokuX, SudokuPX which have additional diagonal constraints.


Mladen and blue use the term "bi-local" for "digit bi-values". Which you prefer is of course optional, but I like "bi-local" - it's shorter, and has the added bonus of amusement - it sounds like an advertising campaign slogan for supporting your local grocer or liquor store. "Don't go to the mall - Buy local!" 8-)
User avatar
Mathimagics
2017 Supporter
 
Posts: 1329
Joined: 27 May 2015
Location: Canberra

Re: Guess Theory 101

Postby champagne » Fri Mar 01, 2019 4:28 am

Mathimagics wrote: Buy local!" 8-)

For me, currently on the beach (on a kite spot), it's

swim local
kite local (not me my grand son :D )
champagne
2017 Supporter
 
Posts: 6979
Joined: 02 August 2007
Location: France Brittany

Re: Guess Theory 101

Postby Mathimagics » Fri Mar 01, 2019 5:45 am

Champagne in Mauritius? I prefer a pina colada … (now on special at your local liquor store - buy local!)

By the way, have you seen any dodos about the place? 8-)
User avatar
Mathimagics
2017 Supporter
 
Posts: 1329
Joined: 27 May 2015
Location: Canberra

Re: Guess Theory 101

Postby Leren » Fri Mar 01, 2019 6:14 am

Champagne wrote : any cell sees 20 cells

Hi Champagne,

In Sudoku PX all cells see at least 24 cells, except r5c5, which sees 32 cells, and other cells on a diagonal see 28 cells.

In Sudoku X all cells see at least 20 cells, except r5c5, which sees 32 cells, and other cells on a diagonal see 26 cells.

Leren
Leren
 
Posts: 3608
Joined: 03 June 2012

Re: Guess Theory 101

Postby dobrichev » Fri Mar 01, 2019 6:44 am

Mathimagics wrote:Mladen and blue use the term "bi-local" for "digit bi-values".

I am not sure whether you got the point.

Number of occurrences of pemcilmark for particular digit in particular house limits digit's location. A digit that can be placed in only 2 cells within a house is therefore bi-local. Traversing the search tree you fix the digit and house and iterate the locations.

Number of digits that can be placed in particular cell limits cell's values. A cell having only 2 value candidates is therefore bi-value. Traversing the search tree you fix the cell and iterate the candidate digits.

The referenced discussion is about bi-local vs bi-value guessing.
dobrichev
2016 Supporter
 
Posts: 1745
Joined: 24 May 2010

Next

Return to Software