Phil's Sudoku Solver

Programs which generate, solve, and analyze Sudoku puzzles

Re: Phil's Sudoku Solver

Postby pjb » Wed Apr 05, 2017 10:39 pm

Thanks for those of you who gave constructive criticism. The program (www.philsfolly.net.au) has undergone a further round of improvements. In particular I have amassed a large collection of examples of deadly patterns for those interested in this topic.
Phil
pjb
2014 Supporter
 
Posts: 2462
Joined: 11 September 2011
Location: Sydney, Australia

Re: Phil's Sudoku Solver

Postby rob.pertienne » Wed Jun 24, 2020 2:42 pm

Hi Phil
I tried to search the SKloop for the grid
... 1.9 ...... 6.5 ..... 6.7.5 ... 1 ..... 4 ... 57.18..3 ....... 14 ...... .3..7.8.6 ... 2 ..... 9. Patterns Game tarek Feb 19, 2009
which is given in the loops documentation.
But the resolution requires a too long amount of time and the program must be stopped.
Perhaps there is a "detail" that blocks the calculation.
I must thank you for your program which is very useful for me to understand the logic of all the operations that one can do on a sudoku puzzle.

Robert Pertienne
rob.pertienne
 
Posts: 1
Joined: 24 June 2020

Re: Phil's Sudoku Solver

Postby ghfick » Thu Jun 25, 2020 6:00 pm

I tried this puzzle. The solver does take quite a while but it eventually presents an 'Almost (+3) SK Loop'. As Phil points out in the help file, this 'Almost' SK Loop requires a massive number of checks. This step is not for human solving. I believe it remains an open question as to when 'Almost' SK Loops have a direct [non-assumptive] logic.
The solver does find an MSLS quite quickly.
ghfick
 
Posts: 161
Joined: 06 April 2016

Re: Phil's Sudoku Solver

Postby SpAce » Thu Jun 25, 2020 6:54 pm

ghfick wrote:I believe it remains an open question as to when 'Almost' SK Loops have a direct [non-assumptive] logic.

As far as I know, it's pure T&E, and not exactly efficient at that. I haven't seen a single example where the Almost-SK-Loop approach would make practical sense for a manual solver (or even a software solver). I've expressed my reasonings here and here. Phil himself agreed here:

pjb wrote:Regarding the almost SK loop (+1) section, I couldn't agree more that the trial and error routine is ugly. If it were possible to predict which of the eliminations is false and thus avoid T&E, the whole thing would be far more useful, but so far this has eluded me.

So, I don't really believe it's an open question at the moment. If someone does find an actually useful example of that approach, then it would turn into an open question. I think I might have laid out some parameters what it would probably take in those two linked posts, as well as here.
User avatar
SpAce
 
Posts: 2671
Joined: 22 May 2017

Re: Phil's Sudoku Solver

Postby pjb » Fri Jun 26, 2020 6:44 am

What I clearly point out is that these +1,+2,and +3 almost SK loops are simply based on numerous observations (I really mean numerous), and the method never fails to deliver correct eliminations. I have hoped that someone cleverer than me could discover a theoretical basis to prove they are valid, and a way to avoid the T&E aspect. They are very powerful, for example the once supposedly most difficult puzzle "escargot" is solved in one move.

Cheers, Phil
pjb
2014 Supporter
 
Posts: 2462
Joined: 11 September 2011
Location: Sydney, Australia

Re: Phil's Sudoku Solver

Postby SpAce » Fri Jun 26, 2020 9:27 am

pjb wrote:What I clearly point out is that these +1,+2,and +3 almost SK loops are simply based on numerous observations (I really mean numerous), and the method never fails to deliver correct eliminations. I have hoped that someone cleverer than me could discover a theoretical basis to prove they are valid

I thought I already did when this was first discussed (see the links in my previous post). To me there's no question that the approach is theoretically valid. It just doesn't make any practical sense to me.

Btw, its real value is not in producing eliminations but placements by finding the false eliminations in the list of PEs (potential eliminations). That, however, only happens once you've T&E-eliminated all the real eliminations and know the rest of the PEs must be true candidates. That's why it's better to have as few PEs as possible, which is of course the exact opposite of a real SK-Loop. The PE eliminations are direct results of T&E, and it's misleading to consider them results of the "almost-SK-loop" move at all.

The only valuable conclusion happens when all of the real eliminations are already eliminated (by T&E), and the survivors can be placed. That's the real "almost-SK-loop" move. All the prerequisite T&E eliminations before it should be considered separate moves, because they're valid eliminations even if you never complete the procedure.

, and a way to avoid the T&E aspect.

I thought I already did that too, by theorizing how the PEs could be used as a SIS (strong inference set). However, that approach would only make practical sense if the number of PEs is very small and the resulting SIS can find something worthwhile to eliminate.

They are very powerful, for example the once supposedly most difficult puzzle "escargot" is solved in one move.

T&E can solve everything, so is that really a miracle? What I have pointed out is that there are probably much easier and more efficient ways to employ T&E than this. I don't think you've made any effort to remove that suspicion. Thus, I still can't see any practical value to this method. I think David pointed out a long time ago that almost-MSLSs (Rank 1+) are practically useless because there's no way to know which PEs are false (without T&E testing them all, which makes no sense). I think these exercises have only underscored his conjecture, not disproved it.

Btw, how can you call it "one move" if you have to test 15-18 candidates for contradictions? That's more like 15-18 T&E moves (one for each elimination) + 1 "almost-SK-loop" move (to place the survivors that are now known to be true candidates). Hardly efficient or elegant. Besides, of those 18 PEs that you need to test in this case, only two (59r9c4) produce a contradiction with simple T&E (basic techniques, no nesting). I haven't checked how many levels of nesting the others need, but in any case, I think it's pretty clear that it makes no sense whatsoever for a manual solver (or even a software solver seeing how long it takes for your solver to do it). Am I wrong?

AI Escargot:

Code: Select all
.-------------------.-------------------------.------------------------.
| 1     2568   2468 | *458      35-4   7      | *246    9         36-4 |
| 457   3      46   | *1459     2      159    | *1467   6-4+7     8    |
| 2478  278    9    |  6       *134   *138    |  5     *2347     *134  |
:-------------------+-------------------------+------------------------:
| 2478  278    5    |  3       *167   *126    |  9     *4678     *146  |
| 479   1      34   | *579      8      569    | *467    356-7+4   2    |
| 6     2789   238  | *12579    159-7  4      | *178    35-78     135  |
:-------------------+-------------------------+------------------------:
| 3     25689  268  |  2478-59  45679  25689  |  248-6  1         4569 |
| 2589  4      1    |  28-5+9   3569   235689 |  28-6   2568      7    |
| 2589  25689  7    |  248-159  14569  125689 |  3      24568     4569 |
'-------------------'-------------------------'------------------------'

Almost-almost-almost MSLS (I refuse to call it "almost-SK-loop" as I don't see much resemblance to the real thing):

16x19 (Rank 3): {34N5689 1256N47 \ 1r34 1c47 2b35 3r3 4b236 5c4 6r4 6c7 7b356 8b26 9c4}

PEs:

Code: Select all
-1 r9c4             (1)
-4 r1c59,r2c8,r5c8* (4)
-5 r789c4           (3)
-6 r78c7            (2)
-7 r2c8*,r5c8,r6c58 (4)
-8 r6c8             (1)
-9 r79c4,r8c4*      (3)
-----------------------
                     18 (of which 3 are false eliminations: 4r5c8, 7r2c8, 9r8c4)

Who's willing to test all 18 (or at least 15) PE candidates with nested T&E to find the three that are false eliminations (i.e. true candidates), even if it does solve the puzzle at the end (which the player can't know in advance)? Forgive me if I'm not, even with software support.

Btw, if you covered the 1s with 1b2356 instead of 1r34c47 you'd get two more PEs. In a normal Rank 0 situation that would be a good thing, but here it would be bad because it would be two more candidates to T&E.
User avatar
SpAce
 
Posts: 2671
Joined: 22 May 2017

Re: Phil's Sudoku Solver

Postby SpAce » Fri Jun 26, 2020 2:36 pm

By the way, the same T&E procedure could be used with any almost-Rank-0-pattern, and it makes just as little sense with any of them. Thus, it has nothing to do with "almost-SK-loops" specifically. Here's a simple example with a dual-finned X-Wing:

Code: Select all
.----------------.-----------------------.------------------.
| 9    45    6   |  7-1     278-1   27-1 |  3     8-+1   45 |
| 14   8     15  |  3       9       56   |  7     456    2  |
| 7    2     3   | #16     *1568    4    | *168  #1568   9  |
:----------------+-----------------------+------------------:
| 25   1     9   |  8       26      3    |  4     256    7  |
| 25   3     8   |  467-1   2467-1  1267 |  9     256-1  56 |
| 6    7     4   |  5      *12      9    | *12    3      8  |
:----------------+-----------------------+------------------:
| 148  456   157 |  2       4567-1  1567 |  68    9      3  |
| 3    4569  125 |  469-1   456-+1  8    |  26    7      46 |
| 48   469   27  |  4679    3       67   |  5     2468   1  |
'----------------'-----------------------'------------------'

Finned X-Wing: (1)r36\c57 fr3c48

If it weren't for the two fins (1r3c4, 1r3c8) we'd have a row-based X-Wing (Rank 0) with four eliminations (-1r1578c5). But, since we have those two fins, we actually have a Rank 2 pattern with two base sectors and four cover sectors. That pattern has nine potential eliminations (PEs):

2x4 (Rank 2): (1)r36\c4578 => 9 PEs: -1 r158c4,r1578c5,r15c8

How do we know which ones are true eliminations? We don't. What we do know is that the two base sectors (being native, i.e holding exactly one truth) can only feed two of the four cover sectors, which means that the true candidates in the other two cover sectors can't be base candidates. In other words, two of the PEs must actually be true candidates. It also means that the list of PEs is a SIS (with exactly two truths).

Does that knowledge help us in any way? Well, there are two ways it could possibly help, though neither has much practical value (compared to other, simpler and shorter ways to solve the puzzle):

First, since the list of PEs is a SIS it could be used as a kraken to prove an external elimination. (A nine-branch kraken doesn't sound much fun, though.)

Second, if you can eliminate 7/9 of those PEs you know for sure that the remaining two PEs can be placed. (In this case the puzzle is stte before you get to eliminate all seven, though.)

Would anyone actually do either of those? I think the answer is a solid no. Since the "almost-SK-loop" procedure is exactly the same (usually with more PEs that are much harder to eliminate), I don't see how it would make any more sense with that either.

My conclusion: the only times this approach might make any sense (with any almost-pattern) is when the rank is high (more true candidates among the PEs), the number of PEs is very low (fewer to eliminate), and eliminating those PEs is easy. The last two qualifications are probably non-existent in almost all "almost-SK-loop" situations.
User avatar
SpAce
 
Posts: 2671
Joined: 22 May 2017

Re: Phil's Sudoku Solver

Postby SpAce » Wed Jul 15, 2020 1:46 am

Phil,

I have now twice expressed my displeasure at your copying of my (version of your) memory chain into your help file without crediting me as the author, but no reaction from you. I find that a bit interesting. Haven't you seen those comments, or don't you care?

Many might think I'm petty for complaining, but I have my reasons. They're mostly laid out in the linked comment. Of course I'm flattered if you thought that my chain was such a perfect example that you chose to copy it verbatim, but in that case you could have credited me too. Fact is, no one else writes memory chains in that exact style, and certainly not you.

Then again, like I said earlier, I don't really want to be credited on that page, because I don't want my memory chain style to be associated with a misleading title ("Complex AIC") or false claims that they're not bidirectional or capable of looping. So, perhaps it's best if you (re)replaced that chain with one written in your own style (though preferably not the original horror story), so we both can avoid unwanted associations.

PS. The only reason why I ever commented that stuff in the first place (from which comment you apparently copied that chain) was because one of your disciples referred to your help file with some pretty clueless comments that had to be straightened out. You know, when an authority figure like yourself calls something a "Complex AIC", some people automatically think it's a valid term without ever realizing that memory chains aren't AICs at all (as per the definition used on this forum).

Misleading terms like that, especially used by authority figures, mean more work for people like me who can't stand letting falsehoods spread. (The same applies to misleading claims about the one-move powers of the "Almost SK-Loop". People who can't think with their own brain tend to take claims like that at face value. Sorry if I have a hard time letting it fly.)
User avatar
SpAce
 
Posts: 2671
Joined: 22 May 2017

Re: Phil's Sudoku Solver

Postby denis_berthier » Wed Jul 15, 2020 3:04 am

SpAce wrote:Phil,I have now twice expressed my displeasure at your copying of my (version of your) memory chain into your help file without crediting me as the author, but no reaction from you. I find that a bit interesting. Haven't you seen those comments, or don't you care?


It's really funny that you claim credit for your version of phil's "memory chains", when neither of you credits me for whips, braids,...
"Phil's memory chains" is a name change for my chains (dating back to 2007, in HLS), designed to avoid proper credit to me, and "your" version of them is just a notational change with the same purpose.
However, there are two things that I can gracefully credit to both phil and you:
- both of you equally contribute to misleading Sudoku players
- both of you lack precise definitions and important distinctions between various subtypes of such chains.

About AICs. Are whips, braids, ... AICs? Nobody knows what an AIC is. The term has never been defined and its use has been extended so much that anything can be called and AIC. You have AICs with inner Subsets, you have some with inner URs; you can add anything in an AIC. With such a broadened notion, anything is an AIC. After all, the proof of a whip elimination is also of the form Z => not L1 => R1 => not L2 => R2 ...., so that's alternating, right?

About reversibility. Apart from my definition of it in CRT and PBCS, nobody has ever said what reversibility means. So discussions about it that don't refer to my definition are vacuous. In my definition however, whips, braids, g-whips... are not reversible.
denis_berthier
2010 Supporter
 
Posts: 3383
Joined: 19 June 2007
Location: Paris

Re: Phil's Sudoku Solver

Postby SpAce » Wed Jul 15, 2020 2:31 pm

Post removed for being off topic.
User avatar
SpAce
 
Posts: 2671
Joined: 22 May 2017

Re: Phil's Sudoku Solver

Postby denis_berthier » Wed Jul 15, 2020 3:51 pm

Post removed for being off topic.
denis_berthier
2010 Supporter
 
Posts: 3383
Joined: 19 June 2007
Location: Paris

Re: Phil's Sudoku Solver

Postby SpAce » Wed Jul 15, 2020 5:08 pm

Post removed for being off topic.
User avatar
SpAce
 
Posts: 2671
Joined: 22 May 2017

Re: Phil's Sudoku Solver

Postby denis_berthier » Wed Jul 15, 2020 5:16 pm

Post removed for being off topic.
denis_berthier
2010 Supporter
 
Posts: 3383
Joined: 19 June 2007
Location: Paris

Re: Phil's Sudoku Solver

Postby SpAce » Wed Jul 15, 2020 9:45 pm

Post removed for being off topic.
User avatar
SpAce
 
Posts: 2671
Joined: 22 May 2017

Previous

Return to Software