Sudoku Fundamentals V3

Programs which generate, solve, and analyze Sudoku puzzles

Sudoku Fundamentals V3

Postby nedBlake » Mon Apr 27, 2020 3:32 pm

This is an iPad App that should be appearing in the Apple Store in a few days. This post had to be made first, as it is referenced in the Store.

Sudoku Fundamentals V3 provides major new functions for the iPad.
Each of the topics in the Overview below is detailed following the Overview.



- - - - - - OVERVIEW - - - - - -


Grader Log:
Whether a puzzle is loaded from one of the four libraries, or imported, or created, the Grader solves the puzzle much like a person would solve it.

What has been added is the creation of a text log of the strategies used by the Grader in solving the puzzle.


Visual Aid for chains:
This provides the ability to draw a chain by touching the chain end, causing the next set of possible links for the selected chain type to be displayed.

Touch the end of one of these, then the others disappear, and the next set from the new endpoint appear. You can backtrack by touching any previous endpoint.


Export and Import new functions
Export now includes the ability to export both solved cells and candidates at any point during the solution, as well as the input puzzle. The Grader Log can also be exported. ("Exported" just means "copied to the iPad pasteboard".)

Import will import the above puzzle exports, as well as a puzzle in text-graphic form, such as that found in the Grader Log or on the Puzzle board of this forum.


Level Skipping:
This gives the user the option of advancing the solution to a higher level and candidate state from a more basic level.


Updates to Fundamentals:
Consists of changes and additions to description of the logic behind groups of strategies.



- - - - - DETAILS AND EXAMPLES - - - - -


Grader Log:
The Grader solves puzzles loaded from one of the four libraries in the main menu, or imported, or created or keyed in by you.

The Grader Log is a text file recording solutions and the strategies used to get them, with a brief description of how the more advanced strategies were applied.


Before the Grader has to move to a higher strategy level, because no more progress can be made at the current level, a text-graphic description of the puzzle's solutions and candidates is recorded in the log. This text-graphic can be copied and Imported as an input puzzle that includes candidates.

Includes Eureka-like text that also can be Imported and used to display chains and row-column grid structures such as Swordfish.

This log can be Exported. The idea here is that pages can be printed, or (ideally) the user can paste the log in an email and mailed to another computer, so that the log can be displayed while solving the puzzle on the iPad.

Brief decriptions of the logical basis of the more advanced strategies are inluded in the this log.

The log gives someone not familiar with Sudoku puzzles a quick way to become familiar. It is hoped that teachers of subjects that involve problem solving, who may not be familiar wth Sudoku, will see these puzzles as an excellent exercise for students in the use of logic to solve problems.



Visual Aid for Creating Chains:

This visual aid is based on a simple way to look at most chains.

An Mchain is defined as a chain that strongly links its endpoint candidates:
Either endpoint not being a solution implies the other endpoint must be one.

An Mchain is useful since any candidate in the puzzle that sees both endpoints of the chain is a "hit" and can be eliminated, since one or the other endpoint has to be a solution.

There are other chains described in the Fundamentals, namely those that cause a contradiction. The Grader looks for these if it cannot find any Mchain solutions. In all the test cases we looked at (most of them are imported from the Puzzle board), they were not necessary (the Cchain statistic count was 0), and so no attempt was made to include them in the visual aid.

If you can find them, chains causing contradictions can be very effective, but they don't appear to be necessary for solving a puzzle.

The Mchain endpoints can be different. In this case, the hit "sees" the two endpoints in different ways; seeing one because it is in the same cell as the endpoint, and sees the other because it is in the same row, column or block and is the same number as the endpoint.

It is easy to see by looking at any simple Mchain - take a Ywing as an example - that in order to strongly link the chain endpoints, it must start and end with a strong link, since we are assuming that the endpoint we start from is not a solution.

And to carry the implication that the other end is a solution through to that end, every other link after the first must be strong.


"Mchain" really designates a family of chains, most of which are restricted in some way or other to make them easier to use.
The two major restricted chains are the Xchain (restricted to using only one candidate number) and the other being the XYchain (restricted to using naked pairs for all required strong links).

Other Mchains, such as Ywings and Xwings, are furthur restricted by size. Cycles, (the Xwing is a small example) can be looked at as multiple Mchains, each Mchain formed by removing a weak link in the cycle.

We use the word "Mchain" for the entirely unrestricted chain of this family, except when we are using it to refer to the entire family. By "unrestricted", we mean that the chain can use any strong and weak links between candidates within cells and between candidates in different cells, where the cells exist in the same row, column or block. (If you want, think of the "M" standing for a Medusa chain.)

The visual aid is then very simple. You pick one of the 3 types: Xchain, XYchain, or Mchain. You touch an endpoint. The next link(s) appropriate for that chain type are displayed. You choose one of them by touching its end, and the other possible links (if any) disappear, and a new set of links from the chosen link endpoint are displayed.
If no links appear, you can backtrack by touching a previous cell in the chain.

When you add a strong link to any one of these chains, you are adding a new endpoint. You should not only check to see whether there are any candidates in the puzzle that see both endpoints of the whole chain. You should also check every subchain in the chain that begins with a strong link and ends at this new endpoint.
Subchain checking is generally not done, for good reason - it is time consuming and tedious work, especially if the chain is long.

So we decided to let the computer do the menial work, and highlight the targets found. The result was surprising. You start adding links to a chain, and all of a sudden one or more unexpected gold-colored hits appear.

It's not obvious which subchains have the endpoints that the hit sees, so we temporarily circle the endpoints of the subchains that caused the hit.

Assume either endpoint is not a solution, and then travel the implications link-by-link to the other endpoint, and see that this other endpoint is a solution. So the hit, which may see each of these endpoints in a different way, can be eliminated.

Showing the hits is an option, and the default for this option is "YES". You should leave it that way for at least awhile - it's educational, and can give you an idea of what to look for. Some of the Mchain examples below give you examples of hits that are not at all obvious.


If you select a 1-star puzzle from the Extreme library, you will get only XYchains and perhaps an Xchain. If you solve this puzzle up through the Moderate level, then skip the Advanced level by skipping to the Extreme level (see "Skipping Levels" below), you will almost always be able to solve the resulting puzzle using a single XYchain.

The actual level of the puzzle should really be that of a 1-star puzzle in the Advanced Library. This makes sense, since Mchains are really an extension of the Pointing Pair strategy used to solve Moderate puzzles.
Mchains are in the Extreme library, only because currently that is the level that provides the buttons for solving chains.

The Pointing Pair uses a strongly linked pair of candidates in a block to eliminate candidates in the intersecting row or column that that see the Pair. The Pointing Pair, looked at as a one-link Xchain, belongs in the Mchain family.
Other Mchains just extend the Pointing Pair strategy to eliiminate candidates anywhere in the puzzle.




Import/Export of Puzzle Solutions Plus Candidates:

The Import and Export of the total status of a partially solved puzzle can be useful. The Export button now provides the export of either the input puzzle, or the "above" puzzle, which is the puzzle being solved including solutions and candidates as displayed.

The Import of text depends on there always being at least one blank character following the number string representing a cell's candidates. You can usually depend on this being true, because blank characters are used in a text-graphic to align solutions and candidates.

Once a blank is found following a 2 to 9 string of characters, then its assumed all such strings represent a candidate string.
This means that a naked single must be represented by an "n" preceding the candidate, such as n3 for naked candidate 3.

Besides the communication of partially solved puzzles, you can also find out why you are having a problem solving a puzzle. Just Export the "above" puzzle and then Import it. The Grader will treat it as an input puzzle.
If you "Advance" (see Skipping Levels below) to the level you were at, you may get the message that you are "short (n) solves", or "You have (n) more (or less) candidates". You can then look at the Grader log to find out what you missed.



Skipping Levels:

When you begin solving a puzzle, the solve level toolkit displayed is the Basic toolkit ("Undo" and "Redo" only), and candidates are not displayed.

This differs from previous releases, where the toolkit displayed is the same level as the puzzle level, and all candidates were displayed if not in Newspaper mode.

If you prefer this, then choose the toolkit for the puzzle level, and reply "NO" to the message asking you wether you want to advance the solution to that level. Then proceed to solve the puzzle as you use to do it.

With this release, you might solve it as well as you can at the Basic level, then choose the next solve level. If told that you missed a solution, you might either return to the previous solve level, or you might ignore that you missed a solution, figuring that you would find it at the next level where you had more tools.

Or if you didn't much care for having to find block and line singles at the Basic level, you might advance the solution to the Moderate level. There you would see the Basic solutions filled in as well as all candidates, or if in Newspaper mode, only the candidates for units missing two or three empty cells would be filled in.

Or, as we suggested above when solving 1-star Extreme puzzles, you might advance the solution to the Advanced level, then skip that by advancing to the Extreme solve level in order to get the chain-solving tools without advancing the solution.

In other words, you can select the solve level or levels that you like, and skip those that you don't much care for.

One thing you should know, if you select Newspaper mode, and intend to solve an Extreme 1-star puzzle graded at the Moderate level, followed by solving it at the Extreme level, selecting a puzzle from the Extreme library may take longer than a few seconds.

This is because puzzles in libraries are graded in non-Newspaper mode, and several may have to be re-solved and graded in Newspaper mode to get the correct grade.



Updates to the Fundamentals:

The major update is the restatement of the logic on which chains are based, providing the simple unified basis on which the chain visual aid is based.

A new topic has been added that has the title "Wouldbe Flaw Fixers". A "Flaw Fixer" is a candidate, which if it is a solution, it causes the deletion of some other candidate that is a flaw causing some strategy to be useless. But by fixing the flaw, it causes its own deletion since it is also a target of that strategy.

A "Flaw Fixer" therefore fixes nothing , but can itself be deleted.
Existing strategies like XYZ Wing, Finned Swordfish and Finned X Wing belong to this logic category, and obvious extensions to any type of Mchain are possible but probably are too hard to find to be worthwhile.




- - - - - USING CHAINS - - - - -

As you add links to a chain, the number of subchains increase. And each addition of a strong link causes all of them to have a new endpoint. It follows that the probability of finding a hit increases along with the increase in the number of links.

It makes sense therefore to look at the chain as an investment, and instead of starting a new one after each hit or set of hits, to backtrack if necessary and continue with the current one.


XY Chains.png
XYchain and subchains
XY Chains.png (174.34 KiB) Viewed 1299 times


To solve a puzzle like this one, you can select any 1-star puzzle in the Extreme library or create a random 1-star Extreme puzzle. Then select a solve level of Extreme and then advance the puzzle to that level.


This example is like one used in the Fundamentals, but has been changed to include a subchain cycle, which is indicated by the gold "cycle link' in the second illustration. This cyclelink requirtes some explanation.

On the left, three hits on candidate 5 happen when the last link ito r3c6 is completed. These hits are due to the subchain starting at the circled 5 in r3c5 and ending at the circled 5 at the chain end.

We drop out of Draw mode and delete the 5's. Also 5 is now the solution to r1c7 due to the two 1,6 pairs in c7.

We return to Draw mode and select r2r6 to backup to that cell. In the second illustration, we take a different branch from that cell, but one that ends up with the same subchain expanded; one that now includes a couple of really weak links ("really" in that they are not strong links being used as weak links, and so are drawn as broken lines).

When weak links exist in a cycle, they become strong and the candidates that made them weak can be removed after dropping out of Draw Chain mode.

The cycle link is added automatically because the link drawer won't allow you to create loops in a chain. The cycle link's purpose is to show that a cycle exists, and it automatically disappears after it has shown that this link exists between the subchain endpoints (or the whole chain endpoints if the whole chain is a cycle).

The puzzle is solved by backingup to r5c5, then extended the chain to r2c3, showing a hit on 9 in r6, exposing a single 4 which leads to the puzzle solution.

MchainHits.PNG
Mchains making hits likely
MchainHits.PNG (184.94 KiB) Viewed 1299 times


Like the XYxhain puzzle above, you can also load Mchain puzzles from the Extreme 2-star library or create them.

In this Mchain, we start at candidate 2 in r5c9, a cell that has several candidates. The advantage in doing this is that we now have several candidates that at least \"see\" one end of the chain, namely the candidates in this first cell that see the 2.

You cannot do this with either an Xchain or an XYchain. But you can if you use a combination of the two. It's OK to start an Xwing in a cell with several candidates, then change the chain type to XYchain when the next link is weak and it is going to a pair cell pair where one of the two candidates is an X candidate.

The only difference between the three chain types are the link choices made available for each link. A hybrid chain is perfectly acceptable.

In the first screenshot, we manage to eliminate the 5 in the starting cell by finding another 5 in the same row.

We then take a different branch from the 2 in r3c1 to the 4 in that row and then followed 4's down ro r9c9, where we did the same to remove the 4 in the starting cell.

This chain can be "continued" to solve the puzzle.



The puzzle shown on the right above can be created by Importing the following and Advancing it the Extreme level:

01...3.2....54....5.....6...3.75...17.8............54..9.4....24....8.....1.6.39.

The hits in this solution result from a subchain cycle.

The gold cycle link in r4c8 is not obvious; the clues that a cycle exists are the several pairs of cicled candidates indicating weak links, and the hits resulting from the fact that these weak links now have the same power as a strong link.

To trace a subchain cycle, start with the red candidate in the last cell (in this case the 8 in r4c8) and proceed backwards until you get to the green start of the subchain (in this case the 6 in r4c8). (If you tried tracing from the green 6 in r4c8, you could easily take the wrong path, as there are two paths.)

In this subchain cycle's path, there are two introcellular weak links (in r7c8 and r1c4). It's worth remembering that if you can include an introcellular weak link in an Mchain that all the candidates not part of the link pair in that cell will be hits if the cell is part of a cycle.

Subchain cycles are very common - so common that a cycle link is not shown unless there is at least one weak link that would produce hits.


M subchains 2AB.png
midSummer 2019 puzzle from Puzzle board
M subchains 2AB.png (195.91 KiB) Viewed 1299 times


0.....2...87..1.94...39...1.725...6.4...7...2.1...348.9...35...73.4..92...6......

The above input is that of a puzzle posted on the Puzzles board and titled "Midsummer" some time in the middle of June 2019. The leading "0" is there to make it easier to copy on your iPad; at least the text editor app that I use refuses to select a string beginning with a period.

If you Import it, select a solve level of Extreme and choose YES when it asks whether you want to advance the solution to that level. The message also tells you that it will add two solutions. Pretty amazing, only two solutions were added by all the lower levels.

Also amazing was that the Grader needed a record 12 Mchains (although they had a maximum length of only 7 links) to solve the puzzle.

This was mostly due to changes in the Grader code that generated much smaller chains than previous releases.
Unfortunately, these changes were made before the visual aids for solving chains were created, and led to the difference in the ways that the Grader and the user solved puzzles, which difference really should not exist.

More about this in "Likely Updates" below. But there is some relationship between the number of these small chains and the number of subchains generating hits.

The image on the left shows you a problem that Mchains create. Mchains, as opposed to X- and XYchains, allow multiple branches within cells. In this case, it is almost impossible, with our relatively big fingers, to touch the branch we want. This is solved by extending the branching one more link (if it exists) to an external cell where it can be touched whenever there are two or more introcell branches.

In this example, after a strong link entered to candidate 3, touching the 3 did more than generate the 4 weak links to 2, 5 and 6 in the cell and to the 3 in the row outsde the cell. Since there were more than 1 introcell branch in the cell, an additional level of branching was provided so that the endpoints would be in external cells, where you could select the one you want by touching its cell.

In this case, the additional level of branching resulted in only the one branch, namely that from the 2. This additional level must be strong (the previous one was weak), and often no branches exist.

So if there is only one introcell branch, you need to touch the cell to extend that branch, just like you had to do when extending an XYchain pair cell.

It's true that starting at candidate 1 in r1c1 was the first choice, but there was also some logic in it, as there was a strong link that immediately went to a different area of the puzzle. And after that there seem to be enough branching available to keep travelling around the puzzle adding subchains, with enough branching to backup to if necessary.


Along the way, a hit was uncovered in the bottom row, and then a set of hits was uncovered as shown in the right-hand screen.

This right-hand screenshot shows examples of by far the most common and also the easiest to find hits in Mchains.

The last link to candidate 5 in column 1 has just been added. The color red tells you that it is the strong final link of the whole chain, as well as all the subchains. All chains or subchaiins are drawn starting with the color green.

To find this common hit, you only have to look at the unit (row, column or block) to which this red 5 belongs, and which also contains chain starts indicated by the color green. Usually, the chain start would not also be 5 (if it were, you would delete all other 5's that see this chain start and end).

What you are looking for is a 5 in the start cell. In this case, there are three of them, all of which can be deleted since they see both the start (being in the start cell) and end of the chain (being in the same column).

If you look at the Grader log, you will see that all the 12 short Mchains found hits this way.
This was not due to the Grader looking for this solution first. The Grader processes several branches simultaneously, looking for candidate hits in all 81 cells. The first series of branches that finds a hit is then the solution for that Mchain.

By the same reasoning, you can also delete any candidate that happens to show up in the final cell that is equal to one of the green subchain starts.

Also shown is a hit on the 9 in r1c3. This happened (and was unnoticed) just previously, when the chain final link was the 9 in r6c3. At that time the final 9 and the 3 in r1c3 were circled.


You will find Erase and Redraw more useful with M-Chains. When drawing XYchains, branching only occured from cells, making backtracking fast and simple. With Mchains, you will often find Erase preferable, such as when you have backtracked to a cell, and then want to backtrack to the first candidate of a pair.

Redraw is also useful when you have mistakenly erased a portion or all of your puzzle by accidenty touching some candidate somewhere in your chain. Just tap Redraw until the chain is redrawn before you do anything else.

When solving Mchains, you are more likely to have the solution and not know it. After hits have been deleted, you should use "Selected Candidate" mode to high-light each candidate and look for moderate-level solutions.

Several cell solutions followed from the above, but several more short backtracks and chain extensions were needed to solve this puzzle.




Likely Updates:

The Grader needs to be changed so that it solves chains in the same way that the user solves them.

There is some rough relationship between the "small" chains, like the 12 Mchains in the example above, and the number of subchains producing hits in the single "continued" solution above.
(The "s" in the current chain statistic stands for "small" - in the furure it will stand for "subchain".)

But it's misleading, particularly if the small chains are separated by use of other Advanced strategies. In the example above, this was not true, and so its original 3-star rating was reduced to 2 stars des.

Since Grader statistics are used in creating puzzles, this change should improve puzzles creation.


A major update might be getting rid of the Extreme level puzzle categoey, so that categories would be simply Basic, Moderate and Advanced. I never did like the name "Extreme" anyway.

Puzzles containg only X- and XYchains would be graded Advanced 1-star. The XYchain in particular, because of its branching solely between cells, could have been invented for this visual aid.
Using this aid, you can accurately try multiple XYchain links as fast as you can "visualize" them.

As above, unrestricted Mchain puzzles would be graded Advanced 2-star, if the Mchain subchain solutions can be continued after Basic or Moderate level processing.

Everything that might also require other Advanced or Extreme level strategies would be graded Advanced 3-star.


Any comments or ideas would be appreciated.

Also, if you have a problem with or think there exists a problem in a puzzle, Export and paste the whole puzzle (solutions and candidates) in a post.

If a chain is part of the problem or is the problem, all that is needed is the chain type, the first candidate, and the sequence of the cells (row,col's) visited in the chain.
nedBlake
2018 Supporter
 
Posts: 36
Joined: 08 May 2016
Location: New Bern, North Caroline

Re: Sudoku Fundamentals V3

Postby nedBlake » Fri May 08, 2020 12:57 pm

Sudoku Fundamentals 3.0 for the iPad is now available in the Apple Store.

It certainly has been more than a "few days" getting there. There were problems. One of them is that the latest level of the Apple program that an Apple developer must use to develop an app no longer runs on my Mac mini.

It looks like this release may be my last release unless I get a newer Mac.

I don't mind making nothing on Sudoku Fundamentals (worse than nothing since being an Apple developer costs).
I enjoy programming, and I got a real kick out of this last release in implementing the Visual Aid for Chains.

But a newer Mac would be expensive.
Could you give me some idea of whether buying one might be worth it, by at least rating Sudoku Fundamentals after you have been using it awhile.
I would appreciate it.

I now have one rating but no comment. I have no idea where it came from. I need quite a few more to get some prominence in the Apple Store.
nedBlake
2018 Supporter
 
Posts: 36
Joined: 08 May 2016
Location: New Bern, North Caroline

Re: Sudoku Fundamentals V3

Postby nedBlake » Thu May 14, 2020 2:09 pm

- - - - - Newspaper Mode Puzzles Solved by an XY-Chain - - - - -


If you like to solve Basic- and Moderate-level puzzles in Newspaper mode, and would like to try out the XY-Chain visual aid, then copy and Import one of the puzzles below.

Solve the puzzle through Moderate level, then select Advanced as the solve level. If you get the Message "You are already at this level", then you know that you have solved it through the Moderate level and can now find the solution with an XY-Chain.

You skip the Advanced level by selecting the Extreme Solve level. Ignore any messages about missing solutions or a different candidate count. You are selecting the Extreme level just to get the buttons necessary for drawing the chain and you do not "Advance the solution" to that level.

Select Draw Chain, XY-Chain as the Chain Type, and the suggested starting candidate and cell (or experiment with a different starting points).
After you have started a chain, it's best to drop out of Selected Candidate mode.

When you get one or more hits, drop out of Draw mode and delete the hit(s).

An alternative would be to load Extreme 1-star puzzles from the library while in Newspaper mode. But there are not that many of them in the library, and the loader may take awhile finding one, since it has to grade each 1-star puzzle to see if it meets NPmode criteria. Skipping Advance level strategies may also make solving the chain difficult.

The following puzzles are a much better choice. When you select one on your iPad for copying and Import, don't worry about including the "Try . . ." suggestion. Import ignores anything else after getting 81 puzzle entries.



0...93.6.5..4..9.11.6..8....62.....9.....2.757..86....9.5...21....5....6.8..24...
Try starting at r1c1(4)


0.3..2..67....1.2...1.9.4......67....8......262.....7..5.8....3..8.3..9....1..6..
Try starting at r1c2(4)


04.8.5.1.27....8.9....19..2425.9.......25..347....42.5..7.3.52.6.45......3.9.1.8.
Try starting at r1c1(9)


8....5.6..1..7.5....3.6...14..6...2.92......6...9.7..4..4...98..61..9......25...3
Try starting at r1c3(7)


2.9.........9.3.1...5....843....6..2.4..7.3..9..4.8......68....456..........2.74.
Try starting at r1c6(5)



In case you are not familiar with solving Basic and Moderate puzzles with the Sudoku Fundamentals app, then the following is a summary. This is covered in more detail and examples in the first three topics of the Fundamentals:

Solving a puzzle at the Basic level involves finding unit (block, row or column) singles.
This is done by double-touching any solution, which circles all solutions in the puzzzle that are the same number.
When you see that there is only one empty cell in block units (then line units) that can have this solution, then enter that number in that cell. To do this, select the cell and, optionally, double-touch the number in the keypad.

This double touch option enters the number and "pre-selects" the number, changing its background color in the keypad. Now you can plant it in other cells without using the keypad.

At the Basic level, you only need to enter candidates in units having 2 or 3 empty cells in order to look for "easy" singles.

At the Moderate level, you look for pairs, triples, and quads in order to find candidates to eliminate.

Moderate level also includes looking at line-block intersections for a Pointing Pair or Box(Block)/line Reductiion.
This may require placing candidates in cells of units that having more than 3 empty cells.

A Pointing Pair, if looked at as a one-link chain, meets the requirements of the M-Chain family of chains, namely as a X-Chain. Looking at things this way, makes XY-Chains the logical next step.

At this point, you most likely have or are close to having candidates in all empty cells. If not, fill the few remaining cells.

You are now ready to create the XY-Chain that solves the puzzle.
nedBlake
2018 Supporter
 
Posts: 36
Joined: 08 May 2016
Location: New Bern, North Caroline


Return to Software