YZF_Sudoku

Programs which generate, solve, and analyze Sudoku puzzles

Re: YZF_Sudoku

Postby ghfick » Tue Dec 31, 2019 6:05 pm

Do you know of a list of hard puzzles that contain the Senior Exocet? With the help of your solver, I would like to further explore this move.
It would be helpful to have XY Chains separated from the AICs. In my opinion, XY Chains are a part of the list of Hard [and not Unfair] moves. This represents the only change I ever made to HoDoKu's default ratings. I think your solver separates XY Chains from AICs sometimes [but not all the time?]
In the description of an ALS-XZ move, the z should be capitalized [z ->Z]
29. SuedecCoq should be Sue de Coq [btw I see Sue de Coq as Unfair ... again my personal rating is different from HoDoKu's default rating]
I see you refer to a Uniqueness Test type 7. I am only familiar with the types 1 through 6. Perhaps you have a reference?
I see that you have Forcing Chains that lead to contradictions. There are other Forcing Chains types like the Kraken Row, Kraken Column or Kraken Box. There are the Kraken Fish too. The simplest Kraken Fish [with a single fin] is often 'easy' to spot.
Also, I have always tried to find POMs [called Template Set and Template Delete in HoDoKu].
I see that you have Dynamic Chains in your list. Do you mean Dynamic in the sense of Sudoku Explainer?
Maybe these are on your to-do list? Hope so.

All the best for the New Year!
Gordon
ghfick
 
Posts: 52
Joined: 06 April 2016

Re: YZF_Sudoku

Postby yzfwsf » Tue Dec 31, 2019 11:42 pm

In fact, my solver has separated XY-Chains from AICs, but I let it search both in parallel at the same time. After getting effective steps, exit the searching. It didn't search both first and then.I do not know a list of hard puzzles that contain the Senior Exocet.Other bugs will fix next release.Uniqueness Test 7 is a three strong links UR.
In fact, I've written POM, but it's only used to check whether we need to search for complex fish. Unfortunately, sometimes when POM have Eliminations, we can't find the equivalent complex fish, which is why sometimes the solver searches for complex fish slowly!
BTW i think that chains are similar.

All the best for the New Year to all members of forum!
yzfwsf
 
Posts: 51
Joined: 16 April 2019

Re: YZF_Sudoku

Postby SpAce » Wed Jan 01, 2020 6:05 am

Hi yzfwsf,

I haven't tried your solver but based on this thread it seems very comprehensive. Good job! Looks like it has a lot of functionality missing from Hodoku. However, it also seems to have retained a couple of Hodoku's worst features. You might want to reconsider those to make it even better.

First, your program seems to have DNLs. Why? I consider them one of hobiwan's (few) blunders, though it might have been somewhat understandable at the time of its programming. They're part of the obsolete Nice Loop paradigm and only cause grief in the modern era of AICs. For some unknown (but obviously stupid) reason Hodoku uses them instead of AICs when there's only one elimination, forcing the player to see a confusing mix of two different paradigms. It would be much simpler to use AICs for everything. It would result in shorter chains, and all chains could be found under the same label. Why on earth would a player switch paradigms and write a longer contradiction chain just because an AIC would eliminate only one candidate? It makes zero sense.

DNLs are basically a beginner's way to find chains before they learn to think in terms of AICs. An experienced player would (almost) never use them, which is why I hate to see them as a mandatory chain type in Hodoku. DNLs could be left as an optional feature for those who really want them, but AICs should be the norm for single eliminations too. If you browse the solutions in the Puzzles section on this forum, you won't find but a couple of DNLs, which should give an idea how necessary and popular they are these days.

Secondly, I don't know what notation you're using, but I would strongly suggest following Gordon's advice about Eureka. It's the norm, at least here, and it's also single-handedly the most expressive chaining notation that exists. Hodoku uses the obsolete Nice Loop notation which is awful, and the totally non-standard SudokuWiki notation is even worse. Implication chain notations (using ->) are less awful being intuitively understandable, but they're verbose and less expressive. Eureka is by far the best. You should have it at least as an option even if you personally prefer something else.

yzfwsf wrote:In fact, my solver has separated XY-Chains from AICs, but I let it search both in parallel at the same time

Why would you search them separately? XY-Chains are AICs, as you must know. They're just a specific subtype of them, just like X-Chains (which are the simplest kind of AICs). So, if you're searching for generic AICs you should find X-Chains, XY-Chains, and mixed types, and the types are easy to check and separate afterwards if need be. Of those I would only search X-Chains separately because they're so easy, and their potential for each digit can be seen with a glance (the same for fishes). It's not so clear-cut between XY-Chains and mixed types.

Personally I never look for XY-Chains specifically. Instead I find them as a side effect of searching for generic AICs. In fact, I almost never use XY-Chains at all because they're often long and boring, and most of the time the same effects are available with more efficient mixed type AICs or by compacting them into ALS moves. So, even though XY-Chains are conceptually simpler than mixed types, I find and use much more of the latter. That's why I don't necessarily think XY-Chains are any easier than mixed types. Either way, X-Chains are definitely the easiest, both conceptually and practically, which should be clearly reflected in the difficulty hierarchy.

yzfwsf wrote:In fact, I've written POM, but it's only used to check whether we need to search for complex fish.

It's the only real value it has. POM is not a viable technique for a manual player, except in very simple cases where other techniques work just as well and more simply.

Unfortunately, sometimes when POM have Eliminations, we can't find the equivalent complex fish

Because it doesn't always exist, as discussed here. You might, however, find Oddagon (modern name for "Broken Wings") eliminations in those cases. I guess you don't have those implemented? They're used a lot in the Puzzles section solutions, much more than complex fishes actually (because they're way easier to spot).

yzfwsf wrote:All the best for the New Year to all members of forum!

You too!
-SpAce-: Show
Code: Select all
   *             |    |               |    |    *
        *        |=()=|    /  _  \    |=()=|               *
            *    |    |   |-=( )=-|   |    |      *
     *                     \  ¯  /                   *   

"If one is to understand the great mystery, one must study all its aspects, not just the dogmatic narrow view of the Jedi."
User avatar
SpAce
 
Posts: 2016
Joined: 22 May 2017

Re: YZF_Sudoku

Postby yzfwsf » Wed Jan 01, 2020 12:11 pm

SpAce wrote:Hi yzfwsf

OK, the next version does not contain DNL by default, or provides an option to toggle its search. Broken wings and Uniqueness Loops have been added to my to-do list. I didn't get Eureka's soul and implement it. It's just that I write the candidates are on or off follow the chain path. In fact, I am only an amateur programmer, not proficient in Sudoku. Thank you for your good feedback and suggestions.
yzfwsf
 
Posts: 51
Joined: 16 April 2019

Re: YZF_Sudoku

Postby ghfick » Thu Jan 02, 2020 1:15 am

Solvers will not agree as to the relative difficulty of steps. One of the strengths of HoDoKu is that the default ratings can be altered by the user. I, personally, see X Chains as harder than XY Chains. That is, in part, why I like to see Two String Kites and Skyscrapers separately. Having said that, I also like seeing XY Wings separately; even though XY Wings are just short XY Chains. With HoDoKu, you can group steps together by changing the default ratings as you wish.

Years back, I asked Bernhard to separate Sue de Coq into two steps :the basic Sue de Coq [which is quite easy to spot] and then the more elaborate ones. While I believe he agreed with me in principle, at the time, he said it was a hard programming matter.

I know that StrmCkr has various subcategories of ALS steps separated in his solver. So he has WXYZ Wings, VWXYZ Wings and many others. I see merit to this type of separation/partitioning of ALS. Finding general ALS moves is very challenging [ for me, anyhow ]. tarek's recent sukaku explainer offers some of these separations [even three string kites!] as does Sunnie's revision to SE.

So, in my opinion, for your solver, separating a class of steps into parts is a plus. A person reading a solution path or considering the results in the All Possible Steps tab can group them as they might wish.

My preference, then, would be to see XY Chains and then X Chains before the more general AICs in the 'Solution Path'. The 'All Possible Steps' tab should still contain them all with your nice feature to show component sets if one wishes.

There continues to be discussions on the forum and elsewhere about chains and loops. I am certainly not an authority on these matters. I do see merits to distinguish between continuous and discontinuous. Continuous loops can have impressive lists of exclusions. So, then, I think keeping Continuous Loops separate [somehow] has appeal to me.

I think your solver is already so fine. Be pleased to see your steps forward in the future too.

Gordon
ghfick
 
Posts: 52
Joined: 06 April 2016

Re: YZF_Sudoku

Postby SpAce » Thu Jan 02, 2020 7:07 am

ghfick wrote:Solvers will not agree as to the relative difficulty of steps.

True. That's why default ratings should be based on objective measures as much as possible.

One of the strengths of HoDoKu is that the default ratings can be altered by the user.

Yes, but if they're changed by the user they're no longer default ratings. They're custom ratings.

I, personally, see X Chains as harder than XY Chains.

I know, but that's a very subjective view and probably due to your apparent specialization in XY-Chains. Objectively X-Chains are clearly simpler because they only use one digit, and they're way easier to find for a player who's equally skilled in all types of chains. It's very easy and fast to isolate the digits that have potential for single-digit patterns (X-Chains, fishes, Oddagons, POM), and in simpler puzzles most digits can be quickly excluded limiting the search. Hodoku digit filters make it trivial (I can see in a couple of seconds whether a digit has such potential or not). They also make it very easy to find any available X-Chains for the potential digits, especially if coloring is used.

That said, spotting X-Chains is actually relatively easy even without any aids or pencil marks, which can't be said about XY-Chains (including XY-Wings). The only non-basic patterns that are easier to spot than short X-Chains are URs. In fact, both URs and X-Chains are usually easier, especially without pm, than the hardest basics such as quads and even triples.

That is, in part, why I like to see Two String Kites and Skyscrapers separately.

You're forgetting Turbot Cranes -- the third type of Turbot Fishes. So does Hodoku, which is another annoying weakness of it.

Having said that, I also like seeing XY Wings separately; even though XY Wings are just short XY Chains.

Of course. Who doesn't? I'd also want to see W-Wings, S-Wings, H-Wings, M(2..3)-Wings, and L(1..3)-Wings separately even though they're all generic AICs. That said, I would never look for them specifically -- except sometimes W-Wings and Y-Wings which are relatively easy to spot as patterns (in that order). All the others (except L1-Wings which are X-Chains) I find as generic AICs and then name them afterwards (just for fun).

Years back, I asked Bernhard to separate Sue de Coq into two steps :the basic Sue de Coq [which is quite easy to spot] and then the more elaborate ones.

I would agree with that. Some of the complex SDCs would be ridiculously hard to spot as such, and they're actually simpler to see as their hidden counter-parts. That said, I never look for SDCs anyway. I find them as ALS-Loops (i.e. Doubly-Linked ALS-XZs) while searching for AICs.

While I believe he agreed with me in principle, at the time, he said it was a hard programming matter.

Sounds like a really bad excuse. I can't see how it could be hard at all.

I know that StrmCkr has various subcategories of ALS steps separated in his solver. So he has WXYZ Wings, VWXYZ Wings and many others. I see merit to this type of separation/partitioning of ALS.

Sure, it's fun in the same way as having names for the one-letter wings, Turbot Fishes, or any other chaining patterns. However, none of it makes any difference for actual solving if you have effective methods to find AICs. I'd never look for anything more complex than XYZ-Wings specifically, and even those rarely. All the more complex (UVW)XY(Z)-Wing types, as well as other ALS moves, I find as generic AICs and name them after the fact.

Finding general ALS moves is very challenging [ for me, anyhow ].

It's not much harder than finding AICs in general -- and finding AICs is easy if you have good tools for that. Of course some large ALSs can be tricky to spot, but in those cases there's often a simpler AHS available.

tarek's recent sukaku explainer offers some of these separations [even three string kites!] as does Sunnie's revision to SE.

Named patterns are fun, and they're good for communicating simple moves. That said, for actual solving it's a very inefficient strategy to look for any but the simplest kinds specifically. In most cases generic methods fly circles around that type of solving. Furthermore, named patterns should be unambiguously defined and easy to recognize, and (as I've told tarek) giving specific names to various L1-Wing shapes (such as 3-String Kites) is on the verge of breaking those rules already.

My preference, then, would be to see XY Chains and then X Chains before the more general AICs in the 'Solution Path'.

Sure, but X-Chains should be before XY-Chains by default. Definitely. Of course a player should be free to change that order, but as a default hierarchy nothing else makes sense. Similarly Turbot Fishes should be before any wing types, because the latter are inherently more complicated (having more digits and links).

There continues to be discussions on the forum and elsewhere about chains and loops. I am certainly not an authority on these matters.

I can't make any judgment about that because I've never seen how you actually solve a puzzle. In any case it's probably fair to say that most of us regulars in the Puzzles section are more or less authorities in matters relating to chains and loops, because it's what we do on a daily basis. In fact, there are hardly much better authorities on this planet. Why don't you join us? There's plenty of room, especially now that I'm taking a break. (I'd be taking a break from this too if I saw any indication that my offer was taken, but doesn't seem like it thus far.)

I do see merits to distinguish between continuous and discontinuous. Continuous loops can have impressive lists of exclusions. So, then, I think keeping Continuous Loops separate [somehow] has appeal to me.

Of course. Everyone loves (continuous) loops. They just should be called AIC-Loops -- not "Continuous Loops" which again implies the obsolete Nice Loop paradigm. In the AIC terminology "loop" implies "continuous" automatically, as there's no such thing as a discontinuous loop. Even if one is used for some reason, it's just an AIC with the same node as both end points, so it doesn't need its own type or definition.
User avatar
SpAce
 
Posts: 2016
Joined: 22 May 2017

Re: YZF_Sudoku

Postby StrmCkr » Fri Jan 03, 2020 10:59 pm

Code: Select all
 know that StrmCkr has various subcategories of ALS steps separated in his solver


not exactly:
i have 1 b.a.r.n engine that does size 1-8 for digit count {9 cells max} limited to row/col + box intersection
that accounts for the normal: xy,xyz, wxyz wings and the 4 others size past these more commonly used ones.

{mostly a redundant project as i have always stood by that these are redundant due to their inherent nature of being als-xz functions merely limited by search space }

wxyz wings - is the only b.a.r.n that should be added to hodoku technically as its a listed technique on many solving sites.
-it should be noted this is the first size of als-xz that can use the double linked rule.


i have an:
als engine for xz, {double linked rule} {which includes the barns,sudecoqs}
Ahs engine for xz, {double linked rule}
als engine for xy, {triple linked rule} {which includes death blossoms}
als - chain { multi-linked rule} -- coded but still a work in progress

AAls 2*RC - engine
N*a-ls N*RC - engine -- work in progress

theoretic:
N*A-LS N*RC - Chain {multi-linked rule} should be the parent technique that accounts for all of the subsets listed before this one.



however:
my solver is a batch mode depth first solver finding all moves {with eliminations or not} at each step per selected technique: i can manually fine tune it to reduce search size to isolate stuff by size, and remove the non elimination moves from being listed.

what i do have isolated individually and coded is theses wings/rings : S,W,M,L,L2,H(1-5),iW, Strong,
which are all short: AIC's and easy to find/identify

i also have a chain hybrid versions {where the bivalves are replaced by an als}
als - w wing/ring
als - S wing
als - M wing/ring

- which can replace the same name wings above as they are found under the same engine as the simplest case

these techniques having a name is a reason i advocate for their inclusion into the aic engine instead of a generic massive chain finder
given their short size they are more human friendly to use is the 2nd reason i want to see them included.

which gives rise to a better grading system when smaller techniques can be used first before scaling into more complex/bigger chain sizes which is the third reason to include them
Some do, some teach, the rest look it up.
User avatar
StrmCkr
 
Posts: 1079
Joined: 05 September 2006

Re: YZF_Sudoku

Postby yzfwsf » Sat Jan 04, 2020 2:54 pm

Added UL Type 1, 2, 3, 4, Broken Wing Basic Edition. Eureka notation are now available for all simple AICs. To provide the Broken Wing , the POM is called early, which results in a slight decrease in speed. By default, DNL is not displayed now, but an option is provided to make it appear.
Release 606 https://drive.google.com/open?id=1W8U6alSZQYHyyrbUDv1YkJkLNaVwCIs9
yzfwsf
 
Posts: 51
Joined: 16 April 2019

Re: YZF_Sudoku

Postby SpAce » Sat Jan 04, 2020 7:35 pm

yzfwsf wrote:Added UL Type 1, 2, 3, 4, Broken Wing Basic Edition. Eureka notation are now available for all simple AICs. To provide the Broken Wing , the POM is called early, which results in a slight decrease in speed. By default, DNL is not displayed now, but an option is provided to make it appear.

Very nice! I guess I need to install Windows somewhere to get to test this (and XSudo as well). Not sure when I'll get around to it, but at least now I have two good reasons.
User avatar
SpAce
 
Posts: 2016
Joined: 22 May 2017

Re: YZF_Sudoku

Postby ghfick » Sat Jan 04, 2020 8:35 pm

Now I have learning Broken Wings and Uniqueness Loops on my to-do list.
The Eureka notation works well. I may be able to offer a minor tweak. If a digit at a node does not change from the previous the digit is usually not repeated in the next part of chain. [at least I think so]
for example, at the end : (3=7)r2c5-(7=6)r1c4-(6)r3c5=(6)r8c5 => r8c5<>3 could be (3=7)r2c5-(7=6)r1c4-r3c5=r8c5 => r8c5<>3

If your OS is Linux/Unix, I use Wine and both YZF_Sudoku and XSudo run quite well.
StormDuko requires some knowledge about Pascal and I am fairly sure one must have MS Windows for it to work. 1to9only has added some features but I am not savvy enough to handle the Pascal.
Time to learn, perhaps. I remain resistant to any involvement with MS Windows directly though.
ghfick
 
Posts: 52
Joined: 06 April 2016

Re: YZF_Sudoku

Postby creint » Sat Jan 04, 2020 9:00 pm

Are you gonna release the source code/pseudocode for sk-loops, msls, exocet?
creint
 
Posts: 146
Joined: 20 January 2018

Re: YZF_Sudoku

Postby 1to9only » Sat Jan 04, 2020 9:07 pm

StormDoku pascal source (latest is StormDoku vrs 7.69.pas) is here.
I used Free Pascal (latest release is 3.0.4) from here to compile for Windows.
Free Pascal is available for many Processors and OS combos, e.g.
Code: Select all
AMD64/Intel 64/x86_64
- FreeBSD
- Linux
- Solaris
- Windows 64-bit

So building a Linux version is feasible.
1to9only
 
Posts: 1408
Joined: 04 April 2018

Re: YZF_Sudoku

Postby yzfwsf » Sat Jan 04, 2020 10:56 pm

creint wrote:Are you gonna release the source code/pseudocode for sk-loops, msls, exocet?

For JE, 1458 structures were pre-processed in advance, and then each structure was checked against David PB's JExocet Compendium item by item. For MSLS, build the m x n grid structure in advance, and then calculate its Rank for each structure in a loop. You can try various combinations of Link-Sets to adjust the Rank (you can try to change multiple Line-Links into Box-Links decrease Rank). If Rank is zero, then find the MSLS. If not, we can set a threshold Rank so that part of the AMSLS is included in the further inspection list. Let us further look at the cells covered by the Link-Sets that are not in the structure and can be completely covered. We include it in the structure. In the unstructured cells involved in the Link-Sets, pre-delete the number and see if you can find a negative Rank Naked-Set, if so,include it .If now the Rank is zero,done!
yzfwsf
 
Posts: 51
Joined: 16 April 2019

Re: YZF_Sudoku

Postby SpAce » Sun Jan 05, 2020 3:46 am

ghfick wrote:The Eureka notation works well. I may be able to offer a minor tweak. If a digit at a node does not change from the previous the digit is usually not repeated in the next part of chain. [at least I think so]

for example, at the end : (3=7)r2c5-(7=6)r1c4-(6)r3c5=(6)r8c5 => r8c5<>3 could be (3=7)r2c5-(7=6)r1c4-r3c5=r8c5 => r8c5<>3

Almost. The optimal way is to always have a digit in the last node, even if it's a repeated one. That's for symmetry, because the two end points are the most important nodes in the whole chain, plus any AIC should be easy to read backwards as well. Besides, it looks more balanced.

If such a nuance is not possible, I think it's better to repeat the digits in all nodes than to not have it in the last node. I always look at the end points first, and it's really annoying if I have to look for the missing digit elsewhere in the chain. I often check chains backwards as well, which has the same issue.

All three variants are correct, and it's a minor detail anyway, but one is quite objectively the best option for readability. However, I think adding white space would help with readability even more. Personally I'd also prefer the forum elimination style because it's less cluttered and easier to read (especially with multiple eliminations). So, this is how I'd write it:

Code: Select all
H-Wing:

(3=7)r2c5 - (7=6)r1c4 - r3c5 = (6)r8c5 => -3 r8c5

That said, any variant of Eureka is better than nothing!

If your OS is Linux/Unix, I use Wine and both YZF_Sudoku and XSudo run quite well.

Good to know. I use OSX (which is Unix), so there are quite a few options (Wine included). I just haven't got around to installing any.

I remain resistant to any involvement with MS Windows directly though.

Words of wisdom :)
User avatar
SpAce
 
Posts: 2016
Joined: 22 May 2017

Re: YZF_Sudoku

Postby SpAce » Mon Jan 06, 2020 10:15 pm

Hi yzfwsf,

How do you deal with Turbot Fish names? That would be one more place to improve on Hodoku. Here are some recent comments about that with links to the original discussions. There's already one solver (tarek's Sukaku Explainer) that has adopted that naming scheme (as far as I know), and I'd be happy to see more to follow that lead.

In other words, what I'd love to see is these two hierarchies implemented:

Code: Select all
                                 AICs
                                   |
                               X-Chains                   
                                   |                     
                             Turbot Fishes               
                                   |                     
           -----------------------------------------------   
          |                        |                      |
     [Skyscraper]           [2-String Kite]         [Turbot Crane]

Code: Select all
                                 AICs
                                   |
                           Grouped X-Chains
                                   |
                         Grouped Turbot Fishes
                                   |
           -------------------------------------------------
          |                        |                        |
[Grouped Skyscraper]    [Grouped 2-String Kite]    [Grouped Turbot Crane]

Hodoku doesn't have a concept of "Turbot Crane". Those patterns are found as generic Turbot Fishes, but there's no way to filter them specifically (i.e. Skyscrapers and Kites are included too). It doesn't know Grouped Skyscrapers or Grouped 2-String Kites either (they can be found as generic AICs/DNLs or fishes). Grouped Turbot Cranes are found as ERs, but that name is ambiguous as well and should preferably be replaced despite its ubiquitous nature.
User avatar
SpAce
 
Posts: 2016
Joined: 22 May 2017

PreviousNext

Return to Software