Guess Theory 101 & 102

Programs which generate, solve, and analyze Sudoku puzzles

Re: Guess Theory 101

Postby Mathimagics » Fri Mar 01, 2019 7:52 am

dobrichev wrote:I am not sure whether you got the point.

This is entirely possible, especially with my track record! 8-)

But really I am not sure what "the point" in question is!

My understanding of the terms "bi-value" and "bi-local" seems to conform to yours, and when champagne talks of "bi-valued cells", he clearly means "bi-values", and so when he talks of "digit bi-values" these are surely "bi-locals", are they not?

Or is your point really about whether bi-values/bi-locals actually qualify as "guesses"?

Cheers
MM
User avatar
Mathimagics
2017 Supporter
 
Posts: 1264
Joined: 27 May 2015
Location: Canberra

Re: Guess Theory 101

Postby champagne » Fri Mar 01, 2019 8:06 am

Leren wrote:
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


I forgot this recent big work on sudoku X sudoku P sudoku PX.

In this case, I agree that r5c5 has a good chance to be a good place to apply the strategy "kill more candidates". This could explain your results.
champagne
2017 Supporter
 
Posts: 6949
Joined: 02 August 2007
Location: France Brittany

Re: Guess Theory 101

Postby Leren » Fri Mar 01, 2019 10:26 am

Looks to me like Mathimagics is confused by the term "local" link, which by mutual agreement and understood by most, is a link that is not in the one cell. I must admit that this (rather weird) terminology is possibly confusing, but I've never concerned myself with semantics and just got on with it. So, for example, with L2 and L3 wings, none of the strong links is in the same cell. Go figure :?

Leren
Leren
 
Posts: 3567
Joined: 03 June 2012

Re: Guess Theory 101

Postby Mathimagics » Fri Mar 01, 2019 12:00 pm

Mathimagics is indeed confused - by just about everything and anything Leren says above. Links, X-wings etc, it's all Greek to me! :lol:

The topic here is NCS strategies, so I suppose AST's (advanced solving techniques) are kind of relevant, but I'm really talking about simple brute-force (DFS) solvers with singles-only capabilities ... and about how NCS is a generic problem for all DFS solvers, but only for certain circumstances.

But a funny thing happened on the way to the forum ... 8-)

Anyway, solvers with AST's are certainly less inclined to suffer, and the problem hardly exists at all for 9x9 grids in any case, but becomes a real issue for:

  • larger grid sizes
and
  • low-clue puzzles. Conventional or "human-solvable" puzzle solvers need not even consider this problem, no matter how great your gattai! This will only be a real problem for geeks like me who are investigating minimal puzzle forms, and of course the greatest question of all, what is the minimum # of clues needed for a valid puzzle?


Cheers!
MM
User avatar
Mathimagics
2017 Supporter
 
Posts: 1264
Joined: 27 May 2015
Location: Canberra

Guess Theory 102

Postby Mathimagics » Fri Mar 01, 2019 12:45 pm

Ok, let's move on to the specific problem area described above, and call this "Guess Theory 102", and reduce the class size! 8-)

So all you P&P solvers can go home, nothing to see here!

"GT 102" considers the problem in the extreme cases - low-clue puzzles on large grids. A typical scenario is that we have 16x16 grid or bigger, so Samurai's are included, and we are looking to obtain a minimal puzzle form from some larger set of clues. We select a clue at random, test it for redundancy, keep it if we have to, or else remove it.

This process is repeated, and we notice that some clue tests are taking longer than others, and then we hit one that seemingly takes forever! That, friends, is BGS (bad guess syndrome).

I wrote: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.

I should really have said "the only way (aside from developing new, smarter, NCS strategies) ..."

A variation on this approach that would probably handle most problems on 16 x 16 grids, say, is to use a parallel approach. Set an appropriate guess limit, and when the solver "fails", start parallel threads with each thread using a different NCS strategy. When the first one completes you simply kill the others, and thus get close to the best possible result. So, an fsss2-like solver might start 4 threads, MR and TR, with and without TC recycling.

This at least offers a pain minimisation option while we (those of us who are still here :lol: ) try to come up with better strategies …
User avatar
Mathimagics
2017 Supporter
 
Posts: 1264
Joined: 27 May 2015
Location: Canberra

Re: Guess Theory 102

Postby m_b_metcalf » Fri Mar 01, 2019 1:08 pm

Mathimagics wrote:This at least offers a pain minimisation option while we (those of us who are still here :lol: ) try to come up with better strategies …

I agree with all you've written, but I've always had that nasty feeling that a redundancy test for a clue that one has 'given up' on might have completed positively and so minimality has not been proven beyond doubt.

Mike

P.s. This reminds me of ancient discussions about megaclues: the clue in question is common to multiple unavoidable sets. Thus, one can make a test that a clue is not the only one in an unavoidable set before trying to remove it.
User avatar
m_b_metcalf
2017 Supporter
 
Posts: 10012
Joined: 15 May 2006
Location: Berlin

Re: Guess Theory 102

Postby Mathimagics » Fri Mar 01, 2019 3:04 pm

Hi Mike,
m_b_metcalf wrote:I've always had that nasty feeling that a redundancy test for a clue that one has 'given up' on might have completed positively and so minimality has not been proven beyond doubt.

I didn't intend to imply that we would ever give up on any clue - sorry if I was unclear.

In the minimal puzzle reduction algorithm, we must necessarily obtain the chosen clue's individual status (redundant or not) in the current context (ie the partially reduced puzzle state).

So the "pain minimisation" approach suggests only that if the clue test fails (by exceeding our guess limit without a result), we retest that clue via the following:

  • temporarily disable the guess limit
  • start the parallel threads
  • wait for the first thread to complete (that's our test result)
  • kill the threads still running
  • restore the guess limit

This maintains the integrity of the reduction process, I think.

PS: Welcome to GT102! 8-)

Hmmm, you are just in time for the first assignment!

"Consider an extension to the Pain-Min algorithm: if all threads exceed some absolute guess limit, we back up one or more levels in the reduction chain and select a different clue. Is there an 'optimal' (time minimising) algorithm? Discuss...".
User avatar
Mathimagics
2017 Supporter
 
Posts: 1264
Joined: 27 May 2015
Location: Canberra

Re: Guess Theory 101 & 102

Postby Hajime » Fri Mar 01, 2019 4:01 pm

What one could do is when 2 possibilities remain (in a cell or in a house) calculate both for this level en keep them and saved. Continue to the next level (of recursion) with the one that has the most candidates eliminated. At this level you may have calculated 1 possibility too many, but it may be better than get lost in the next level(s). If this leads to no solution, try the other one, that already have been calculated (restore) en do the next level with this second one.
[when 3 possibilities remain, calculate 3, save them an go further with the most eliminated one]
Last edited by Hajime on Sat Mar 02, 2019 7:48 am, edited 1 time in total.
User avatar
Hajime
 
Posts: 75
Joined: 20 April 2018
Location: Netherlands

Re: Guess Theory 102

Postby m_b_metcalf » Fri Mar 01, 2019 4:32 pm

Mathimagics wrote:Hmmm, you are just in time for the first assignment!

"Consider an extension to the Pain-Min algorithm: if all threads exceed some absolute guess limit, we back up one or more levels in the reduction chain and select a different clue. Is there an 'optimal' (time minimising) algorithm? Discuss...".

Well, I think I'll pass on that, especially as I start some more travels soon. I might pursue the unavoidable set approach though, later. I have some UA4 and UA6 code already written that I can maybe adapt for bigger puzzles.

Regards,

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

Re: Guess Theory 101 & 102

Postby Mathimagics » Fri Mar 01, 2019 5:15 pm

Hajime,

Yes, certainly "look-ahead" strategies such as the "most candidates eliminated" model do look attractive, and definitely worthy of consideration.

Surprisingly, my initial tests on 9x9 Sudoku's with low-clue puzzles gave disappointing results, but perhaps this will be different with larger grids, and/or Samurai's. More work is needed on this …


Mike,

UA's too are yet another area that needs some investigation. Variants: UA's for variant modes are less easy to find (I seem to recall) than for "vanilla Sudoku", which is yet another aspect to consider.


Hmmm … I can already see how GT, originally a "one-semester course" (seminars only) could rapidly evolve into a full 4-year degree program ... :?
User avatar
Mathimagics
2017 Supporter
 
Posts: 1264
Joined: 27 May 2015
Location: Canberra

Re: Guess Theory 101 & 102

Postby dobrichev » Fri Mar 01, 2019 10:34 pm

Hajime wrote:What one could do is when 2 possibilities remain (in a cell or in a house) calculate both for this level en keep them and saved. Continue to the next level (of recursion) with the one that has the most candidates eliminated.

Apply the same logic even on the first candidate by choosing the cell or house with most possibilities and doing immediate most candidates elimination. Bad prognosis follow.
dobrichev
2016 Supporter
 
Posts: 1707
Joined: 24 May 2010

Re: Guess Theory 102

Postby dobrichev » Fri Mar 01, 2019 10:39 pm

Mathimagics wrote:... and call this "Guess Theory 102"…

With all my respect there should be something wrong in a forum that constantly produces 7 theories per week.
dobrichev
2016 Supporter
 
Posts: 1707
Joined: 24 May 2010

Re: Guess Theory 101 & 102

Postby Mathimagics » Sat Mar 02, 2019 12:53 am

The number is just my little joke - in US colleges/universities "XXX 101" is a code that usually means "Introduction to XXX", "XXX 102" is the same subject but at the next level.

My sense of humour probably loses something in translation, indeed perhaps it loses something even where there is no translation involved ... :roll:

Too many theories? :?:

I see them as something positive, an indication that people are thinking about a problem. :idea:
User avatar
Mathimagics
2017 Supporter
 
Posts: 1264
Joined: 27 May 2015
Location: Canberra

Re: Guess Theory 101 & 102

Postby coloin » Sun Mar 03, 2019 4:36 pm

Mathimagics wrote:......, 9 x 9 Sudoku solvers can solve even low-clue, minimal puzzles, so fast that it is unlikely to matter..

well it might not be relevant
but i always thought that high rated puzzles with suexratt ... were high rated because they were difficult to guess / solve with backtracking software
Code: Select all
+---+---+---+
|..3|...|...|
|4..|.8.|.36|
|..8|...|1..|
+---+---+---+
|.4.|.6.|.73|
|...|9..|...|
|...|..2|..5|
+---+---+---+
|..4|.7.|.68|
|6..|...|...|
|7..|6..|5..|
+---+---+---+
there are at least 4 bi-values though ....
we never really got to the reason behind the rating of these puzzles .. ?
coloin
 
Posts: 1790
Joined: 05 May 2005

Re: Guess Theory 101 & 102

Postby Mathimagics » Sun Mar 03, 2019 5:58 pm

Hi coloin,

It's true that your example has a fairly high "guess count" (my solver needed 558 guesses to solve it), but only relative to other Sudoku 9x9's. When the solver can process perhaps 100K guesses a second, the "difficulty" level is largely theoretical ...

As you increase the grid size, though, you get a very much larger guess-count range, plus the guesses/second rate rapidly declines ... and that can cause genuine difficulties, for sure ...
User avatar
Mathimagics
2017 Supporter
 
Posts: 1264
Joined: 27 May 2015
Location: Canberra

PreviousNext

Return to Software